---
title: '6-1 圖的種類及術語'
disqus: hackmd
---
[TOC]

## 連通圖 Connected Graph
**Def：**
設 $G=(V,E)$ 為一個無向圖 **(Undirected Graph)**
$∀x,y∈V，x≠y$，點集 $V$ 中任兩相異點之間==皆有一條 $walk$== 可以到達==彼此==
否則稱 $G$ 為 不連通圖 **(Disconnected Graph)**

右圖中.$(5,4)$ $(0,1,2,3)$ 不存在無向 $walk$ 可到達彼此

---

### 強連通圖 Strongly Connected Graph
**Def：**
設 $G=(V,E)$ 為一個有向圖 **(Directed Graph)**
$∀x,y∈V，x≠y$，點集 $V$ 中任兩相異點之間==皆有一條有向 $walk$== 可以到達==彼此==
右圖中 $2$ 不存在有向 $walk$ 可到達 $(0,1,3)$

---
### 單方向連通圖 Unilaterally Connected Graph
**Def：**
設 $G=(V,E)$ 為一個有向圖 **(Directed Graph)**
$∀x,y∈V，x≠y$，點集 $V$ 中任兩相異點之間==有一條有向 $walk$== 可以到達==其中一點==
可能有點出不去，同如上一個例子中右圖

---

### 弱連通圖 Weakly Connected Graph
**Def：**
無法藉由單一方向拜訪所有的點

---
### 名詞定義及特性

---

## 子圖 Subgraph，(點隨意、邊隨意)
**Def：**
* 設 $G=(V,E)$ 為一個有向圖 **(Directed Graph)** 或無向圖 **(Undirected Graph)**

* 設 $G'$ = $(V',E')$ 為一圖滿足
* $G'$ 的點包含於 $G$ 而且 $G$ 不是 ∅
* $G'$ 的邊包含於 $G$，$E'⊆E$

則稱 $G'$ 為 $G$ 的一個子圖 **(Subgraph)**

==子圖 **(Subgraph)** 可以是==
* 原圖 (自己本身)
* 空圖 (完全刪除)

右圖為左圖的子圖 **(Subgraph)**

---

### 誘導子圖 Induced Subgraph，(點隨意、邊全取)
**Def：**
設 $G'$ 為 $G$ 的子圖，滿足 $E'$ = $E∩(V'×V')$，(取的點形成的邊數必須與父圖一致)
右圖為左圖的誘導子圖 **(Induced Subgraph)**

---

### 生成子圖 Spanning Subgraph，(點全取、邊隨意)
**Def：**
設 $G'$ 為 $G$ 的子圖，滿足 $V'$ = $V$，(取的點數必須與父圖一致)

==**Spanning Tree 也是 Spanning Subgraph**==

---

### 連通分量圖 Connected Component Graph，(各個小國)
**Def：**
* 簡稱 **Component**
* 設 $G$ = $(V,E)$ 為一個無向不連通圖 **(Undirected & Unconnected Graph)**
* 則 $G$ 的 極大連通誘導子圖
* 連通誘導子圖： ==點隨意，邊全取，連通 **(Conneted)**==
* 極大：該 連通誘導子圖 無法再擴張
* 稱作 **連通分量圖 (Connected component)**
* 一個 $G$ 的 **Component** 個數記作：$κ(G)$，$κ$ 為希臘字母
* 在無向圖 **(Undirected Graph)** 中

* 一個點也視為一個 **Component**
* **Component** 裡的 **Component** 不成立，(下圖右)
* 演算法 **(Algorithm)**：**Graph Traversal** 尋找所有 **Component**

* $G$ 是連通圖 **(Connected Graph)**：只有一個 **Component** (自己本身)


左圖(上) $G$ 為一無向不連通圖 **(Undirected & Unconnected Graph)**，$κ(G)$ = $3$

* 觀念視覺化


參考資料：[演算法筆記](http://www.csie.ntnu.edu.tw/~u91029/Component.html#3)

---

## 切點 (Cut point)、切集 (Cut set)

---

### 雙連通圖 (Biconnected graph)
**Def：**
設 $G=(V,E)$ 為連通無向圖 **(Connected & Undirected Graph)**
* 不含切點 **(Connected Point)**，(任切掉一點依舊連通)
* 為無迴圈 **(Loop Free)**，(X 點到 X 點)

稱為雙連通圖 **(Biconnected Graph)**


左圖任切掉一點依舊保持連通 **(Connected)**

---

### 雙連通分量圖 (Biconnected component)
**Def：**

* 設 $G$ = $(V,E)$ 為一個無向連通圖
* 則 $G$ 的 極大雙連通誘導子圖

* 雙連通誘導子圖： ==點隨意，邊全取，連通 **(Connected)**，不含切點 **(Cut Point)**，無迴圈 **(Loop Free)**==
* 極大：該 雙連通誘導子圖 無法再擴張
* 稱作 **雙連通分量圖 (Biconnected component)**

左圖 $G$ 為一個無向連通圖，因為含三個切點 (紅框處)，所以 $G$ 不是雙連通圖
而 $G$ 擁有 $4$ 個雙連通分量圖 (右圖)

---

### Component 觀念整理

---

## 完全圖 Complete Graph
**Def：**
設 $G$ = $(V,E)$ 為一個無向圖，任兩點間恰有一邊相連，稱為完全圖 **(Complete Graph)**
若 $G$ 的點數量為 $n$，記作 $K_n$

圖為 $K_7$ 無向完全圖，可得知 $K_n$ ==必為連通圖 (Connected Graph)==

---

### 有向完全圖 Direct Complete Graph
**Def：**
* 又稱 完全競賽圖 **Complete Tournament**
* 設 $G$ = $(V,E)$ 為一個有向圖，任兩點 $x,y$ 間恰有一邊相連 (單一方向即可)，稱為 有向完全圖 **(Direct Complete Graph)**
若 $G$ 的點數量為 $n$，記作 $K_{n}^{*}$
圖為 $K_{4}^{*}$ 有向完全圖，因方向性所以==不具唯一性==

---

### 完全圖的邊數關係
設 $G$ 為完全圖，點數為 $n$
* $K_n$、$K_{n}^{*}$ 任兩點決定一邊，邊數為：$\left(
\begin{array}{ccc}
n\\
2\\
\end{array}
\right)$
* $K_{n}^{*}$ 的圖形表達數量：具有 $2^{\left(
\begin{array}{ccc}
n\\
2\\
\end{array}
\right)}$ 種可能，(每個邊有兩個方向)

---

## 雙分圖 Bipartite Graph
**Def：**
設 $G$ = $(V,E)$ 為一個無向圖 **(Undirected Graph)**，存在以下分割關係
* $V$ = $V_1∪V_2$，可將 $V$ 分成兩集合
* $V_1∩V_2$ = ∅，兩點集 **(Vertex Set)** 無重複的點
* 兩點集之間所有的邊關係 ⊆ $G$


圖中皆為 雙分圖 **Bipartite Graph**，紅黑兩點集各自無邊關係存在 (紅連紅，黑連黑)

---

### 完全雙分圖 Complete Bipartite Graph，(連好連滿)
**Def：**
* 同 雙分圖 **(Bipartite Graph)**
* 額外條件為：兩點集 **(Vertex Set)** 中，任兩點 $x,y$ 皆有邊相連
* 記作 $K_{m,n}$，$m,n$ 為兩點集的元素個數

$K_{m,n}$ 的邊數為 $m*n$

---

## 補圖 Complement Graph
**Def：**
設 $G$ = $(V,E)$ 為一個簡單無向圖 **(Undirected Simple Graph)**
若 $G'$ = $(V,E')$，且 $E'$ = $(V×V)-E$ 為 $G$ 圖的邊補集
稱 $G'$ 為 $G$ 的補圖 **(Complement Graph)**，記作 $\overline{G}$ 或 $G^c$

設左圖為 $G$ 右圖為 $H$，$\overline{G}$ = $G^c$ = $H$
* 設 $G$ 與 $\overline{G}$ 的點數合為 $n$，則該邊數合 = 完全圖 $K_n$ 的邊數$\left(
\begin{array}{ccc}
n\\
2\\
\end{array}
\right)$

---

## 特殊圖

* $n$ 個點的 $Cycle$，$C_n$：


* 輪子圖 **(Wheel Graph)**，$W_n$：
* 在 $C_n$ 中新增一個中心點與每一點相連，所以增加 $n$ 個邊


* 超立方體 **Hypercube**，$Q_n$：

* $Q_n$ 點數：$2^n$
* 每個點 $Degree$ 為 $n$

---

## 有向圖與無向圖整理
未列出的表示兩者皆可，此關係僅以此篇文章來區分、或許會有特例存在


###### tags: `Discrete Math`