的度数举例 e d(v1)=4(注意,环提供2度) 6△=4,8=1, v4是悬挂顶点,7是悬挂边。 dr(a)=4,d(m)=1 a)2b(环1提供出度1,提供入度1), d(a)=4+1=5。△=5,=3, △+=4(在a点达到) 6+=0(在b点达到) dC△-=3(在b点达到) 6-=1(在a和c点达到)
图的度数举例 d(v1 )＝4(注意，环提供2度)， △＝4，δ＝1， v4是悬挂顶点，e7是悬挂边。 d +(a)＝4，d -(a)＝1 (环e1提供出度1，提供入度1)， d(a)＝4+1＝5。△＝5，δ＝3， △+＝4 (在a点达到) δ+＝0(在b点达到) △-＝3(在b点达到) δ-＝1(在a和c点达到)
握手定理 定理14.1设G=V,E>为任意无向图,V={1,2…,vn}, E|=m,则 ∑d(V)=2m 说明任何无向图中,各顶点度数之和等于边数的两倍。 证明G中每条边(包括环)均有两个端点, 所以在计算G中各顶点度数之和时, 每条边均提供2度,当然,m条边,共提供2m度。 定理14.2设D=<V,E>为任意有向图,V={v1,v2,…,vn E|=m,则 ∑d()=2m且∑a(v)=∑d(v,)=m
握手定理 定理14.1 设G＝<V,E>为任意无向图，V＝{v1 ,v2 ,…,vn }， |E|＝m，则 = = n 1 ( ) 2 i d vi m 说明 任何无向图中，各顶点度数之和等于边数的两倍。 证明 G中每条边(包括环)均有两个端点， 所以在计算G中各顶点度数之和时， 每条边均提供2度，当然，m条边，共提供2m度。 定理14.2 设D＝<V,E>为任意有向图，V＝{v1 ,v2 ,…,vn }， |E|＝m，则 = = + − = = = = n n n 1 1 1 ( ) 2 , ( ) ( ) i i i i i d vi m 且 d v d v m
握手定理的推论 推论任何图(无向的或有向的)中,奇度顶点的个数是偶数。 证明设G=<V,E>为任意一图,令 V1={lv∈VAd()为奇数 V2={vlv∈v∧d(m)为偶数 则v∪V2=V,V1nV2=⑦,由握手定理可知 2m= ∑4(1)=∑4()+∑() v∈p v∈ v∈V2 由于2mz和∑d(),所以∑4(v)为偶数, v∈ v∈ 但因V中顶点度数为奇数,所以|V1必为偶数
握手定理的推论 推论 任何图(无向的或有向的)中，奇度顶点的个数是偶数。 证明 设G＝<V，E>为任意一图，令 V1 ＝{v|v∈V∧d(v)为奇数} V2 ＝{v|v∈V∧d(v)为偶数} 则V1∪V2 ＝V，V1∩V2 ＝ ，由握手定理可知 = v V 2m d(v) = + 1 2 ( ) ( ) v V v V d v d v 由于2m和 2 ( ) v V d v ，所以 1 ( ) v V d v 为偶数， 但因V1中顶点度数为奇数， 所以|V1|必为偶数
问题研究 问题:在一个部门的25个人中间,由于意见不同,是否可能每 个人恰好与其他5个人意见一致? 解答:不可能。考虑一个图,其中顶点代表人,如果两个人意见 相同,可用边连接,所以每个顶点都是奇数度。存在奇数个 度数为奇数的图,这是不可能的。 说明: (1)很多离散问题可以用图模型求解。 (2)为了建立一个图模型,需要决定顶点和边分别代表什么。 (3)在一个图模型中,边经常代表两个顶点之间的关系
问题研究 问题：在一个部门的25个人中间，由于意见不同，是否可能每 个人恰好与其他5个人意见一致？ 解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见 相同，可用边连接，所以每个顶点都是奇数度。存在奇数个 度数为奇数的图，这是不可能的。 说明： (1)很多离散问题可以用图模型求解。 (2)为了建立一个图模型，需要决定顶点和边分别代表什么。 (3)在一个图模型中，边经常代表两个顶点之间的关系
度数列 设G=<V,E>为一个m阶无向图,V={v1,v2,…,v},称d(v1), d(v2),…,d(v)为G的度数列。 对于顶点标定的无向图,它的度数列是唯一的。 反之,对于给定的非负整数列d={d1,a2,…,an},若存在V v1,V2…,vn}为顶点集的n阶无向图G,使得(v)=l,则称d 是可图化的。 特别地,若所得图是简单图,则称l是可简单图化的 d(v1),a(v2),…,d()为D的度数列,另外称r(v1·称 类似地,设D=<,E为一个n阶有向图,V={vn,v2,…,vn} dr(v2),灬,a(vn)与d(v1),d(2),…,d(vn)分别为D的出 度列和入度列
度数列 设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是可简单图化的。 类似地，设D＝<V,E>为一个n阶有向图，V＝{v1 ,v2 ,…,vn}，称 d(v1 )，d(v2 )，…，d(vn )为D的度数列，另外称d +(v1 )， d +(v2 )，…，d +(vn)与d -(v1 )，d -(v2 )，…，d -(vn)分别为D的出 度列和入度列