設 \(A, B\) 為任意的兩個集合, 稱

\[\{\{a, b\} \mid a \in A \wedge b \in B\} \]

為 \(A\) 與 \(B\) 的無序積,記作 \(A \& B\).
為方便起見, 將無序積中的無序對 \(\{a, b\}\), 記為 \((a, b)\), 并且允許 \(a=b\). 需要指出的是, 無論 \(a, b\) 是否相等, 均有 \((a, b)=(b, a)\), 因而 \(A \& B=B \& A\).

定義 \(\mathbf{1 4 . 1}\) 無向圖 \(G=<V, E>\), 其中
(1) \(V \neq \varnothing\) 為頂點集, 元素稱為頂點
(2) \(E\) 為 \(V \& V\) 的有窮多重集, 稱為邊集, 其元素稱為無向邊, 簡稱邊

實例
設

\[\begin{aligned} V= & \left\{v_1, v_2, \ldots, v_5\right\}, \\ E= & \left\{\left(v_1, v_1\right),\left(v_1, v_2\right),\left(v_2, v_3\right),\left(v_2, v_3\right),\right. \\ & \left.\left(v_2, v_5\right),\left(v_1, v_5\right),\left(v_4, v_5\right)\right\} \end{aligned} \]

則 \(G=<\boldsymbol{V}, \boldsymbol{E}>\) 為一無向圖

定義 \(\mathbf{1 4 . 2}\) 一個有向圖 \(D\) 是一個有序的二元組 \(\langle V, E\rangle\), 其中
(1) \(V\) 同定義 \(14.1(1)\).
(2) \(E\) 是笛卡兒積 \(V \times V\) 的有窮多重子集, 稱作邊集, 其元素稱作有向邊, 簡稱為邊. 通常用圖形來表示無向圖和有向圖: 用小圓圈 (或實心點) 表示頂點, 用頂點之間的連線表示無向邊, 用帶箭頭的連線表示有向邊.

  1. 無向圖和有向圖統稱作圖, 但有時也常把無向圖簡稱作圖. 通常用 \(G\) 表示無向圖\({\mathrm{(Graph)}}\), \(D\) 表示 有向圖\({\mathrm{(Directed Graph)}}\), 有時也用 \(G\) 泛指圖 (無向的或有向的). 用 \(V(G), E(G)\) 分別表示 \(G\) 的頂點集和邊集, \(|V(G)|,|E(G)|\) 分別是 \(G\) 的頂點數和邊數. 有向圖也有類似的符號.

  2. 頂點數稱作圖的階, \(n\) 個頂點的圖稱作 \(n\) 階圖.

  3. 一條邊也沒有的圖稱作零圖. \(n\) 階零圖記作 \(N_n\), \(1\) 階零圖 \(N_1\) 稱作平凡圖. 平凡圖只有一個頂點, 沒有邊.

  4. 在圖的定義中規定頂點集 \(V\) 為非空集, 但在圖的運算中可能產生頂點集為空集的運算結果, 為此規定頂點集為空集的圖為空圖, 并將空圖記作 \(\varnothing\).

  5. 當用圖形表示圖時, 如果給每一個頂點和每一條邊指定一個符號 (字母或數字, 當然字母還可以帶下標), 則稱這樣的圖為標定圖, 否則稱作非標定圖.

  6. 將有向圖的各條有向邊改成無向邊后所得到的無向圖稱作這個有向圖的基圖.

  7. 設 \(G=\langle V, E\rangle\) 為無向圖, \(e_k=\left(v_i, v_j\right) \in E\), 稱 \(v_i, v_j\) 為 \(e_k\) 的端點, \(e_k\) 與 \(v_i\left(v_j\right)\) 關聯.

  • ? 若 \(v_i \neq v_j\), 則 稱 \(e_k\) 與 \(v_i\left(v_j\right)\) 的關聯次數為 1 ;

  • ? 若 \(v_i=v_j\), 則稱 \(e_k\) 與 \(v_i\) 的關聯次數為 2 , 并稱 \(e_k\) 為環.

  • ? 如果頂點 \(v_l\) 不與邊 \(e_k\) 關聯,則稱 \(e_k\) 與 \(v_l\) 的關聯次數為 0 .

  • 若兩個頂點 \(v_i\) 與 \(v_j\) 之間有一條邊連接, 則稱這兩個頂點相鄰. 若兩條邊至少有一個公共端點,則稱這兩條邊相鄰.

  1. 設 \(D=\langle V, E\rangle\) 為有向圖, \(e_k=\left\langle v_i, v_j\right\rangle \in E\), 稱 \(v_i, v_j\) 為 \(e_k\) 的端點, \(v_i\) 為 \(e_k\) 的始點, \(v_j\) 為 \(e_k\) 的終點, 并稱 \(e_k\) 與 \(v_i\left(v_j\right)\) 關聯. 若 \(v_i=v_j\), 則稱 \(e_k\) 為 \(D\) 中的環.
    若兩個頂點之間有一條有向邊, 則稱這兩個頂點相鄰. 若兩條邊中一條邊的終點是另一條邊 的始點,則稱這兩條邊相鄰.
    圖 (無向的或有向的) 中沒有邊關聯的頂點稱作孤立點.

  2. 設無向圖 \(G=\langle V, E\rangle, \forall v \in V\), 稱

\[N_G(v)=\{u \mid u \in V \wedge(u, v) \in E \wedge u \neq v\} \]

為 \(v\) 的鄰域, 稱

\[\bar{N}_G(v)=N_G(v) \cup\{v\} \]

為 \(v\) 的閉鄰域, 稱

\[I_G(v)=\{e \mid e \in E \wedge e \text { 與 } v \text { 相關聯 }\} \]

為 \(v\) 的關聯集.
設有向圖 \(D=\langle V, E\rangle, \forall v \in V\), 稱

\[\Gamma_D^{+}(v)=\{u \mid u \in V \wedge< v, u>\in E \wedge u \neq v\} \]

為 \(v\) 的后繼元集, 稱

\[\Gamma_D^{-}(v)=\{u \mid u \in V \wedge<u, v>\in E \wedge u \neq v\} \]

為 \(v\) 的先驅元集, 稱

\[N_D(v)=\Gamma_D^{+}(v) \cup \Gamma_D^{-}(v) \]

為 \(v\) 的鄰域, 稱

\[\bar{N}_D(v)=N_D(v) \cup\{v\} \]

為 \(v\) 的閉鄰域(包含該點本身).

定義 \(\mathbf{1 4 . 3}\) 在無向圖中, 如果關聯一對頂點的無向邊多于 1 條, 則稱這些邊為平行邊, 平行邊的條數稱作重數.

在有向圖中, 如果關聯一對頂點的有向邊多于 1 條, 并且這些邊的始點與終點相同 (也就是它們的方向相同), 則稱這些邊為平行邊. 含平行邊的圖稱作多重圖, 既不含平行邊也不含環的圖稱作簡單圖.

定義 \(\mathbf{1 4 . 4}\)

? 設 \(G=< V, E>\) 為無向圖, \(\forall v \in V\), 稱 \(v\) 作為邊的端點的次數為 \(v\) 的度數, 簡稱為 度, 記作 \(d_G(v)\). 在不發生混淆時, 略去下標 \(G\), 簡記為 \(d(v)\).

? 設 \(D=< V, E>\) 為有向圖, \(\forall v \in V\), 稱 \(v\) 作為邊的始點的次數為 \(v\) 的出度, 記作 \(d_D^{+}(v)\), 簡記為 \(d^{+}(v)\). 稱 \(v\) 作為邊的終點的次數為 \(v\) 的入度, 記作 \(d_D^{-}(v)\), 簡記為 \(d^{-}(v)\). 稱 \(d^{+}(v)+d^{-}(v)\) 為 \(v\) 的度數, 記作 \(d_D(v)\), 簡記為 \(d(v)\).
注意: 在無向圖中, 頂點 \(v\) 上的環以 \(v\) 作 2 次端點. 在有向圖中, 頂點 \(v\) 上的環以 \(v\) 作一次始 點和一次終點, 共作 2 次端點.

在無向圖 \(G\) 中,令

\[\begin{gathered} \Delta(G)=\max \{d(v) \mid v \in V(G)\} \\ \delta(G)=\min \{d(v) \mid v \in V(G)\} \end{gathered} \]

分別稱為 \(G\) 的最大度\({\mathrm{Delta}}\)和最小度\({\mathrm{delta}}\).

可以類似定義有向圖 \(D\) 的最大度 \(\Delta(D)\) 、最小度 \(\delta(D)\) 和最大出度 \(\Delta^{+}(D)\) 、最小出度 \(\delta^{+}(D)\) 、最大入度 \(\Delta^{-}(D)\) 、最小入度 \(\delta^{-}(D)\).

\[\begin{aligned} \Delta(D) & =\max \{d(v) \mid v \in V(D)\} \\ \delta(D) & =\min \{d(v) \mid v \in V(D)\} \\ \Delta^{+}(D) & =\max \left\{d^{+}(v) \mid v \in V(D)\right\} \\ \delta^{+}(D) & =\min \left\{d^{+}(v) \mid v \in V(D)\right\} \\ \Delta^{-}(D) & =\max \left\{d^{-}(v) \mid v \in V(D)\right\} \\ \delta^{-}(D) & =\min \left\{d^{-}(v) \mid v \in V(D)\right\} \end{aligned} \]

并把它們分別簡記為 \(\Delta, \delta, \Delta^{+}, \delta^{+}, \Delta^{-}, \delta^{-}\).

另外, 稱度數為 1 的頂點為懸掛頂點, 與它關聯的邊稱作懸掛邊. 度為偶數 (奇數) 的頂點稱 作偶度（奇度) 頂點.

下述定理是歐拉于 1736 年給出的, 稱作握手定理, 是圖論的基本定理.
定理 \(\mathbf{1 4 . 1}\) 在任何無向圖中, 所有頂點的度數之和等于邊數的 2 倍.
證 圖中每條邊 (包括環) 均有兩個端點, 所以在計算各頂點度數之和時, 每條邊均提供 2 度. \(m\) 條邊,共提供 \(2 m\) 度.
定理 \(\mathbf{1 4 . 2}\) 在任何有向圖中, 所有頂點的度數之和等于邊數的 2 倍; 所有頂點的入度之和 等于所有頂點的出度之和, 都等于邊數.
證 本定理的證明類似于定理 14.1 .

推論 任何圖(無向的或有向的) 中, 奇度頂點的個數是偶數.
證 設圖 \(G=\langle V, E\rangle\), 令

\[\begin{aligned} & V_1=\{v \mid v \in V \wedge d(v) \text { 為奇數 }\} \\ & V_2=\{v \mid v \in V \wedge d(v) \text { 為偶數 }\} \end{aligned} \]

? 則 \(V_1 \cup V_2=V, V_1 \cap V_2=\varnothing\), 由握手定理可知

\[2 m=\sum_{v \in V} d(v)=\sum_{v \in V_1} d(v)+\sum_{v \in V_2} d(v) \]

? 由于 \(2 m, \sum_{v \in V_2} d(v)\) 均為偶數, 所以 \(\sum_{v \in V_1} d(v)\) 為偶數, 但因 \(V_1\) 中頂點度數為奇數, 所以 \(\left|V_1\right|\) 必為偶數.

? 設 \(G=\langle V, E\rangle\) 為一個 \(n\) 階無向圖, \(V=\left\{v_1, v_2, \cdots, v_n\right\}\), 稱 \(d\left(v_1\right), d\left(v_2\right), \cdots, d\left(v_n\right)\) 為 \(G\) 的度數列. 對于頂點標定的無向圖, 它的度數列是唯一的.

? 反之, 對于給定的非負整數列 \(d=\left(d_1, d_2, \cdots\right.\), \(\left.d_n\right)\), 若存在以 \(V=\left\{v_1, v_2, \cdots, v_n\right\}\) 為頂點集的 \(n\) 階無向圖 \(G\), 使得 \(d\left(v_i\right)=d_i\), 則稱 \(d\) 是可圖化的. 特別地, 若所得到的圖是簡單圖, 則稱 \(d\) 是可簡單圖化的. 對有向圖還可以類似定義出度列和入度列.

下述定理是顯然的.
**定理 **\(\mathbf{1 4 . 4}\) 設 \(G\) 為任意 \(n\) 階無向簡單圖, 則 \(\Delta(G) \leqslant n-1 \enspace(菊花圖)\).

定義 \(\mathbf{1 4 . 5}\) 設 \(G_1=\left\langle V_1, E_1\right\rangle, G_2=\left\langle V_2, E_2\right\rangle\) 為兩個無向圖 (兩個有向圖), 若存在雙射函數 \(f: V_1 \rightarrow V_2\), 使得 \(\forall v_i, v_j \in V_1\), \(\left(v_i, v_j\right) \in E_1\) 當且僅當 \(\left(f\left(v_i\right), f\left(v_j\right)\right) \in E_2\left(\left\langle v_i, v_j\right\rangle \in E_1\right.\) 當且僅 當 \(\left\langle f\left(v_i\right), f\left(v_j\right)>\in E_2\right)\), 并且 \(\left(v_i, v_j\right)\) 與 \(\left(f\left(v_i\right), f\left(v_j\right)\right)\left(<v_i, v_j>\right.\) 與 \(\left.<f\left(v_i\right), f\left(v_j\right)>\right)\) 的重數相同, 則稱 \(G_1\) 與 \(G_2\) 同構, 記作 \(G_1 \cong G_2\).

附錄：Peterson圖是一個經典的圖論問題，它由朱利葉斯·彼得森（Julius Petersen）于1898年首先提出。Peterson圖是一個無向圖，它具有10個頂點和15條邊，是一個具有特殊性質的圖。

Peterson圖的特殊之處在于它不具有哈密頓回路，但是有一個長度為5的環（也稱為Petersen環），這使得它在研究哈密頓回路和圖的著色問題等方面具有重要的意義。此外，Peterson圖還是一個具有自相似性質的圖，這種自相似性質在某些領域（如代數拓撲學和計算機圖形學等）中也具有重要的應用。

Peterson圖的繪制方式比較有特色，一般采用一個五芒星的形狀來表示，其中五條邊表示五個外部的點，而五個內部的點則連接成一個長度為5的環。Peterson圖的結構非常復雜，它被廣泛應用于圖論領域的各種問題，如圖的著色、哈密頓回路、匹配問題等等。

定義 \(\mathbf{1 4 . 6}\) 設 \(G\) 為 \(n\) 階無向簡單圖, 若 \(G\) 中每個頂點均與其余的 \(n-1\) 個頂點相鄰, 則稱 \(G\) 為 \(n\) 階無向完全圖, 簡稱為 \(n\) 階完全圖, 記作 \(K_n(n \geqslant 1)\).
設 \(D\) 為 \(n\) 階有向簡單圖, 若 \(D\) 中每個頂點都鄰接到其余的 \(n-1\) 個頂點, 則稱 \(D\) 為 \(n\) 階有向完全圖.
設 \(D\) 為 \(n\) 階有向簡單圖, 若 \(D\) 的基圖為 \(n\) 階無向完全圖 \(K_n\), 則稱 \(D\) 為 \(n\) 階競賽圖.

定義 \(\mathbf{1 4 . 7}\) 設 \(G\) 為 \(n\) 階無向簡單圖, 若 \(\forall v \in V(G)\), 均有 \(d(v)=k\), 則稱 \(G\) 為 \(k\)-正則圖. 由定義可知, \(n\) 階零圖是 0 -正則圖, \(n\) 階無向完全圖是 \((n-1)\)-正則圖,彼得松圖是 3-正則圖. 由握手定理可知, \(n\) 階 \(k\)-正則圖中, 邊數 \(m=\frac{k n}{2}\), 因而當 \(k\) 為奇數時, \(n\) 必為偶數.

定義 \(\mathbf{1 4 . 8}\) 設 \(G=\langle V, E\rangle, G^{\prime}=\left\langle V^{\prime}, E^{\prime}\right\rangle\) 為兩個圖 (同為無向圖或同為有向圖), 若 \(V^{\prime} \subseteq V\) 且 \(E^{\prime} \subseteq E\), 則稱 \(G^{\prime}\) 為 \(G\) 的子圖, \(G\) 為 \(G^{\prime}\) 的母圖, 記作 \(G^{\prime} \subseteq G\). 又若 \(V^{\prime} \subset V\) 或 \(E^{\prime} \subset E\), 則稱 \(G^{\prime}\) 為 \(G\) 的真子圖. 若 \(V^{\prime}=V\), 則稱 \(G^{\prime}\) 為 \(G\) 的生成子圖.
設 \(G=\langle V, E\rangle, V_1 \subset V\) 且 \(V_1 \neq \varnothing\), 稱以 \(V_1\) 為頂點集, 以 \(G\) 中兩個端點都在 \(V_1\) 中的邊組成邊集 \(E_1\) 的圖為 \(G\) 的 \(V_1\) 導出子圖(頂點）, 記作 \(G\left[V_1\right]\). 又設 \(E_1 \subset E\) 且 \(E_1 \neq \varnothing\), 稱以 \(E_1\) 為邊集, 以 \(E_1\) 中邊關聯的頂點為頂點集 \(V_1\) 的圖為 \(G\) 的 \(E_1\) 導出子圖（邊), 記作 \(G\left[E_1\right]\).

定義 \(\mathbf{1 4 . 9}\) 設 \(G=\left\langle V, E\right\rangle\) 為 \(n\) 階無向簡單圖, 令 \(\bar{E}=\{(u, v) \mid u \in V \wedge v \in V \wedge u \neq v \wedge(u, v) \notin\) \(E\}\), 稱 \(\bar{G}=\langle V, \bar{E}\rangle\) 為 \(G\) 的補圖. 若圖 \(G \cong \bar{G}\), 則稱 \(G\) 為自補圖.

(4) 設 \(u, v \in V\) (u, v 可能相鄰, 也可能不相鄰), 用 \(G \cup(u, v)\) (或 \(G+(u, v))\) 表示在 \(u, v\) 之間 加一條邊 \((u, v)\), 稱作加新邊.

===14.2 通路與回路

定義 \(\mathbf{1 4 . 1 1}\) 設 \(G\) 為無向標定圖, \(G\) 中頂點與邊的交替序列 \(\Gamma=v_{i_0} e_{j_1} v_{i_1} e_{j_2} \cdots e_{j_1} v_{i_l}\) 稱作 \(v_{i_0}\) 到 \(v_{i_l}\) 的通路, 其中 \(v_{i_{r-1}}, v_{i_r}\) 為 \(e_{j_r}\) 的端點, \(r=1,2, \cdots, l, v_{i_0}, v_{i_l}\) 分別稱為 \(\Gamma\) 的始點與終點, \(\Gamma\) 中邊的條數稱作它的長度. 若又有 \(v_{i_0}=v_{i_l}\), 則稱 \(\Gamma\) 為回路. 若 \(\Gamma\) 的所有邊各異, 則稱 \(\Gamma\) 為簡單通路. 若又有 \(v_{i_0}=\) \(v_{i_l}\), 則稱 \(\Gamma\) 為簡單回路. 若所有頂點 (除 \(v_{i_0}\) 與 \(v_{i_l}\) 可能相同外) 各異, 所有邊也各異, 則稱 \(\Gamma\) 為初級通路或路徑. 若又有 \(v_{i_0}=v_{i_l}\), 則稱 \(\Gamma\) 為初級回路或圈. 將長度為奇數的圈稱作奇圈, 長度為偶數的圈稱作偶圈。

? 另外, 若 \(\Gamma\) 中有邊重復出現, 則稱 \(\Gamma\) 為復雜通路. 若又有 \(v_{i_0}=v_{i i}\) 則稱 \(\Gamma\) 為復雜回路.

\(簡單通路和初級通路的區別是：\)

  • \(初級通路一定是簡單通路，簡單通路不一定是初級通路123\)。
  • \(初級通路是每個結點只經過一次，簡單通路是邊只經過一次123\)。
  • \(若通路中的所有邊互不相同，則稱它為簡單通路或跡13\)。

\(一個簡單通路不是初級通路的例子是：在有向圖中，從結點A到結點B有一條路徑為\)

\[A \rightarrow C\rightarrow D\rightarrow B\rightarrow E\rightarrow D\rightarrow B \]

\(，這條路徑中沒有重復的邊，所以是簡單通路，但是有重復的結點D和B，所以不是初級通路?\)。??

定理 \(\mathbf{1 4 . 5}\) 在 \(n\) 階圖 \(G\) 中, 若從頂點 \(u\) 到 \(v(u \neq v)\) 存在通路, 則從 \(u\) 到 \(v\) 存在長度小于等于 \(n-1\) 的通路.

? 推論 在 \(n\) 階圖 \(G\) 中, 若從頂點 \(u\) 到 \(v(u \neq v)\) 存在通路, 則 \(u\) 到 \(v\) 一定存在長度小于等于 \(n-1\) 的初級通路 (路徑).

定理 \(\mathbf{1 4 . 6}\) 在 \(n\) 階圖 \(G\) 中, 若存在 \(v\) 到自身的回路, 則一定存在 \(v\) 到自身長度小于等于 \(n\) 的 回路.
推論 在 \(n\) 階圖 \(G\) 中, 若存在 \(v\) 到自身的簡單回路, 則一定存在 \(v\) 到自身長度小于等于 \(n\) 的 初級回路.

? 長度相同的圈都是同構的, 因此在同構意義下給定長度的圈只有一個.

? 在標定圖中, 圈表示成頂點和邊的標記序列. 只要兩個標記序列不同, 就認為這兩個圈不同, 稱這兩個圈在定義意義下不同.

定義 \(\mathbf{1 4 . 1 2}\) 設無向圖 \(G=\langle V, E\rangle\), 若 \(u, v \in V\) 之間存在通路, 則稱 \(u, v\) 是連通的, 記作 \(u \sim v\). 規定 : \(\forall v \in V, v \sim v\).
若無向圖 \(G\) 是平凡圖或 \(G\) 中任何兩個頂點都是連通的, 則稱 \(G\) 為連通圖,否則稱 \(G\) 為非連通圖.
由定義不難看出, 無向圖中頂點之間的連通關系是 \(V\) 上的等價關系, 具有自反性、對稱性和傳遞性.
完全圖 \(K_n(n \geqslant 1)\) 都是連通圖, 而零圖 \(N_n(n \geqslant 2)\) 都是非連通圖.

定義 \(\mathbf{1 4 . 1 3}\) 設無向圖 \(G=\langle V, E\rangle, V_i\) 是 \(V\) 關于頂點之間的連通關系的一個等價類, 稱導出子圖 \(G\left[V_i\right]\) 為 \(G\) 的一個連通分支. \(G\) 的連通分支數記作 \(p(G)\).
由定義, 若 \(G\) 為連通圖, 則 \(p(G)=1\); 若 \(G\) 為非連通圖, 則 \(p(G) \geqslant 2\). 在所有的 \(n\) 階無向圖中, \(n\) 階零圖是連通分支最多的, \(p\left(N_n\right)=n\).

定義 \(\mathbf{1 4 . 1 4}\) 設 \(u, v\) 為無向圖 \(G\) 中的任意兩個頂點, 若 \(u \sim v\), 則稱 \(u, v\) 之間長度最短的通路為 \(u, v\) 之間的短程線. 短程線的長度稱為 \(u, v\) 之間的距離, 記作 \(d(u, v)\). 當 \(u, v\) 不連通時, 規定 \(d(u, v)=\infty\).
距離有以下性質: \(\forall u, v, w \in V(G)\),

  1. \(d(u, v) \geqslant 0\), 且當且僅當 \(u=v\) 時等號成立.
  2. 具有對稱性: \(d(u, v)=d(v, u)\).
  3. 滿足三角不等式: \(d(u, v)+d(v, w) \geqslant d(u, w)\).

定義 \(\mathbf{1 4 . 1 5}\) 設無向圖 \(G=\langle V, E\rangle.\) 若存在 \(V^{\prime} \subset V\) 使得 \(p(G-V^{\prime}) > p(G)\), 且對于任意的 \(V^{\prime \prime} \subset\) \(V^{\prime}\), 均有 \(p\left(G-V^{\prime \prime}\right)=p(G)\), 則稱 \(V^{\prime}\) 是 \(G\) 的點割集. 若 \(V^{\prime}=\{v\}\), 則稱 \(v\) 為割點.