第五章图论（三）.pptVIP

第五章 图论 5.3图的表示和同构 5.3.1图的邻接矩阵 n阶图的邻接矩阵是方阵A=(aij)n×n 例3 简单图的例子 将7-27所示的图用相邻矩阵表示。 图的邻接矩阵不唯一，取决于顶点的排列顺序 无向图的邻接矩阵对称 例5 伪图的表示 用相邻矩阵表示图7-29所示的伪图 5.3.2图的同构 同构的图：本质上相同的图，表示了类似的集合和关系 定义1 简单图同构 G1，G2，?一一对应f：V1→V2，使 (a, b)∈E1?(f(a), f(b))∈E2 例8 说明图G=(V, E) 和H=(W, F)同构。 解： 函数f满足f(u1)=v1,f(u2)=v4 ,f(u3)=v3 ,f(u4)=v2 ,它是V和W之间的一一对应。为了看出这个对应保持相邻关系，注意G里相邻的顶点是u1和u2， u1和u3，u2和u4，以及u3和u4，由f(u1)=v1和f(u2)= v4 ，f(u1)=v1 和f(u3)= v3 ，f(u2)= v4和f(u4)= v2 ，以及f(u3)= v3和f(u4)= v2所组成的每一对顶点都是在H里相邻的。 同构的充分条件，可用于判定同构 给出一个顶点的一一对应，按相应的顺序求出邻接矩阵 邻接矩阵相同?同构 同构的必要条件，可用于判定不同构 （1）顶点数相同 （2）边数相同 （3）顶点度的升序相同 （4）同度顶点构成的子图都同构 例9 说明图7-33所示的图不同构。 解 G和H都具有5个顶点和6条边。不过，G有1度顶点e而H没有1度顶点。所以G与H是不同构的。 例10 判断图7-34所示所示的图是否同构。 解 图G和H都具有8个顶点和10条边。它们都具有4个2度顶点和4个3度顶点。因为这些不变量都相同，所以可能想到它们是同构的. 然而G和H不是同构的。为了看明白这一点，注意到因为在G里deg(a)=2，所以a必然对应于H里的t，u，x或y，这是因为这些顶点是H里的2度顶点。不过， H里的这4个顶点中每一个都与H里另一个2度顶点相邻，但是在H里a却不是这样的。 看出G与H不同构的另一种方式是，注意到若这两个图同构，则由3度顶点和连接它们的边所组成的子图同构（读者应当验证它）。然而图图所示的这些子图却不是同构的。 习题 1.什么是无向图的相邻矩阵的一行中的各项之和？对有向图来说呢？ 2.设G和H是同构的简单图。证明：它们的补图和也是同构的。 3.带有3个顶点的非同构的简单图有多少个？ * *