可图化、可简单图化 设G=<VE>为一个n阶无向图,V={1V2…,Vn},称 dv1)d(v2)d(n)为G的度数列。对于顶点标定的无向图,它的度数 列是唯一的。反之,对于给定的非负整数列d=(d1,d2…,d),若存在以 V={vV2…vn}为顶点集的n阶无向图G,使得d(v)=d则称d是可 图化的。特别的,如果所得图是简单图,则称d是可简单图化的。 d=(4,4,2,1,3) V=(v1,v2,v3,V4,V5) 东南大学计算机科学与工程学院 同的出学 图论
设 G=<V,E> 为一个 n 阶无向图 ， V ＝ ｛ v1 ,v2 ,…,vn ｝ ， 称 d(v1 ),d(v2 )…d(vn ) 为G的度数列。对于顶点标定的无向图，它的度数 列是唯一的。反之，对于给定的非负整数列d=(d1 ,d2 ,…,dn ),若存在以 V＝｛v1 ,v2 ,…,vn｝为顶点集的n阶无向图G，使得d(vi )=di则称d是可 图化的。特别的，如果所得图是简单图，则称d是可简单图化的。 v1 v2 v3 v4 v5
可图化的判定定理 定理143非负整数列d=(d1d2d)是可图化的当且仅当∑为偶数。 由定理141可知,度数之和必为偶数,必要性得证。 定理的充分性采用构造法证明(的确可以通过合适的方法构造出一个图) 根据定理14.2的推论,度数为奇数的顶点数为偶数,因此设度数为奇数的顶点 数为2k,在d中对应d1d2…dk,d,dk+2…,d2,则可以通过如下方法构造以d为 度数列的n阶无向图G=<V,E>:V=(v1,w2,…,vn)。 [步骤1]首先选择2k个顶点,v1,V2,…,v,Vk+1,vk2, 在v,和 Vr+k之间连边,r=1,2,…,k。则v1,…V2中顶点度和为2k [步骤2]考察整个度数列中的各个度数d,并重新构造一个度数列d’。若d1为 偶数则令d;’=d;,若d为奇数,则令d1’=d1-1。与原有度数列d相比,新 构造的度数列d’在图的顶点度数和恰好少了2k,且为偶数。 [步骤3]由于d’中的所有元素均为偶数,对于所有的节点画d1’/2条环,则整 个图中顶点度数恰为与原度数列d的度数之和相等。 东南大学计算机科学与工程学院 同的出学 图论
定理14.3 非负整数列d=(d1 ,d2 ,…,dn)是可图化的当且仅当 = n i di 1 为偶数。 由定理14.1可知，度数之和必为偶数，必要性得证。 定理的充分性采用构造法证明（的确可以通过合适的方法构造出一个图） 根据定理14.2的推论，度数为奇数的顶点数为偶数，因此设度数为奇数的顶点 数为2k，在d中对应d1 ,d2 ,…,dk，dk+1,dk+2,…,d2k，则可以通过如下方法构造以d为 度数列的n阶无向图G=<V,E>：V=(v1, v2, …, vn)。 [步骤2]考察整个度数列中的各个度数di，并重新构造一个度数列d’。若di为 偶数则令di’= di ，若di为奇数，则令di’= di -1。与原有度数列d相比，新 构造的度数列d’在图的顶点度数和恰好少了2k，且为偶数。 [步骤3]由于d’中的所有元素均为偶数，对于所有的节点画di’/2条环，则整 个图中顶点度数恰为与原度数列d的度数之和相等。 [步骤1]首先选择2k个顶点， v1, v2, …, vk， vk+1, vk+2, …, v2k。在vr和 vr+k之间连边，r=1，2，…,k。则v1,…v2k中顶点度和为2k
例子 d=(4,4,2,1,3) d=(4,4,2,0,2) V=(v1,V2,v3,v4,Vs5) 东南大学计算机科学与工程学院 同的出学 图论
可简单图化的判定 定理144设G为任意n阶无向简单图,则△(G)sn1 无向图G中对于任意顶点与其它n-1个顶点之间最多存在一条边,否则将出现平行 边。而顶点自身不存在环。因此最大度为n-1。 度数列可简单图化的必要条件 度数列中元素之和为偶数 度数列中每一个元素均不大于n-1,其中n为度数列阶数 d=(3,3,3,1)可以被简单图化么? 斗一条 [步骤1从大到小依次删除度数列中的元素,并均匀降低剩余各项度数 [步骤2]检查剩余度数列是否满足可简单图化必要条件; 东南大学计算机科学与工程学院 同的出学 图论
定理 设G为任意n阶无向简单图，则△(G) ≤n-1 14.4 无向图G中对于任意顶点与其它n-1个顶点之间最多存在一条边，否则将出现平行 边。而顶点自身不存在环。因此最大度为n-1。 度数列可简单图化的必要条件 度数列中元素之和为偶数； 度数列中每一个元素均不大于n-1，其中n为度数列阶数 d=(3 , 3 , 3 , 1)可以被简单图化么？ 尝试一下 [步骤1]从大到小依次删除度数列中的元素，并均匀降低剩余各项度数； [步骤2]检查剩余度数列是否满足可简单图化必要条件；
图的同构 定义15设G:=M,E和G2=<V,E>是两个无向图(两个有向图),若 存在双射函数f:V1→V2,使得对M,v∈V1,(,v∈E当且仅 当(f(4),1)∈E2有向图中<v,y∈E当且仅当<f(),y少>∈ E2),并且,和(v),f()有向图中v,v和<f(v),f0y)>)有 相同的重数,则称G和G2同构。 图的同构的判定方法 (1)G′和G是同构的,它们的顶点必须是—对应的; 2)且对无向图而言,还要保持顶点之间的邻接关系和边的重数; 3)且对有向图而言,不但要保持顶点之间的邻接关系,而且还应 保持边的方向和边的重数 839-9IU 东南大学计算机科学与工程学院 同的出学 图论
定义14.5 设G1=<V1 , E1>和Ｇ2＝<V2 , E2>是两个无向图（两个有向图），若 存在双射函数f： V1 → V2 ，使得对 vi , vj∈V1，(vi , vj )∈ E1当且仅 当(f(vi ) , f(vj ))∈ E2 (有向图中<vi , vj>∈ E1当且仅当<f(vi ) , f(vj )>∈ E2 ) ，并且(vi , vj )和(f(vi ) , f(vj ))(有向图中<vi , vj>和<f(vi ) , f(vj )>)有 相同的重数，则称G1和Ｇ2同构。 Julius Petersen 1839-1910 （1）Ｇ’和Ｇ是同构的,它们的顶点必须是一一对应的； （2）且对无向图而言，还要保持顶点之间的邻接关系和边的重数； （3）且对有向图而言，不但要保持顶点之间的邻接关系，而且还应 保持边的方向和边的重数