最大(出/入)度,最小(出/入)度 最大度:△(G)= max dG()|veVG)} 最小度:8(G)=min(de)VeV(G)} 最大出度:△(D)= max d()|veV(D) 鲁最小出度:8(D)= minl d()|vevD) 最大入度:△(D)=max{d()|vEVD} 鲁最小入度:8(0)= min dp()veV(D)} 简记为△,8,A+,δ,△,δ 《集合论与图论》第14讲
《集合论与图论》第14讲 11 最大(出/入)度,最小(出/入)度 最大度: Δ(G) = max{ dG(v) | v∈V(G) } 最小度: δ(G) = min{ dG(v) | v∈V(G) } 最大出度: Δ+(D) = max{ dD+(v) | v∈V(D) } 最小出度: δ+(D) = min{ dD+(v) | v∈V(D) } 最大入度: Δ-(D) = max{ dD-(v) | v∈V(D) } 最小入度: δ-(D) = min{ dD-(v) | v∈V(D) } 简记为 Δ, δ, Δ+, δ+, Δ-, δ-
握手定理(图论基本定理) 定理1:设G=<V,E>是无向图, ∨=1V2,dE|=m,则 d(1)+d(2)+…1+d(vn)=2m.# 秦定理2设D=<V,E>是有向图, ∨={1V2…,Vd旧E=m,则 d(v1)+dV2)+…d(v) dt()+d(w2)+…td(n)=m.# 婚推论:任何图中奇数度顶点的个数是偶数 # 《集合论与图论》第14讲
《集合论与图论》第14讲 12 握手定理(图论基本定理) 定理1:设G=<V,E>是无向图, V={v1,v2,…,vn}, |E|=m, 则 d(v1)+d(v2)+…+d(vn)=2m. # 定理2:设D=<V,E>是有向图, V={v1,v2,…,vn}, |E|=m, 则 d+(v1)+d+(v2)+…+d+(vn) = d-(v1)+d-(v2) +…+d-(vn) = m. # 推论:任何图中,奇数度顶点的个数是偶数. #
简单图( simple graph),正则图 简单图( simple graph):无环,无平行边 若G是简单图,则0≤△(G)≤n-1 馨k正则图( egular graph):v,d()=k 《集合论与图论》第14讲 13
《集合论与图论》第14讲 13 简单图(simple graph),正则图 简单图(simple graph): 无环,无平行边 若G是简单图, 则 0 ≤ Δ(G) ≤ n-1 k-正则图(regular graph): ∀v, d(v)≡k
度数列 度数列:设G=<V,E,={1,2…,n}称 d=(dv,dV),…,d(vn) 为G的度数列 静例:d=(5,1,2,3,3) 《集合论与图论》第14讲
《集合论与图论》第14讲 14 度数列 度数列: 设G=<V,E>,V={v1,v2,…,vn}, 称 d = ( d(v1),d(v2),…, d(vn) ) 为G的度数列 例: d = ( 5, 1, 2, 3, 3 ) v2 v3 v4 v5 v1
可图化,可简单图化 可图化设非负整数列d=(d1,d2,…,dn), 若存在图G,使得G的度数列是d,则称d 为可图化的 可简单图化:设非负整数列d=(0,2, dn),若存在简单图G,使得G的度数列是d, 则称d为可简单图化的 静例:d=(5,3,3,2,1) 《集合论与图论》第14讲 15
《集合论与图论》第14讲 15 可图化,可简单图化 可图化:设非负整数列d=( d1,d2, …, dn ), 若存在图G, 使得G的度数列是d, 则称d 为可图化的 可简单图化:设非负整数列d=( d1, d2, …, dn ), 若存在简单图G, 使得G的度数列是d, 则称d为可简单图化的 例: d = ( 5, 3, 3, 2, 1 )