圖論初步講義-wenkub
2022-09-11 19:05:43 本頁面
【正文】 ICL of PKU 10 問題： ? 具有 n 個(gè)頂點(diǎn)的連通圖，最少應(yīng)有多少條邊？最多呢？ Houfeng Wang, ICL of PKU 11 子圖： subgraph 設(shè)有兩個(gè)圖 G=（ V， E）、 G1=（ V1， E1），若 V1? V，E1 ? E， E1關(guān)聯(lián)的頂點(diǎ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的任何不在該子圖中的頂點(diǎn)（或邊，或兩者）加入，子圖不再連通； V3 V1 V2 V4 V5 V6 V5 V6 V3 V1 V2 V4 連通分量 Houfeng Wang, ICL of PKU 13 問題 ? 一個(gè)連通圖有多少個(gè)連通分量？ Why 2 3 8 10 1 4 5 9 11 6 7 Just One: Original graph Houfeng Wang, ICL of PKU 14 強(qiáng)連通分量 有向圖 D的極大強(qiáng)連通子圖稱為 D的強(qiáng)連通分量 極大強(qiáng)連通子圖意思是：該子圖是 D強(qiáng)連通子圖，將D的任何不在該子圖中的頂點(diǎn)加入，子圖不再是強(qiáng)連通的； Houfeng Wang, ICL of PKU 15 圖的存儲(chǔ)表示 ? 回憶線性表，樹型結(jié)構(gòu)的表示，必須刻畫： – 節(jié)點(diǎn)信息 – 節(jié)點(diǎn)之間的關(guān)系（一對一，一對多，多對多） ? 如何表示圖的節(jié)點(diǎn)和節(jié)點(diǎn)之間的關(guān)系？ Houfeng Wang, ICL of PKU 16 （ 1）圖的鄰接矩陣表示法 （ 2）圖的鄰接表示法 圖的存儲(chǔ)結(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 鄰接矩陣表示法對求頂點(diǎn)的度很方便。 頂點(diǎn)的度：依附于該頂點(diǎn)的邊數(shù)或弧數(shù)。 V1 V3 V2 V4 V1 V3 V2 V4 Houfeng Wang, ICL of PKU 4 V1 V3 V2 V4 V1 V3 V2 V4 頂點(diǎn)集合 V={V1 ， V2 ， V3 ， V4 } 邊的集合 E={V1 ， V3, V3 ， V4, V2 ， V4, V4， V1} 如何表示： G=( V, E ) 頂點(diǎn)集合 V={V1 ， V2 ， V3 ， V4 } 邊的集合 E={(V1, V3), (V1, V2), (V1, V4),(V2, V4)} (V1, V3)與 (V3, V1)表示同一條邊 區(qū)別 ？？？？ Houfeng Wang, ICL of PKU 5 圖相關(guān)的實(shí)際例子 例 1 交通
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1