圖論-L1

L1 基本概念

符號定義

符號	意義
$G=(V,E)$	圖、頂點集、邊集
$n=\|V(G)\|$；$m=\|E(G)\|$	頂點數；邊數
$N_G(v)$	$v$ 的鄰居集合
$d_G(v)$ 或 $\deg_G(v)$	$v$ 的度數
$\delta(G)$；$\Delta(G)$	最小度；最大度
$G[S]$	由頂點集 $S$ 導出的子圖
$\overline G$	$G$ 的補圖
$K_n$、$P_n$、$C_n$	完全圖、$n$ 點路徑圖、$n$ 點環圖

圖表示

	Adjacency matrix (鄰接矩陣)	Adjacency list (鄰接串列)
內容	$n\times n$ 矩陣，$A_{ij}=1\iff ij\in E$	每個頂點列出所有鄰居
儲存空間	$O(n^2)$	$O(n+m)$
查詢 $i,j$ 是否相鄰	$O(1)$	最壞需掃描 $i$ 的所有鄰居，$O(d(i))$
適用情況	稠密圖、需要快速查邊	稀疏圖、常遍歷鄰居

度數與計數

• Degree (度): $d_G(v)$ 是與 $v$ 相接的邊數；自環計兩次。
• Minimum degree (最小度): $\displaystyle\delta(G)=\min_{v\in V(G)}d(v)$。
• Maximum degree (最大度): $\displaystyle\Delta(G)=\max_{v\in V(G)}d(v)$。
• Degree sequence (度序列): 圖中所有頂點的度數，通常依 $d_1\ge d_2\ge\cdots\ge d_n$ 排序。
• $k$-regular graph ($k$-正則圖): 每個頂點的度數皆為 $k$，即 $d(v)=k$。

Lemma

握手定理: ${\sum_{v\in V(G)}d(v)=2|E(G)|=2m}$

度數總和為偶數對簡單圖僅為必要條件，不是充分條件。

子圖與導出子圖

名詞	定義	點與邊
Subgraph (子圖) $H\subseteq G$	$V(H)\subseteq V(G)$，$E(H)\subseteq E(G)$，保留邊時須保留端點	點、邊皆可刪
Spanning subgraph (生成子圖)	$H\subseteq G$ 且 $V(H)=V(G)$	點完全不變，邊可刪
Vertex-induced subgraph (頂點導出子圖) $G[S]$	固定非空 $S\subseteq V(G)$，保留 $G$ 中兩端點皆在 $S$ 的所有邊	先選點，相關邊全收
Edge-induced subgraph (邊導出子圖)	固定非空 $B\subseteq E(G)$，邊集為 $B$，頂點為這些邊的所有端點	先選邊，端點全收；沒有額外孤立點

令 $m=|E(G)|$:

• 生成子圖有 $2^m$ 個
• 邊導出子圖有 $2^m-1$ 個 (非空)

Walk、Trail、Path、Cycle 與連通性

名詞	定義	重複頂點	重複邊
Walk	連續頂點之間都有邊的頂點序列	可以	可以
Trail	沒有重複邊的 walk	可以	不可以
Path	沒有重複頂點的 walk	不可以	不可以
Cycle	只有起終點相同，且至少含 3 條邊的封閉 walk	只重複起終點	不可以

• $\text{Path}\Rightarrow\text{Trail}\Rightarrow\text{Walk}$；逆向不一定成立。
• 每條從 $u$ 到 $v$ 的 walk 都包含一條從 $u$ 到 $v$ 的 path (反覆刪去迴繞部分)。

---

• 若 $\delta(G)\ge1$，則存在 長度至少 $\delta(G)$ 的 path。
• 若 $\delta(G)\ge2$，則存在 長度至少 $\delta(G)+1$ 的 cycle。

證明在講義 P91-93

---

• Connected (連通圖): 任意兩頂點間都存在 path；否則是 disconnected。

• Component (連通分量/分支): 無法再擴大的連通子圖 (maximal connected subgraph)。

• Cut-edge / Bridge (割邊/橋): 刪除該邊後，連通分量數增加。

• Cut-vertex / Articulation point (割點): 刪除該頂點及其相接邊後，連通分量數增加。

• 頂點數 $>2$ 的連通圖若有割邊，則一定有割點；逆向不一定成立。

• 連通圖刪除一條割邊後，恰好產生 2 個連通分量。

圖同構

Isomorphism (同構): 圖 $G,H$ 之間存在頂點集合的雙射 $f:V(G)\to V(H)$，且保留相鄰與不相鄰關係: ${uv\in E(G)\iff f(u)f(v)\in E(H)}$

• 證明同構：給出具體的頂點對應 $f$，驗證雙射與相鄰關係。
• 證明不同構：找任一圖不變量或結構差異即可，例如頂點數、邊數、度序列、連通分量、環的結構、補圖結構。
• 同構圖必有相同度序列，但相同度序列不保證同構。
• 畫圖時的頂點位置和邊彎曲方式不影響同構；重點在鄰接關係。

特殊圖

圖	定義/性質
Complete graph $K_n$	任意兩個不同頂點皆相鄰；$(n-1)$-正則
Path graph $P_n$	$n$ 個頂點形成一條路徑
Cycle graph $C_n$	$n\ge3$ 的單一環；連通 2-正則
$k$-regular graph	每個頂點度數恰為 $k$
Petersen graph	常見的特殊圖
Bipartite graph (二部圖)	頂點可分成兩個非空不交集合，每條邊都跨越兩集合
Complete bipartite graph $K_{m,n}$	二部圖且跨組頂點全部相連
Star graph (星圖) $K_{1,n}$	特殊的完全二部圖：1 個中心點，$n$ 個葉點
$k$-partite graph ($k$ 部圖)	頂點分成 $k$ 個非空不交集合，各集合內無邊
Complete $k$-partite graph $K_{n_1,\ldots,n_k}$	不同集合之間的點全部相連，集合內無邊

二部圖判定

${G\text{ 為二部圖}\iff G\text{ 可合法二著色}\iff G\text{ 不含奇數長度環}}$

• 二著色：任一邊兩端顏色不同。
• 一旦有奇環，必然不是二部圖；偶環可以是二部圖。
• 超立方體 $Q_k$: 頂點為所有 $k$ 位元 0/1 字串，恰有一位不同的兩頂點相鄰。
  • ${|V(Q_k)|=2^k}$
  • ${d(v)=k}$
  • ${|E(Q_k)|=k2^{k-1}}$
  • 依字串中 $1$ 的個數之奇偶分組，可得二部圖。

有向圖與競賽圖

• $D=(V,A)$: $A$ 是 弧(arc)/有向邊 集合，$(u,v)$ 代表從 $u$ 指向 $v$，不表示存在 $(v,u)$。
• Out-neighborhood (外鄰域): $N^+(v)=\{u\mid (v,u)\in A\}$。
• In-neighborhood (內鄰域): $N^-(v)=\{u\mid (u,v)\in A\}$。
• Out-degree (出度) $d^+(v)$：從 $v$ 出發的弧數。
• In-degree (入度) $d^-(v)$：進入 $v$ 的弧數。

Lemma

有向圖握手公式: ${\sum_{v\in V(D)}d^+(v)=|A(D)|=\sum_{v\in V(D)}d^-(v)}$

---

名詞	定義
Strongly connected (強連通)	任意兩個不同頂點 $u,v$，都有 $u\to v$ 和 $v\to u$ 的有向路徑
Unilaterally connected (單連通)	任意兩個不同頂點，至少一個方向存在有向路徑
Weakly connected (弱連通)	忽略所有邊的方向後，得到的無向圖連通
Disconnected（不連通）	存在一對頂點，兩個方向都沒有有向路徑

• $\text{強連通}\Longrightarrow\text{單向連通}\Longrightarrow\text{弱連通}$

---

• Oriented graph (定向圖): 將簡單無向圖的每條邊指定恰一個方向。
• Tournament (競賽圖)：完全圖 $K_n$ 的一種定向；每對不同頂點之間恰有一個方向的弧。
• 競賽圖若含任一有向環，則一定含有向 3-cycle。

證明在講義 P194

---

• King (王)：從該頂點出發，到所有其他頂點的最短有向路徑長度皆 $\le2$。
• 競賽圖中 出度最大的頂點必為王，因此每一個競賽圖至少有一個王。
• 不存在恰好兩個王的競賽圖。

證明在講義 P196-199