基礎圖論: 連通、路徑與環

藉由基礎圖論(一)，我們基礎的認識了圖的結構與一些有趣的圖。本章來聊聊圖的一些連通及一些有趣的性質

有一些名詞定義可能會因為不同作者而有不同說法，本篇筆記會以 D.B.West 寫的 Introduction to Graph Theory 2/e 為主

走訪一張圖

行走 Walk

假設在一張圖上，我們可以隨便走，然後將走過的節點與邊都記錄下來，那應該會得到一個序列

$v_0,e_1,v_1,...,e_k,v_k$，那麼這個序列我們就稱之為一條「行走」
舉例: 下圖中，存在一行走

$v_1,e_2,v_2,e_5,v_3,e_6,v_1,e_1,v_2,e_2,v_1$
由例子會發現，行走是允許重複的。

行走分成兩種:

• 開行走(open walk): 頭與尾的節點不相同
• 閉行走(closed walk): 頭與尾的節點相同

道路 Trail

如果一個行走並沒有重複的邊(可能有重複的節點)，則稱其為「道路」。
舉例:

$v_1,v_3,v_8,v_6,v_3,v_2,v_1$ 是一條道路
因這張圖是一張簡單圖，故道路可以不寫邊，因為對於任兩節點的邊都是固定的

• 如果一道路經過所有道路，則稱為歐拉道路 (Eulerian trail)

道路分成兩種:

• 開道路 (open trail) : 頭與尾的節點不相同
• 閉道路 (closed trail) : 頭與尾的節點相同

迴路 Circuit

如果一條道路為閉道路，則稱其為「迴路」。一個迴路的邊不可重複，但是點可以重複。
舉例: 下圖中

$v_1,v_2,v_3,v_4,v_5,v_3,v_1$ 為一條迴路

• 如果一迴路經過所有節點，則稱為歐拉迴路 (Eulerian circuit)

路徑 Path

一條道路節點不重複，則稱為「路徑」
舉例: 下圖中

$v_5,v_4,v_3,v_1,v_2$ 為一條路徑

• 在一簡單圖中，可能存在一條最長路徑經過所有節點

環 Cycle

當遍歷一條路徑時，最後又走一條邊回到起點，則稱此為環
舉例: 下圖中

$v_1,v_2,v_4,v_5,v_3,v_1$ 為一環

• 在一環中，只有起點與終點可以重複，其他節點及邊皆不可重複

圖的連通性 Connectivity

設有一張圖

$G$

• 假如
  $G$ 是連通的 (connected)，那
  $G$ 就必存在一條
  $(u,v)$ 路徑，否則就是不連通的 (disconnected)
• 假如
  $G$ 有一條
  $(u,v)$ 路徑，則
  $u$ 與
  $v$ 連通
• 假如有一條
  $(u,v)$ 邊，則
  $u$ 與
  $v$ 相鄰 (adjacent)

以上圖為例，

$a$ 與

$c$ 連通，但

$b$ 與

$e$ 不連通；

$a$ 與

$c$ 連通，因此存在至少一條路徑

連通塊 Connected Component

連通塊定義

連通塊又稱連通分量、連通單元、連通成分，定義如下:

• 設一張圖
  $G$，其連通塊為
  $G$ 的極大 (maximal) 連通子圖 (subgraph)
• 如果有一連通塊無邊 (即只有
  $1$ 節點)，則稱為顯然的 (trivial) 連通塊
• 如果有一連通塊有邊，則稱為非顯然的 (nontrivial) 連通塊
• 如果
  $G$ 只有一個連通塊，則稱
  $G$ 為連通圖

$$
以上圖來說，有兩個連通塊

$\{a,b,c,d,e\}$ 與

$\{f\}$，其中

$\{f\}$ 為顯然連通塊

性質: 連通塊的數量關係

引理

假設

$G$ 有多個連通塊，每增加一條邊，則會減少

$0$ 或

$1$ 個連通塊；每減少一條邊則有可能增加

$0$ 或

$1$ 個連通塊

命題

設一張圖

$G$ 有

$n$ 個節點與

$k$ 條邊，則

$G$ 最少有

$n-k$ 個連通塊

證明

令

$G$ 有

$n$ 個節點與

$0$ 條邊，則

$G$ 有

$n$ 個連通塊。根據引理，每次加一條邊，最多可能減少

$1$ 個連通塊。因此設有

$k$ 條邊，則最少會有

$n-k$ 個連通塊

備註

當

$k=n-1$ 時，

$G$ 最少會有

$1$ 個連通塊。又根據連通性，

$G$ 只有

$1$ 連通塊時，

$G$ 為一張連通圖。因此如果

$G$ 是一張連通圖，則至少有

$n-1$ 條邊

二分圖的連通性質

二分圖的定義在之前已經提過了，可以回去複習一下
一張二分圖

$G$ 可以被分為兩個獨立集

$X,Y$

性質: 判斷一張圖是否為二分圖

引理

任何奇數邊的閉行走都包含奇數環

定理 (Kőnig [1936])

一張圖是二分圖若且為若不存在奇數環

證明

$\to$ : 令

$G$ 是二分圖。考慮每次在兩個獨立集之間交替行走，如果果要走回原來的獨立集就必須走偶數次才能走回來，因此

$G$ 沒有奇數環

$\leftarrow$ : 令

$G$ 是一張沒有奇數環的圖。我們可以把圖分成兩個獨立集。令

$u$ 為非顯然連通塊

$H$ 的節點，對於所有

$v\in V(H)$，令

$f(v)$ 為

$u,v$-路徑的最短長度。令

$X=\{v\in V(H):f(v)\text{ 是偶數}\}$、

$Y=\{v\in V(H):f(v)\text{ 是奇數}\}$。有一條在

$X$ 或

$Y$ 的邊

$(u,u^{\prime })$ 會造出一條

$u$ 到

$v$ 的閉奇數行走，分別由邊

$(u,v)$、

$(v,v^{\prime })$ 與

$(v^{\prime },u)$ 構成。但這違背了引理，因為奇數閉行走會產生奇數環。因此

$G$ 有奇數環的假設並不成立，換句話說，

$G$ 沒有奇數環

歐拉道路/迴路 Eulerian Trail/Circuit

• 如果一張圖存在一條閉道路能走過所有邊，則稱這一張圖是歐拉圖
• 一個歐拉道路為一條包含所有圖上的邊的道路
• 一個歐拉迴路為一條包含所有圖上的邊的迴路

定理

一張圖

$G$ 是歐拉圖若且為若只存在最多一個非顯然連通塊，且所有節點的度數皆為

$2$
證明太多了不想寫

---

想一想

1. 在一簡單圖中，任選兩點

   $u,v$ ，所形成
   $u$ 到
   $v$ 的行走是否必包含一條
   $u$ 到
   $v$ 的道路?

2. 在一張完全圖

   $K_4$ 中，是否包含非環的道路?

3. 在柯尼斯堡的七橋問題中，是否存在歐拉路徑或是歐拉迴路?

---

參考資料

• D.B.West - Introduction to Graph Theory 2/e
• geeksforgeeks
• 維基百科

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2024/12/15