对于给定的非负整数列d=(d1,2,dn 若存在/={y,2,yn,使是()=d,则称d 是可图化的.特别地，若所得图是简单图，则称 d是可简单图化的. 定理14.3 设非负整数列d=(d1,d2,d),则 称d可图化的充要条件是Σd,是偶数. 定理14.4设G为任意n阶无向简单图，则4(Gsn-1. 16
16 对于给定的非负整数列d=(d1 , d2 , ., dn ), 若存在V={v1 , v2 , ., vn },使是d(vi ) =di ,则称d 是可图化的.特别地,若所得图是简单图,则称 d是可简单图化的. 定理14.3 设非负整数列d=(d1 , d2 , ., dn ),则 称d可图化的充要条件是∑di是偶数. 定理14.4 设G为任意n阶无向简单图,则(G) ≤ n-1
握手定理的应用 例1(3,3,3,4)，(2,3,4,6,8)能成为图的度数列吗？ 解不可能.它们都有奇数个奇数， 例2已知图G有10条边，4个3度顶点，其余顶点的度 数均小于2，问G至少有多少个顶点？ 解设G有n个顶点.由握手定理， 4x3+2x(n-4)≥2x10 解得 n28
17 握手定理的应用 例1 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗? 解 不可能. 它们都有奇数个奇数. 例2 已知图G有10条边, 4个3度顶点, 其余顶点的度 数均小于2, 问G至少有多少个顶点? 解 设G有n个顶点. 由握手定理, 43+2(n-4)210 解得 n8
握手定理的应用（续） 例3证明不存在具有奇数个面且每个面都具有奇数 条棱的多面体. 证用反证法.假设存在这样的多面体， 作无向图G=<V,E>,其中={y|v为多面体的面， E={(,)川w,VEVAu-与有公共的棱Au≠以. 根据假设，I为奇数且veV,d(y)为奇数.这与握 手定理的推论矛盾。 18
18 握手定理的应用(续) 例3 证明不存在具有奇数个面且每个面都具有奇数 条棱的多面体. 证 用反证法. 假设存在这样的多面体, 作无向图G=<V,E>, 其中V={v | v为多面体的面}, E={(u,v) | u,vV u与v有公共的棱 uv}. 根据假设, |V|为奇数且vV, d(v)为奇数. 这与握 手定理的推论矛盾
图的同构 定义设G=<V1,E1>,G2=<V,E2>为两个无向图（有 向图)，若存在双射函数fV1→V,使得对于任意的 y∈V, (y)∈E1(<,旷∈E)当且仅当 vfy)》eE2（fvfy>∈E2), 并且，((<y,旷)与y》(y>） 的重数相同，则称G与G,是同构的，记作G≥G2, 19
19 图的同构 定义 设G1 =<V1 ,E1 >, G2 =<V2 ,E2 >为两个无向图(有 向图), 若存在双射函数 f: V1V2 , 使得对于任意的 vi ,vjV1 , (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是同构的，记作G1 G2
图的同构（续） 几点说明： 图之间的同构关系具有自反性、对称性和传递性。 能找到多条同构的必要条件，但它们都不是充分条件： ①边数相同，顶点数相同 ②度数列相同（不计度数的顺序） ③对应顶点的关联集及邻域的元素个数相同，等等 若破坏必要条件，则两图不同构 至今没有找到判断两个图同构的多项式时间算法 20
20 图的同构(续) 几点说明： 图之间的同构关系具有自反性、对称性和传递性. 能找到多条同构的必要条件, 但它们都不是充分条件: ① 边数相同，顶点数相同 ② 度数列相同(不计度数的顺序) ③ 对应顶点的关联集及邻域的元素个数相同，等等 若破坏必要条件，则两图不同构 至今没有找到判断两个图同构的多项式时间算法