圖論名詞解釋

圖 / 節點 / 邊

圖 (Graph) 就是由多個節點 (Node / Vertex) 並透過邊 (Edge) 連結成的，像是下面的示意圖：

在題目中，常常會用來表達城鎮（Node / Vertex）和道路（Edge）之類的情境。

路徑和簡單路徑

路徑就是指圖上，某個節點「走」到另外一個節點所經過的路，比如 5 走到 2 的路徑就長這樣：

簡單路徑就是指路徑上經過的節點都不會重複，也就是說，一個節點只會經過一次。比如 5 走到 2 的路徑可以繞好幾圈再走到 2，但是這樣的路徑就不是簡單路徑了。

有向圖和無向圖

有向圖 (Directed Graph) 就是圖上的邊有方向，在題目的情境中，可能會用來表示只能單向通行的道路。畫出來的圖會長這樣：

無向圖 (Undirected Graph) 就是圖上的邊沒有方向，也就是說，兩個節點之間的道路是雙向的。畫出來的圖會長這樣：

連通性

在圖論中，我們說兩個節點是連通的，就是指這兩個節點之間有路徑可以走到。比如下面這張圖，1 和 4 是連通的，而 1 和 5 就不是連通的：

當一個圖上的所有節點都是互相連通的，我們就稱這個圖是連通圖 (Connected Graph)。反之，如果有節點之間沒有路徑可以走到，我們就稱這個圖是非連通圖 (Disconnected Graph)。

連通塊

在一個圖中，如果有一群節點彼此之間都是連通的，但是和其他節點不連通，我們就稱這一群節點是一個連通塊 (Connected Component)。比如下面這張圖，1、2、3 是一個連通塊，4、5 是另一個連通塊：

度數

在圖論中，我們用度數 (Degree) 來表示一個節點的相鄰節點數量。對於有向圖，我們分為入度 (In-Degree) 和出度 (Out-Degree)，分別表示進入這個節點的邊數和從這個節點出去的邊數。

以下面這張圖為例，節點 1 的出度是 2，入度是 1；節點 2 的出度是 1，入度是 1；節點 3 的出度是 1，入度是 1：

對於無向圖，我們只有度數這個概念，也就是說，無向圖的度數就是相鄰節點的數量，不用區分入度和出度。

環

在圖論中，我們說一個路徑是環 (Cycle) 的話，就是指這個路徑的起點和終點是同一個節點，且路徑中除了起點和終點外沒有重複的節點。比如下面這張圖，1 -> 2 -> 3 -> 1 就是一個環：

當然在無向圖中，定義也是一樣的。

子圖

在圖論中，我們說一個圖是另一個圖的子圖 (Subgraph) 的話，就是指這個圖的節點和邊都是另一個圖的節點和邊的子集。比如下面這張圖，紅色圈起來的 1、2、3 的部分就可以是這整張圖的子圖：