第章图论 ba 4 图9.6
第9章 图论
第章图论 定义9.1.10设G1=<V1,E1>与G2=<V2E2>是两个无向图 (有向图),若存在双射函数 →2,、v1∈,2e (v12)∈E1(<v12>∈E1)当且仅当 fv1)f(v2)∈E2)(<(v1)f(v2)>∈E2) 并且(v1,2)(<v1n2>)与(v1)f(v2)<fv1)/(v2))的重数相同, 则称图G1与图G2同构。记为G1≌G2。双射函数称为图G1 与图G2的同构函数
第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章 图论 两个图同构必须满足下列条件： ①结点数相同。 ②边数相同。 ③度数相同的结点数相同。 这三个条件是两个图同构的必要条件，不是充分条件。 一般的，用上述三个必要条件判断两个图是不同构的。 两个图同构，它们的同构函数必须实现同度结点对应 同度结点
第章图论 91.5补图、子图和生成子图 定义91.11设G=<V,E>是n阶简单无向图,G中的所有 结点和所有能使G成为完全图的添加边组成的图称为图G 的相对于完全图的补图,简称为G的补图。记为G。若 G≌G,则称G为自补图 在图9.9a9 O b 中,(b)是(a) 的补图,(a)与 (b)同构,所 以(a)是自补图 (a (b) 图99
第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
第章图论 定义91.12设G=<VE>与G=<V1E1>是两个图。如果 V且EcE,则称G1是G的子图,G是G1的母图;如果 V1V且E1cE,则称G1是G的真子图;如果V=V且E1cE则 称G1是G的生成子图。 在图 9.10中, ao (b)是(a)的 子图、真 子图、生 成子图 图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)的 子图、真 子图、生 成子图。 返回章目录