第8章图的基本概念 图G的最大度4(G)=max{d(v)h∈v(G)} 图G的最小度δ(G)=min{d(ν)|∈v(G)} 有向图G的最大出度4(G)=max{d(v)h∈V(G)} 有向图G的最小出度+(G)=mim{d(v)∈V(G)} 有向图G的最大入度4(G)=mx{d(v)∈V(G)} 有向图G的最小入度(G)=min{a(v)∈V(G) k正则图每个顶点的度数均是k的无向图。 另外,我们称度数为1的顶点为悬挂点,称与悬挂 点关联的边为悬挂边
第8章 图的基本概念 图G的最大度 Δ(G）=max{d（v）|v∈V（G)} 图G的最小度 δ（G）=min{d（v）|v∈V（G）} 有向图G的最大出度 Δ +（G）=max{d +（v）|v∈V（G）} 有向图G的最小出度 δ +（G）=min{d +（v）|v∈V（G）} 有向图G的最大入度 Δ -（G）=max{d -（v）|v∈V（G）} 有向图G的最小入度 δ -（G）=min{d -（v）|v∈V（G）} k-正则图 每个顶点的度数均是k的无向图。 另外，我们称度数为1的顶点为悬挂点，称与悬挂 点关联的边为悬挂边
第8章图的基本概念 定理8.1.1(握手定理)任一图中,顶点的度数的 总和等于边数的二倍,即 ∑d(U)=2|E vEV 证明因为在任一图中,每一条边均关联着两个顶点 (或二点重合),所以在计算度数时要计算两次,故顶 点的度数的总和等于边数的二倍
第8章 图的基本概念 定理8.1.1（握手定理） 任一图中，顶点的度数的 总和等于边数的二倍，即 ( ) 2 V d E = 证明 因为在任一图中，每一条边均关联着两个顶点 （或二点重合），所以在计算度数时要计算两次，故顶 点的度数的总和等于边数的二倍
第8章图的基本概念 推论任一图中,奇度数顶点必有偶数个。 证明设V1={vd(v)为奇数},V2=VV1,则 ∑d(U)+∑d()=∑d(U)=2m EV1 U∈V U∈ 因为∑d()是偶数,∑d()也是偶数,所以∑d() U∈V D 必是偶数。而d(ν)为奇数,故V是偶数
第8章 图的基本概念 推论 任一图中，奇度数顶点必有偶数个。 证明 设V1={v|d（v）为奇数}，V2 =V-V1，则 1 2 ( ) ( ) ( ) 2 V V V d d d m + = = 因为 2 ( ) V d 是偶数， ( ) V d 也是偶数， 1 ( ) V d 所以 必是偶数。而d（v）为奇数，故|V1 |是偶数
第8章图的基本概念 定理8.1.2若G=〈VE〉是有向图,则 ∑d(U)=∑d(U) ∈ U∈ 证明请读者自己完成
第8章 图的基本概念 定理8.1.2 若G=〈V,E〉是有向图，则 ( ) ( ) V V d d m + − = = 证明请读者自己完成
第8章图的基本概念 假设{v1,v2,…,v}是m阶图G的顶点集,称a (v1),d(nv2),…,d(vn)为G的度数列。如例8.1.2 中图8.1.1(a)的度数列为2,2,2,3,3。例8.1.,2中图 8.1.1(c)的度数列为1,2,2,3,3,其中出度数列为0, 2,0,2,1,入度数列为1,0,2,1,2
第8章 图的基本概念 假设V={v1，v2，…，vn}是n阶图G的顶点集，称d （v1），d（v2），…，d（vn）为G的度数列。如例8.1.2 中图8.１.1（a）的度数列为2，2，2，3，3。例8.1.2中图 8.1.1（c）的度数列为1，2，2，3，3，其中出度数列为0， 2，0，2，1，入度数列为1，0，2，1，2