第9章图论 a ba od 2 03 40 (a) (b) 图9.6
第9章 图论
第9章图论 定义9.1.10设G=<V1,E1>与G2<V2,E2>是两个无向图 (有向图)，若存在双射函数 f:V1→V2,v1∈V1,v2∈Vi (y1,2)eE1(<1,V2>∈E)当且仅当 (v1)2)∈E2)(≤v)v2>∈E2) 并且(y1,2)(<y1,y2>)与（优y)2)≤y1)2>)的重数相同， 则称图G1与图G2同构。记为G2G2。双射函数称为图G1 与图G,的同构函数
第9章 图论 定义9.1.10 设G1 =V1 ,E1 与G2 =V2 ,E2 是两个无向图 (有向图)，若存在双射函数 f：V1→V2，v1V1，v2V1 (v1 ,v2 )E1 (v1 ,v2 E1 )当且仅当 (f(v1 ),f(v2 ))E2 )(f(v1 ),f(v2 )E2 ) 并且(v1 ,v2 )(v1 ,v2 )与(f(v1 ),f(v2 ))(f(v1 ),f(v2 ))的重数相同， 则称图G1与图G2同构。记为G1≌G2。双射函数f称为图G1 与图G2的同构函数
第9章图论 两个图同构必须满足下列条件： ①结点数相同。 ②边数相同。 ③度数相同的结点数相同。 这三个条件是两个图同构的必要条件，不是充分条件。 般的，用上述三个必要条件判断两个图是不同构的。 两个图同构，它们的同构函数必须实现同度结点对应 同度结点
第9章 图论 两个图同构必须满足下列条件： ①结点数相同。 ②边数相同。 ③度数相同的结点数相同。 这三个条件是两个图同构的必要条件，不是充分条件。 一般的，用上述三个必要条件判断两个图是不同构的。 两个图同构，它们的同构函数必须实现同度结点对应 同度结点
第9章图论 9.1.5补图、子图和生成子图 定义9.1.11设G=<V,E>是n阶简单无向图，G中的所有 结点和所有能使G成为完全图的添加边组成的图称为图G 的相对于完全图的补图，简称为G的补图。记为G。若 G≌G,则称G为自补图 在图9.9 ao b 中，(b)是(a 的补图，(a)与 (b)同构，所 以(a)是自补图。 do do (a) (b) 图9.9
第9章 图论 9.1.5补图、子图和生成子图 定义9.1.11 设G=V,E是n阶简单无向图，G中的所有 结点和所有能使G成为完全图的添加边组成的图称为图G 的相对于完全图的补图，简称为G的补图。记为 。若 G≌ ，则称G为自补图。 在图9.9 中，(b)是(a) 的补图，(a)与 (b)同构，所 以(a)是自补图。 G G
第9章图论 定义9.1.12i 设G=<V,E>与G,=<V,E>是两个图。如果 VV且EE,则称G1是G的子图，G是G,的母图；如果 V∈V且EcE,则称G是G的真子图；如果V,=V且E,cE则 称G1是G的生成子图。 在图 b 9.10中， (b)是(a)的 子图、真 子图、生 成子图。 d do (a) (b) 图9.10 返回章目录
第9章 图论 定义9.1.12 设G=V,E与G1 =V1 ,E1 是两个图。如果 V1V且E1E，则称G1是G的子图，G是G1的母图；如果 V1V且E1E，则称G1是G的真子图；如果V1 ＝V且E1E则 称G1是G的生成子图。 在图 9.10中， (b)是(a)的 子图、真 子图、生 成子图。 返回章目录