---
# System prepended metadata

title: 6-1 圖的種類及術語
tags: [Discrete Math]

---

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

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

![](https://i.imgur.com/gJXvigT.png)
右圖中.$(5,4)$ $(0,1,2,3)$ 不存在無向 $walk$ 可到達彼此


---

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


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

---

### 弱連通圖 Weakly Connected Graph
**Def：**
無法藉由單一方向拜訪所有的點
![](https://i.ytimg.com/vi/A7iByRFzEy4/maxresdefault.jpg)

---
### 名詞定義及特性
![](https://i.imgur.com/OUbBM5e.png)

---

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

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

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

==子圖 **(Subgraph)** 可以是==
* 原圖 (自己本身)
* 空圖 (完全刪除)
![](https://www.researchgate.net/profile/Peter_Hufnagl/publication/232085273/figure/fig5/AS:214001028997138@1428033229916/Subgraph-isomorphism-An-example-of-subgraph-isomorphism-between-graphs-G-and-G-with.png)

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

---

### 誘導子圖 Induced Subgraph，(點隨意、邊全取)
**Def：**
設 $G'$ 為 $G$ 的子圖，滿足 $E'$ = $E∩(V'×V')$，(取的點形成的邊數必須與父圖一致)
![](https://i.imgur.com/4YNlSKO.png)
右圖為左圖的誘導子圖 **(Induced Subgraph)**

---

### 生成子圖 Spanning Subgraph，(點全取、邊隨意)
**Def：**
設 $G'$ 為 $G$ 的子圖，滿足 $V'$ = $V$，(取的點數必須與父圖一致)
![](https://image.slidesharecdn.com/graphtheory1-120903115149-phpapp01/95/graph-theory-1-40-728.jpg?cb=1346673196 =400x)


==**Spanning Tree 也是 Spanning Subgraph**==
![](https://i.imgur.com/YZQqdzU.png)

---

### 連通分量圖 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** (自己本身)

![](https://i.imgur.com/gtECXge.png)

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

* 觀念視覺化


![](https://i.imgur.com/ayUCOGB.png =600x)

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

---

## 切點 (Cut point)、切集 (Cut set)
![](https://i.imgur.com/1g8jhm3.png)



---

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

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

![](https://i.imgur.com/BHeNVQn.png =400x)

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


---


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

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

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

![](https://i.imgur.com/UhjBzPm.png)
左圖 $G$ 為一個無向連通圖，因為含三個切點 (紅框處)，所以 $G$ 不是雙連通圖
而 $G$ 擁有 $4$ 個雙連通分量圖 (右圖)

---

### Component 觀念整理
![](https://i.imgur.com/ILmKUJ4.png)


---

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

![](https://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Complete_graph_K7.svg/1200px-Complete_graph_K7.svg.png =200x)
圖為 $K_7$ 無向完全圖，可得知 $K_n$ ==必為連通圖 (Connected Graph)==


---

### 有向完全圖 Direct Complete Graph
**Def：**
* 又稱 完全競賽圖 **Complete Tournament**
* 設 $G$ = $(V,E)$ 為一個有向圖，任兩點 $x,y$ 間恰有一邊相連 (單一方向即可)，稱為 有向完全圖 **(Direct Complete Graph)**
若 $G$ 的點數量為 $n$，記作 $K_{n}^{*}$
![](https://upload.wikimedia.org/wikipedia/commons/thumb/8/89/4-tournament.svg/180px-4-tournament.svg.png)
圖為 $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$

![](https://i.imgur.com/d7BtxMw.png)

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


---

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

![](https://i.imgur.com/fmSyHbn.png)
$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$

![](https://upload.wikimedia.org/wikipedia/commons/thumb/2/2f/Petersen_graph_complement.svg/1200px-Petersen_graph_complement.svg.png =450x)
設左圖為 $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$：

    ![](https://i.imgur.com/I8bqDxt.png)

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

![](https://i.imgur.com/IHDGTaN.png)

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

    * $Q_n$ 點數：$2^n$
    * 每個點 $Degree$ 為 $n$
![](https://i.imgur.com/Uy0jHfh.png)


---

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

![](https://i.imgur.com/xGI6JUv.png)


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