本文主要內(nèi)容為：圖的定義以及基本術(shù)語

• 圖的定義
  • 圖

圖G的組成：由 數(shù)據(jù)元素的集合E 和 數(shù)據(jù)間的關(guān)系集合E 組成，記作：G = <V, E>

頂點 (vertex)：數(shù)據(jù)元素，V就是頂點的有窮非空集合

邊 (edge): 頂點的序偶對，例如 (v1, v2)，E就是邊的集合

• • 子圖

定義：設(shè) G=<V, E> 是一個圖，E' 是 E 的子集，V' 是 V 的子集，且 E' 中的邊權(quán) 僅與 V' 中的頂點相關(guān)聯(lián)，

           則 G' = <V', E'> 稱為 圖G 的子圖

特殊的子圖：空圖，只有一個頂點，圖G本身

• • 無向圖

定義：代表一條邊的頂點的序偶是無序的（即該邊無方向）

表示：無序的序偶對用圓括號表示，例如 (v1, v2) 和 (v2, v1) 是代表同一條邊

• • 有向圖

定義：代表一條邊的頂點的序偶是有序的（即該邊有方向）

表示：有序的序偶對用尖括號表示，例如 <v1, v2> 和 <v2, v1> 是代表不同的邊

弧：有向圖的邊的別稱

弧尾 / 始點：邊的起點，例如 <v1, v2> 中的 v1

弧頭 / 終點：邊的終點，例如 <v1, v2> 中的 v2

• • 帶權(quán)圖

定義：圖的每條邊邊或弧都附帶權(quán)(weight)

權(quán)的作用：可以用于表示從一個頂點到另一個頂點的距離，費用，代價等等

• • 稀疏圖：邊比較少的圖
  • 稠密圖：邊比較多的圖
  • 完全圖：任何兩個頂點間都有邊相關(guān)聯(lián)的圖

• 圖的基本術(shù)語
  • 無向圖頂點 v 的度：與該頂點相關(guān)的邊的數(shù)目，記作 D(v)
  • 有向圖頂點 v 的入度：以頂點 v 為終點的弧的數(shù)目，記作 ID(v)
  • 有向圖頂點 v 的出度：以頂點 v 為起點的弧的數(shù)目， 記作 OD(v)
  • 終端頂點 / 葉子：出度為 0 的頂點

• • 路徑：從一個頂點到另一個頂點，中間允許經(jīng)過其他頂點，有向圖的路徑也是有向的
  • 路徑長度：路徑上的 邊 或 弧  * 權(quán)重 之和
  • 回路 / 環(huán)：路徑的起點和終點是同一個頂點的路徑
  • 圖的根：從該頂點有路徑可以到達圖的其他所有頂點

• • 連通圖：無向圖的任意兩個頂點有路徑
  • 強連通圖：有向圖的任意兩個頂點之間有來回路徑
  • 連通分量：無向圖中的極大連通子圖
  • 強連通分量：有向圖強連通的極大子圖
  • 網(wǎng)絡(luò)：帶權(quán)的連通圖

• 圖的相關(guān)計算

n：表示圖中頂點的數(shù)目

e：表示圖中邊的數(shù)目

• • 無向圖 e 的取值范圍：[0，n(n - 1) / 2]
  • 有向圖 e 的取值范圍：[0, n(n - 1)]