圖論初步講義-展示頁
2024-09-12 19:05本頁面
【正文】 中對應該頂點的行 或 列中非零元素的個數(shù)。 無向圖中的頂點序列 v1,v2,… ,vk,若 (vi,vi+1)?E( i=1,2,… k1), v =v1, u =vk, 則稱該序列是從頂點 v到頂點u的路徑；若 v=u，則稱該序列為回路； 有向圖中的頂點序列 v1,v2,… ,vk, 若 vi,vi+1?E ( i=1,2,… k1), v =v1, u =vk, 則稱該序列是從頂點 v到頂點u的路徑；若 v=u，則稱該序列為回路； 路徑上邊或弧的數(shù)目稱為該路徑的路徑長度 。 出度：（僅對有向圖）以該頂點為尾的弧數(shù)。 網(wǎng)：帶權的圖。 ? 有 n(n1)條邊的有向圖稱為 有向完全圖 ，有 n(n1)/2條邊的無向圖稱為 無向完全圖 。 在無向圖中， (V1， V3)表示 V1和 V3之間的一條邊。Houfeng Wang, ICL of PKU 1 圖論初步 線性表：一對一； （一個節(jié)點對一個節(jié)點） 由 簡 單 到 復 雜 樹結(jié)構：一對多； （一個節(jié)點對多個節(jié)點） 圖結(jié)構：多對多； （多個節(jié)點對多個節(jié)點） Houfeng Wang, ICL of PKU 2 圖的基本概念 圖 B A C D 6 3 2 1 5 頂點 :圖中的數(shù)據(jù)元素 用 V表示 頂 點的非空有限集合 邊 :頂點之間的關系 E表示兩個 頂 點之間關系的集合 Houfeng Wang, ICL of PKU 3 圖 有向圖 無向圖 在有向圖中， V1， V3表示從 V1到 V3的一條邊，也稱?。饫ㄌ柋硎荆?。 V1為弧尾或始點， V3為弧頭或終點。 V1 V3 V2 V4 V1 V3 V2 V4 Houfeng Wang, ICL of PKU 4 V1 V3 V2 V4 V1 V3 V2 V4 頂點集合 V={V1 ， V2 ， V3 ， V4 } 邊的集合 E={V1 ， V3, V3 ， V4, V2 ， V4, V4， V1} 如何表示： G=( V, E ) 頂點集合 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 圖相關的實際例子 例 1 交通圖（公路、鐵路） 頂點：地點 邊：連接地點的公路 交通圖中的有單行道雙行道，分別用無向邊、有向邊表示； 例 2 電路圖 頂點：元件 邊：連接元件之間的線路 例 3 通訊線路圖 頂點：地點 邊：地點間的連線 例 4 化學結(jié)構？ Houfeng Wang, ICL of PKU 6 基本概念 ? 假定沒有節(jié)點指向自身的邊。 ? 完全圖的含義：任意兩個不同的節(jié)點之間都有邊（ 有向圖有互指的弧 ） Houfeng Wang, ICL of PKU 7 權：圖的邊 (或弧 ) 相關的數(shù)值。 頂點的度：依附于該頂點的邊數(shù)或弧數(shù)。 入度：（僅對有向圖）以該頂點為頭的弧數(shù)。 B A C D 6 3 2 1 5 4 Houfeng Wang, ICL of PKU 8 幾個問題 ? 線性表是一種特殊的樹（假定樹可以空）嗎？ ? 樹是一種特殊的圖嗎？ ? 假定樹的最大度數(shù)為 m ，如果將其看成一個圖，頂點的最大度數(shù)是多少？ Houfeng Wang, ICL of PKU 9 連通圖（強連通圖） 在無（有）向圖 G=( V, E )中，若對任何兩個不同頂點 v、 u都存在從 v到 u的路徑，則稱 G是連通圖（強連通圖） V5 V1 V2 V4 V3 連通圖 V3 V1 V2 V4 V5 V6 非連通圖 Houfeng Wang, ICL
環(huán)評公示相關推薦
鄂ICP備17016276號-1