圖的基本概念ppt課件(參考版)
2025-05-09 23:18本頁面
【正文】 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 七 . 有向圖結(jié)點的出度和入度 :(in degree out degree) G=V,E是有向圖 ,v∈ V v的出度 : 從結(jié)點 v射出的邊數(shù) . 記作 deg+(v) 或 dego(v) v的入度 : 射入結(jié)點 v的邊數(shù) . 記作 deg(v) 或 degi(v) degi(a)=2 degi(b)=2 degi(c)=1 degi(d)=1 dego(a)=2 dego(b)=3 dego(c)=1 dego(d)=0 定理 G=V,E是有向圖 , 則 G的所有結(jié)點的出度之和 等于入度之和 . 證明 : 因為圖中每條邊對應(yīng)一個出度和一個入度 . 所以所 有結(jié)點的出度之和與所有結(jié)點的入度之和都等于有向邊 數(shù) . 必然有所有結(jié)點的出度之和等于入度之和 . a? ?b c? ?d 八 . 完全圖 定義 :G是個簡單圖 , 如果每對不同結(jié)點之間都有邊相連 則稱 G是個無向完全圖 . 如果 G有 n個結(jié)點 , 則記作 Kn. 定理 無向完全圖 Kn, 有邊數(shù) 證明 : 因為 Kn中每個結(jié)點都與其余 n1個結(jié)點關(guān)聯(lián) , 即每 個結(jié)點的度均為 n1, 所以 Kn的所有結(jié)點度數(shù)總和為 n(n1), 設(shè)邊數(shù)為 |E|, 于是 n(n1)=2|E| 所以 |E|= ? ? ? ? ? ? ? ? ? ? ? ? ? ? K2 K3 K4 K5 )1(21 ?nn)1(21 ?nn2. 有向圖的完全圖 (注 :這里的定義與教材不同 ) 1).有向簡單完全圖 :G是個 有向簡單圖 ,如果任何兩個 不同 結(jié)點之間都有相互可達的邊 ,則稱它是有向簡單完全圖 . 例如 : 定理 : 有 n個結(jié)點的 有向簡單完全圖有邊數(shù)為 n(n1). 證明 : 顯然它的邊數(shù)是 Kn邊數(shù)的 2倍 .所以是 n(n1). 2).有向完全圖 (有向全圖 ) (它與完全關(guān)系圖一致 ) G是個有向圖如果任何兩個結(jié)點之間都有相互可達的邊 ,則稱它是有向完全圖 . 其圖形如下 : ? ? ? ? ? ? ? ? ? 所以有 n個結(jié)點的有向完全圖 , 有邊數(shù) n2. 九 .子圖和生成子圖 :設(shè) G=V,E是圖 ,如果 G’=V’,E’且 V’?V, V’≠Φ, E’?E, 則稱 G’是 G的子圖 . 可見 G1,G2,G3都是 K5的子圖 . ? ? ? ? ? ? ? ? ? b? ?c d? ?e ?a b? ?c ?a b? ?c d? ?e G1 G2 G3 K5 ?a b? ?c d? ?e 2. 生成子圖 設(shè) G=V,E是圖 , G’
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1