可图化 对于给定的非负整数列d=(d1,d2,…,dnl,若存在以V={v1, v23…,Vn}为顶点集的n阶无向图G,使得叫(v)=d则称d是可图 化的 特别地,若所得图是简单图,则称d是可简单图化的 给定非负整数列d=(d1,d2,……,dn),如何判断其是否可图化 的? 可以使用下列定理 定理:设非负整数列d=(d1,d2,…,dn),则d是可图化的,当且仅当 E=1.nd1=0(mod2) 16
16 可图化 对于给定的非负整数列d = (d1, d2, …, dn), 若存在以V = { v1, v2, …, vn }为顶点集的n阶无向图G, 使得d(vi) = di, 则称d是可图 化的。 特别地, 若所得图是简单图, 则称d是可简单图化的。 给定 非负整数列d = (d1, d2, …, dn), 如何判断其是否可图化 的? 可以使用下列定理. 定理: 设非负整数列d = (d1, d2, …, dn), 则d是可图化的, 当且仅当 Σi=1..ndi = 0 (mod 2)
可图化 定理:设非负整数列d=(d1d2…,dn,则d是可图化的 当且仅当Σ=1nd1=0mod2) 证明:由握手定理可知:必要条件是显然的。 下面证明其充分性。由已知条件可知:d中有2k(0≤k≤ Ln/2小个奇数。不妨设这些奇数为:d,d2…,dk,d+1, dk+2,…,d2。做出n阶无向图G=<V,E>,v={v1,V2,…,vn} 的方法如下: 首先,在顶点V与v+k之间连边(r=1.k 若d为偶数,令d=d;若d为奇数,令d;=d1-1,得 d=(d'1d2y,d'n),其中d均为偶数 再在v处做出d2条环(i=1n)将所得各边集合在一起 17组成E,则G的度数列为d
17 可图化 定理: 设非负整数列d = (d1, d2, …, dn), 则d是可图化的, 当且仅当Σi=1..ndi = 0 (mod 2) . 证明: 由握手定理可知: 必要条件是显然的。 下面证明其充分性。由已知条件可知: d中有2k(0 ≤ k ≤ ⎣n/2⎦)个奇数。不妨设这些奇数为: d1, d2, …, dk, dk+1, dk+2, …, d2k。做出n阶无向图G = <V, E>, V = { v1, v2, …, vn } 的方法如下: 首先, 在顶点vr与vr+k之间连边(r = 1..k); 若di为偶数, 令d’i = di; 若di为奇数, 令d’i = di - 1, 得 d’=(d’1,d’2,…, d’n), 其中d’i均为偶数. 再在vi处做出di’/2条环(i = 1..n), 将所得各边集合在一起 组成E, 则G的度数列为d
可图化 定理:设G为任意n阶无向简单图,则△(G)≤n1 证明:因为G是简单图,所以G中无平行边,也无环 这样,G中任何顶点V至多与其余n-1个顶点相邻,即 d(v)≤n-1。由v的任意性可知:△(G)≤n-1。 18
18 可图化 定理: 设G为任意n阶无向简单图, 则Δ(G) ≤ n-1。 证明: 因为G是简单图, 所以G中无平行边, 也无环. 这样, G中任何顶点v至多与其余n-1个顶点相邻, 即 d(v) ≤ n-1。由v的任意性可知: Δ(G) ≤ n-1
图的同构 定义:设G1=<V1E1>,G2=<V2,E2>为两个无向图(两个有向图) 若存在双射函数f:V1→V2对于vveV1wpv)∈E(vy>∈E) 当且仅当(,(y)∈E2(f(v,f(y少>eE2,并且vvy)(y) 与(f(v,(y)(fv,f(y)2)的重数相同,则称G1与G2是同构的 ( amorphic),记作:G1≌G2 19
19 图的同构 定义: 设G1=<V1, E1>, G2=<V2, E2>为两个无向图(两个有向图)。 若存在双射函数f: V1→V2, 对于vi, vj∈V1, (vi, vj)∈E1(<vi, vj>∈E1), 当且仅当(f(vi), f(vj))∈E2(<f(vi), f(vj)>∈E2), 并且(vi, vj) (<vi, vj>) 与(f(vi), f(vj))(<f(vi), f(vj)>)的重数相同, 则称G1与G2是同构的 (Isomorphic), 记作: G1 ≅ G2
图的同构 图之间的同构关系可看成全体图集合上的二元关系,该二元 关系是自反、对称和传递的,因此,它是等价关系。 在同构关系的每个等价类中取一个非标定图作为其代表,凡与 它同构的图,在同构含义下都可看成一个图 20
20 图的同构 图之间的同构关系≅可看成全体图集合上的二元关系, 该二元 关系是自反、对称和传递的, 因此, 它是等价关系。 在同构关系的每个等价类中取一个非标定图作为其代表, 凡与 它同构的图, 在同构含义下都可看成一个图