图的度数 定义: 设G=<VE>为一无向图,Vv∈V,称V作为边的端点次数之和为v 的度数,简称为度,记做d(v),在不发生混淆时,简记为d(v) 设D=<V,E>为有向图,v∈V,称v作为边的始点次数之和为v的 出度记做dv),简记作d(v);称v作为边的终点次数之和为v的 入度,记做dpv),简记作d(v;称d(v)+d)为v的度数,记做
11 图的度数 定义: ¾ 设G = <V, E>为一无向图, ∀v∈V, 称v作为边的端点次数之和为v 的度数, 简称为度, 记做 dG(v), 在不发生混淆时, 简记为d(v)； ¾ 设D = <V, E>为有向图, ∀v∈V, 称v作为边的始点次数之和为v的 出度,记做d+D(v), 简记作d+(v)；称v作为边的终点次数之和为v的 入度, 记做d-D(v), 简记作d-(v)；称d+(v)+d-(v)为v的度数, 记做 d(v)
图的度数 定义: 设G=<V,E>为一无向图,令△(G)=max{d(y)v∈v(G)},8(G)= min{d(y)v∈(G)},称△(G,8(G)分别为G的最大度和最小度 设D=<V,E>为有向图,在有向图D中,类似可定义最大度△G)和 最小度δ(G)另外,令△(G)=max{d(v)v∈VG}, δ(G)=min{dt(v)veⅤ(G)},△(G)=max{d(v)vev(G},6 (G)=min{d(v)v∈V(G)},分别称为D的最大出度,最小出度,最大 入度,最小入度 当不会引起混淆时,以上记号可分别简记为△,8,△t,δ+,△,δ 此外,称度数为1的顶点为悬挂顶点,与它关联的边称为悬挂边 度数为偶数(奇数)的顶点称为偶度(奇度)项点 12
12 图的度数 定义: ¾ 设G = <V, E>为一无向图, 令Δ(G)=max{d(v)|v∈V(G)}, δ(G) = min{d(v)|v∈V(G)}, 称Δ(G), δ(G)分别为G的最大度和最小度. ¾ 设D = <V, E>为有向图, 在有向图D中, 类似可定义最大度Δ(G)和 最小度δ(G). 另外, 令Δ+(G)=max{d+(v)|v∈V(G)}, δ+(G)=min{d+(v)|v∈V(G)}, Δ-(G)=max{d-(v)|v∈V(G)}, δ- (G)=min{d-(v)|v∈V(G)}, 分别称为D的最大出度, 最小出度, 最大 入度,最小入度. ¾ 当不会引起混淆时, 以上记号可分别简记为Δ, δ, Δ+, δ+, Δ-, δ-. ¾ 此外，称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边. 度数为偶数(奇数)的顶点称为偶度(奇度)顶点
握手定理 定理:设G=<V,E>为任意无向图,V={v1V23…,Vn},|E=m, 则Σ=1nd(v)=2 证明:G中每条边(包括环)均有两个端点,在计算G中各顶点度数 之和时,每条边均提供2度,所以,m条边共提供2m度 定理:设D=<V,E>为任意有向图,v={v1V2…,Vn],|旧E=m, 则Σ=1nd(v)=2m,E=1nd(w)=E=1.nd(v) 该定理的证明与上面的定理类似
13 握手定理 定理: 设G = <V, E>为任意无向图, V = { v1, v2, …, vn }, |E| = m, 则Σi=1..nd(vi) = 2m。 证明: G中每条边(包括环)均有两个端点, 在计算G中各顶点度数 之和时, 每条边均提供2度, 所以, m条边共提供2m度。 定理: 设D = <V, E>为任意有向图, V = { v1, v2, …, vn }, |E| = m, 则Σi=1..nd(vi) = 2m, Σi=1..nd+(vi) = Σi=1..nd-(vi) = m 该定理的证明与上面的定理类似
握手定理 握手定理的推论: 任何图(无向的或有向的)中,奇度顶点的个数是偶数。 证明:设G=<V,E>为任意图,令 1={v|v∈Vd(v)为奇数}V2={v|veV,d(v)为偶数} 则Ⅴ1UV2=V,v1∩v2=φ。 由握手定理可知: 2m= Zveyd(v)= Evey, d(v)+ Evev d(v) 由“2m和Σev2,d)均为偶数”可知Ev,d(v)也为偶数 因为V1中各顶点的度数都为奇数,所以Ⅳ必为偶数 14
14 握手定理 握手定理的推论: 任何图(无向的或有向的)中, 奇度顶点的个数是偶数。 证明: 设G = <V, E>为任意图, 令 V1 = { v | v∈V, d(v)为奇数 }, V2 = { v | v∈V, d(v)为偶数 } 则 V1∪V2 = V, V1∩V2 = φ。 由握手定理可知: 2m = Σv∈Vd(v) = Σv∈V1d(v) + Σv∈V2d(v) 由“2m和Σv∈V2d(v)均为偶数”可知 Σv∈V1d(v)也为偶数。 因为V1中各顶点的度数都为奇数, 所以 |V1|必为偶数
度数列 设G=<V,E>为一个n阶无向图,V={V1,V2,…,Vn},称d(v dv2),……,d(vn)为G的度数列.对于顶点标定的无向图,它的度数列 是唯一的 设D=<V,E>为一个n阶有向图,v={v1V2,…vn},称d(v) dN2),……,d(vn)为D的度数列,称d(vd(v2),…,d(vn)与d(v1 d(v2)…,d(vn)分别为D的出度列和入度列 15
15 度数列 设G = <V, E>为一个n阶无向图, V = { v1, v2, …, vn }, 称d(v1), d(v2), …, d(vn)为G的度数列. 对于顶点标定的无向图, 它的度数列 是唯一的。 设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的出度列和入度列