圖論初步講義-在線瀏覽
2024-11-03 19:05本頁面
【正文】 of PKU 10 問題： ? 具有 n 個頂點的連通圖，最少應(yīng)有多少條邊？最多呢？ Houfeng Wang, ICL of PKU 11 子圖： subgraph 設(shè)有兩個圖 G=（ V， E）、 G1=（ V1， E1），若 V1? V，E1 ? E， E1關(guān)聯(lián)的頂點都在 V1中，則稱 G1是 G的子圖； 例：圖 圖 3 都是 圖 1 的子圖 V5 V1 V2 V4 V3 圖 1 V5 V1 V2 V3 圖 2 V5 V1 V2 V4 V3 圖 3 Houfeng Wang, ICL of PKU 12 連通分量 Connected Component 無向圖 G的極大連通子圖稱為 G的連通分量 極大連通子圖意思是：是 G子圖，且連通，將 G的任何不在該子圖中的頂點（或邊，或兩者）加入，子圖不再連通； V3 V1 V2 V4 V5 V6 V5 V6 V3 V1 V2 V4 連通分量 Houfeng Wang, ICL of PKU 13 問題 ? 一個連通圖有多少個連通分量？ Why 2 3 8 10 1 4 5 9 11 6 7 Just One: Original graph Houfeng Wang, ICL of PKU 14 強連通分量 有向圖 D的極大強連通子圖稱為 D的強連通分量 極大強連通子圖意思是：該子圖是 D強連通子圖，將D的任何不在該子圖中的頂點加入，子圖不再是強連通的； Houfeng Wang, ICL of PKU 15 圖的存儲表示 ? 回憶線性表，樹型結(jié)構(gòu)的表示，必須刻畫： – 節(jié)點信息 – 節(jié)點之間的關(guān)系（一對一，一對多，多對多） ? 如何表示圖的節(jié)點和節(jié)點之間的關(guān)系？ Houfeng Wang, ICL of PKU 16 （ 1）圖的鄰接矩陣表示法 （ 2）圖的鄰接表示法 圖的存儲結(jié)構(gòu) Houfeng Wang, ICL of PKU 17 V1 V3 V2 V4 V1 V2 V3 V4 V1 0 0 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0 V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0 圖的鄰接矩陣表示法 V1 V3 V2 V4 A[i][j]= 1 若 (vi,vi+1)?E 或 vi,vi+1?E 0 否則 Houfeng Wang, ICL of PKU 18 鄰接矩陣表示法對求頂點的度很方便。 在有向圖中： 頂點的出度 =矩陣中對應(yīng)該頂點的 行 中非零元素的個數(shù)。 Houfeng Wang, ICL of PKU 19 特點 ? 無向圖的鄰接矩陣一定是一對稱矩陣， 同一條邊表示了兩次。 ? 容易計算度。 Houfeng Wang, ICL of PKU 20 V1 V3 V2 V4 V1 V3 V2 V4 V1 V2 V3 V4 V1 0 0 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0 V1 V2 V3 V4 V1 0 1 1 1 V2 1 0
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1