在无向图G中令 △G)=max{d(v)v∈(G)}; S(G)=mindvlvEv(G) 称△(G)和8(G)分别为G的最大度和最小度 在有向图D中可类似定义(D)、8(G)。另外令 △+(G)=max{d(v)v∈(D)} δ+(G)=min{dt(v)v∈Ⅴ(D)} △(G)=max{d(v川v∈v(D)} 8(G)=mind( vEv) 分别为D的最大出度、最小出度、最大入度、最 小入度。简记作公、δ、A+、δ+、△-、δ
在无向图G中,令 △(G)=max{d(v)|v∈V(G)}; (G) = min{d(v)| v∈V(G) } 称 △(G)和 (G)分别为G的最大度和最小度。 在有向图D中,可类似定义△(D)、(G)。另外,令 △+ (G) = max{d+ (v)| v∈V(D) } + (G) = min{d+ (v)| v∈V(D) } △- (G) = max{d- (v)| v∈V(D) } - (G) = min{d- (v)| v∈V(D) } 分别为D的最大出度、最小出度、最大入度、最 小入度。简记作△、、 △+ 、 + 、 △- 、 -
5 N5 eA 5e 5 6 (2) 例在上图(1)中,最大度4=6,最小度8=0, 在图(2)中,最大度4=4,最小度8=2, 最大出度4+=4,最大入度△=3 最小出度δ+=1,最小入度8=0
v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 (1) v1 v2 v3 v4 v5 e e1 2 e3 e4 e5 e6 e7 e8 (2) 例 在上图(1)中,最大度△=6, 最小度=0, 在图(2)中,最大度△= 4, 最小度=2, 最大出度△+ = 4,最大入度△- = 3 最小出度 + = 1,最小入度 - = 0
握手定理 设G二三<V,E>为无向图或有向图, 9●●● ,n,E|=m(m为边数)则 ∑deg()=2nm。即个顶南度数之和等手 v∈ 边数的2倍。 证明:G中每条边(包括环)均提供2个端点,故 在计算各顶点度数的和时,每条边均提供2度,m 条边共提供2m度。 推论在任何图G=<VE中,度数为奇数的结点 为偶数个
握手定理 设G=<V,E>为无向图或有向图， V={v1 ,v2 ,…,vn },|E|= m ( m为边数) 则 证明：G中每条边（包括环）均提供2个端点，故 在计算各顶点度数的和时，每条边均提供2度，m 条边共提供2m度。 =2m。 即每个顶点度数之和等于 边数的2倍。 vV deg(v) 推论 在任何图G=V,E中，度数为奇数的结点 必为偶数个
设G=<VE>是有向图,v∈,射入(出)结 点v的边数称为结点的入(出)度。记为deg(v) (deg+(v)显然,任何结点的入度与出度的和 等于该结点的度数,即deg(吵)=deg-(v)+deg 定理:在有向图中,所有结点入度的和等于所 有结点出度的和。 证明:在有向图中每一条边对应一个入度 和一个出度,为图的入度和出度各增加1。所 以,所有结点入度的和等于边数,所有结点出 度的和也等于边数
设G=V,E是有向图，vV，射入(出)结 点v的边数称为结点v的入(出)度。记为deg－(v) (deg＋(v))。显然，任何结点的入度与出度的和 等于该结点的度数，即deg(v)=deg－(v)+deg＋ (v)。 定理：在有向图中，所有结点入度的和等于所 有结点出度的和。 证明：在有向图中每一条边对应一个入度 和一个出度，为图的入度和出度各增加1。所 以，所有结点入度的和等于边数，所有结点出 度的和也等于边数
设Ⅴ={v122,n}为图的顶点集,称 (d(v1),d(v2),,d(vn)为G的度数序列。 例:在下图中的度数序列为(4,43,1,0)
设V={v1 ,v2 ,…,vn }为图的顶点集，称 ( d(v1 ),d(v2 ), …d(vn ))为G的度数序列。 例： 在下图中的度数序列为（4,4,3,1,0 )。 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6