圖的基本概念ppt課件(編輯修改稿)
2025-06-02 23:18 本頁面
【文章內(nèi)容簡介】 b? a? c? a? ?b ?d 上圖中 Δ(G)=5 δ(G)=2 4. 定理 每個無向圖所有結(jié)點(diǎn)度總和等于邊數(shù)的 2倍 . 即 證明 :因?yàn)閳D中每條邊關(guān)聯(lián)兩個結(jié)點(diǎn) ,因此每條邊給予它所 關(guān)聯(lián)的兩個結(jié)點(diǎn)的度各是 1, 即一條邊對應(yīng)的度數(shù)是 2, 所 以整個圖的度數(shù)總和為邊數(shù)的 2倍 . 定理 (握手定理 )每個無向圖中 ,奇數(shù)度的結(jié)點(diǎn)必為偶 數(shù)個 .(一次集會中 ,與奇數(shù)個人握手的人 ,必是偶數(shù)個 .) 證明 :令 G=V,E是無向圖 ,將 V分成兩個子集 V1 和 V2, 其中 V1 是度數(shù)是奇數(shù)的結(jié)點(diǎn)集合 , V2 是度數(shù)是偶數(shù)的結(jié)點(diǎn)集合 而 是偶數(shù) . 所以 也是偶數(shù) , 于是奇數(shù)度的結(jié)點(diǎn)數(shù)是偶數(shù) . ∑deg(v)=2|E| v∈ V ∑deg(v) + ∑deg(v) =2|E| v∈ V1 v∈ V2 ∑deg(v) v∈ V2 ∑deg(v) v∈ V1 六 . k正則圖 :一個無向簡單圖 G中 ,如果 Δ(G)=δ(G)=k 則稱 G為 k正則圖 . 課堂練習(xí) : ,可能是一個圖的度數(shù)序列 ? 如果可能 ,請試畫出它的圖 . 哪些可能不是簡單圖 ? a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) G中 ,有 10條邊 ,4個 3度結(jié)點(diǎn) ,其余結(jié)點(diǎn)的 度均小于或等于 2,問 G中至少有多少個結(jié)點(diǎn) ?為什么 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1. a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) 解 :a)不是 , 因?yàn)橛腥齻€數(shù)字是奇數(shù) . b) 是 . c) 可能 不是簡單圖 ,如圖： :已知邊數(shù) |E|=10, ∑deg(v)=2|E|=20 其中有 4個 3度結(jié)點(diǎn) , 余下結(jié)點(diǎn)度之和為 : 203 4=8 因?yàn)?G是簡單圖 , 其余每個結(jié)點(diǎn)度數(shù) ≤2, 所以至少還有 4個結(jié)點(diǎn) . 所以 G中至少有 8個結(jié)點(diǎn) .同時， 8個結(jié)點(diǎn)也是 足夠的。例如“目”的圖形就是滿足條件的例子。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 七 . 有向圖結(jié)點(diǎn)的出度和入度 :(in degree out degree) G=V,E是有向圖 ,v∈ V v的出度 : 從結(jié)點(diǎn) v射出的邊數(shù) . 記作 deg+(v) 或 dego(v) v的入度 : 射
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1