408答疑

---

---

一、圖的基本概念

圖的定義

圖 $G$ 由頂點集 $V$ 和邊集 $E$ 組成，記為 $G=(V,E)$，其中 $V(G)$ 表示圖 $G$ 中頂點的有限非空集；$E(G)$ 表示圖 $G$ 中頂點之間的關系（邊）集合。

非空性

• 線性表可以是空表，樹可以是空樹，但圖不可以是空圖。也就是說，圖中不能一個頂點也沒有，圖的頂點集 $V$ 一定非空，但邊集 $E$ 可以為空，此時圖中只有頂點而沒有邊。

非線性結構

• 圖是非線性結構，由頂點和邊組成。

頂點和邊的表示

• 若 V = { v 1 , v 2 , ? , v n } V = \{v_1, v_2, \cdots, v_n\} V={v1?,v2?,?,vn?}，則用 $|V|$ 表示圖 $G$ 中頂點的個數。
• 邊集 $E=\{(u,v)|u\in V,v\in V\}$，用 $|E|$ 表示圖 $G$ 中邊的條數。

頂點

• 圖中的結點稱為頂點。

邊

• 連接頂點之間的線稱為邊。
  • 無向邊簡稱為邊。
  • 有向邊稱為弧。

有向圖 & 無向圖

有向圖

• 有向圖的邊使用尖括號 $??$ 表示。
• 弧是頂點的有序對，記為 $?v,w?$，其中 $v,w$ 是頂點，$v$ 稱為弧尾，$w$ 稱為弧頭。
• $?v,w?$ 稱為從 $v$ 到 $w$ 的弧，也稱 $v$ 鄰接到 $w$。

有向圖 $G_1$ 的表示

• $G_1=(V_1,E_1)$
• V 1 = { 1 , 2 , 3 } V_1 = \{1, 2, 3\} V1?={1,2,3}
• $E_1=\{?1,2?,?2,1?,?2,3?\}$

無向圖

• 無向圖的邊使用圓括號 $()$ 表示。
• 邊是頂點的無序對，記為 $(v,w)$ 或 $(w,v)$。
• 可以說 $w$ 和 $v$ 互為鄰接點。
• 邊 $(v,w)$ 依附于 $w$ 和 $v$，或稱邊 $(v,w)$ 和 $v,w$ 相關聯。

無向圖 $G_2$ 的表示

• $G_2=(V_2,E_2)$
• V 2 = { 1 , 2 , 3 , 4 } V_2 = \{1, 2, 3, 4\} V2?={1,2,3,4}
• $E_2=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}$

簡單圖 & 多重圖

簡單圖

• 不存在重復邊。
• 不存在頂點到自身的邊。

多重圖

• 允許兩個頂點之間的邊數大于 1 條。
• 允許頂點通過一條邊和自身關聯。

頂點的度、入度和出度

頂點的度

• 連接頂點邊的數量稱為頂點的度，記為 $TD(v)$。
• 在無向圖中，每條邊和兩個頂點相關聯，因此無向圖的全部頂點的度之和等于邊數的 2 倍。
• 在下圖中，每個頂點的度均為 3。

有向圖的度

• 對于有向圖，頂點 $v$ 的度分為入度和出度。
  • 入度：以頂點 $v$ 為終點的有向邊的數目，記為 $ID(v)$。
  • 出度：以頂點 $v$ 為起點的有向邊的數目，記為 $OD(v)$。
• 頂點 $v$ 的度等于其入度與出度之和，即 $TD(v)=ID(v)+OD(v)$。
• 有向圖的全部頂點的入度之和與出度之和相等，并且等于邊數，這是因為每條有向邊都有一個起點和終點。

路徑、路徑長度和回路

• 路徑：

  • 頂點 $v_p$ 到頂點 $v_q$ 之間的一條路徑是指頂點序列 $v_p,v_{i_1},v_{i_2},?,v_{i_m},v_q$。
  • 路徑上的邊的數目稱為路徑長度。
  • 第一個頂點和最后一個頂點相同的路徑稱為回路或環。
  • 若一個圖有 $n$ 個頂點，且有大于 $n?1$ 條邊，則此圖一定有環。

• 簡單路徑：

  • 在路徑序列中，頂點不重復出現的路徑稱為簡單路徑。

• 簡單回路：

  • 除第一個頂點和最后一個頂點外，其余頂點不重復出現的回路稱為簡單回路。

距離

• 從頂點 $u$ 出發到頂點 $v$ 的最短路徑若存在，則此路徑的長度稱為從 $u$ 到 $v$ 的距離。
• 若從 $u$ 到 $v$ 根本不存在路徑，則記該距離為無窮（$\infty$）。

子圖

• 設有兩個圖 $G=(V,E)$ 和 $G^{\prime }=(V^{\prime },E^{\prime })$，若 $V^{\prime }$ 是 $V$ 的子集，且 $E^{\prime }$ 是 $E$ 的子集，則稱 $G^{\prime }$ 是 $G$ 的子圖。
• 若有滿足 $V(G^{\prime })=V(G)$ 的子圖 $G^{\prime }$，則稱其為 $G$ 的生成子圖。
• 注意：并非 $V$ 和 $E$ 的任何子集都能構成 $G$ 的子圖，因為這樣的子集可能不是圖，即 $E$ 的子集中的某些邊關聯的頂點可能不在這個 $V$ 的子集中。
• 下圖中，(2)為(1)的子圖。

完全圖（簡單完全圖）

無向完全圖

• 對于無向圖，邊的取值范圍為 $0$ 到 $\frac{n(n?1)}{2}$。
• 如果圖有 $\frac{n(n?1)}{2}$ 條邊，則無向圖稱為無向完全圖。
• 在完全圖中任意兩個頂點之間都存在邊。

有向完全圖

• 對于有向圖，邊的取值范圍為 $0$ 到 $n(n?1)$。
• 如果圖有 $n(n?1)$ 條弧，則有向圖稱為有向完全圖。
• 在有向完全圖中任意兩個頂點之間都存在方向相反的兩條弧。

連通圖、連通分量、強連通圖，強連通分量

連通性

連通圖

• 在無向圖中，若從頂點 $v$ 到頂點 $w$ 有路徑存在，則稱 $v$ 和 $w$ 是連通的。
• 若圖 $G$ 中任意兩個頂點都是連通的，則稱圖 $G$ 為連通圖，否則稱為非連通圖。

強連通圖

• 在有向圖中，若有一對頂點 $v$ 和 $w$，從 $v$ 到 $w$ 和從 $w$ 到 $v$ 之間都有路徑，則稱這兩個頂點是強連通的。
• 若圖中任意一對頂點都是強連通的，則稱此圖為強連通圖。

連通分量

• 無向圖中的極大連通子圖稱為連通分量。
• 在下圖中，圖 $G$ 有 3 個連通分量。
• 假設一個圖有 $n$ 個頂點，若邊數小于 $n?1$，則此圖必是非連通圖。
  • 若該圖是非連通圖，非連通情況下邊最多的情況：由 n-1 個頂點構成一個完全圖，此時再加入一個頂點則變成非連通圖。

強連通分量

• 有向圖中的極大強連通子圖稱為有向圖的強連通分量。
• 在下圖中，圖 $G$ 有 2 個連通分量。
• 假設一個有向圖有 $n$ 個頂點，若該圖是強連通圖，則連通情況下邊最少的情況：至少需要 n 條邊，構成一個環路。

注意：在無向圖中討論連通性，在有向圖中討論強連通性

生成樹 & 生成森林

生成樹

• 連通圖的生成樹是包含圖中全部頂點的一個極小連通子圖。
• 若圖中頂點數為 $n$，則它的生成樹含有 $n?1$ 條邊。
• 包含圖中全部頂點的極小連通子圖，只有生成樹滿足這個極小條件，對生成樹而言，若砍去它的一條邊，則會變成非連通圖，若加上一條邊則會形成一個回路。

生成森林

• 非連通圖中，連通分量的生成樹構成了非連通圖的生成森林。

注意：區分極大連通子圖和極小連通子圖。極大連通子圖要求子圖必須連通，而且包含盡可能多的頂點和邊；極小連通子圖是既要保持子圖連通又要使得邊數最少的子圖。

邊的權、網和帶權路徑長度

邊的權

• 在一個圖中，每條邊都可以標上具有某種含義的數值，該數值稱為該邊的權值。

網

• 這種邊上帶有權值的圖稱為帶權圖，也稱網。

帶權路徑長度

• 路徑上所有邊的權值之和，稱為該路徑的帶權路徑長度。

稠密圖 & 稀疏圖

稀疏圖

• 邊數很少的圖稱為稀疏圖。
• 稀疏和稠密本身是模糊的概念，稀疏圖和稠密圖常常是相對而言的。
• 一般當圖 $G$ 滿足 $|E|<|V|{\log }_2|V|$ 時，可以將 $G$ 視為稀疏圖。

稠密圖

• 反之稱為稠密圖。

有向樹

• 一個頂點的入度為 $0$、其余頂點的入度均為 $1$ 的有向圖，稱為有向樹。

六、參考資料

鮑魚科技課件

b站免費王道課后題講解: link

網課全程班: link

26王道考研書