###### tags: `離散數學`

:::info
[回共筆首頁](https://hackmd.io/zrsmsRtEQ-OrnGslDxT0NQ)
[回科目首頁](https://hackmd.io/OwMjUy0fRq2kEuCRiMwtkQ)
:::
- [上課簡報](https://moodle2.ntust.edu.tw/pluginfile.php/237456/mod_resource/content/0/Chapter10_m.pdf)

[TOC]
# 10. Graphs
## Section 10.1: Graphs and Graph Models
### Definition:
- graph G = (V,E)
- 由 vertices(or nodes) 和 edges 組成

### Some Terminology
:::info
Terminology => 術語、專有名詞
:::
- simple graph: 每個邊都連結到不同的節點，且沒有兩個邊同時連接到相同的兩個節點
- Multigraphs: 可能有不同邊，同時連接到想童的兩個節點
- loop: 邊的兩端連接到同一個節點，自己連自己
- Pseudograph: 可能含有 loop 和 Multigraph 的特性
---
- Directed Graph: 有向圖，兩個節點連接的線具有方向性
- simple directed graph: 沒有 loop 且沒有 multiple edges
## Section 10.2: Graph Terminology and Special Types of Graphs
### Basic Terminology
1. adjacent (or neighbors): 相鄰的節點
2. neighborhood: G = (V,E), denoted by N(v)，指一個集合為v的所有adjacent
3. degree: denoted by deg(v)
- undirected graph: deg(v)， v 節點的edge的數量
- directed graph: in-deg(v)、out-deg(v)，指進v、指出v的edge的數量

### Special Simple Graph
- Complete Graphs:
- Cycles and Wheels
- n-Cubes

### Bipartite Graphs
- V個節點，可以被拆成兩個 subsets => V1, V2
- 沒有一條邊，連接著同一個 subsets 的節點
:::warning
### **Complete** Bipartite Graphs
V1的每個點都有連接到V2的每個節點
:::

## Section 10.3: Representing Graphs and Graph Isomorphism
### Adjacency Lists
- represent a graph with no multiple edges by specifying the vertices that are adjacent to each vertex of the graph
- 只能標示有存在連線，不能表示 multiple edges 的數量

### Adjacency Matrices
- 用矩陣紀錄點跟點之間的關係，也可以表示 multiple edges 的數量
:::warning
Note: The adjacency matrix of a **simple graph** is **symmetric**, i.e., aij = aji
Also, since there are no loops, each diagonal entry aij for i = 1, 2, 3, …, n, is 0.

- simple graph 所表示的 adjacency matrix 會是 symmetric (對稱的矩陣)
:::
### Incidence Matrices
- 紀錄 undirected graph 節點跟邊的關係
- row 跟 column 分別代表為 vertices 跟 edges
- 每條邊有自己的編號，會記錄哪兩個節點與之連接
- 假如一個邊，只存在著一個節點，就是 loop

### Isomorphism of Graph
- 當G1 = (V1,E1) 和 G2 = (V2, E2) 為 **one-to-one and onto**，就稱為 **isomorphic**
- 兩個 graph 看起來不一樣，因為節點擺放的位置不同，但他們的**節點與邊的關係**是一樣的，那就說他們是 isomorphic
:::success
isomorphic 的判別：
- 可以透過以下幾點觀察，做初步的篩選
1. number of vertices
2. number of edges
3. degree sequence
- 即使全都相同，也不可斷定 isomorphism，最後還是要把兩個 graph 的 adjacency matrix 證明
:::
:::info
Isomorphism 的應用：
1. 在化學中，觀察兩個化學物質的**化學鍵**是否相同，判斷是否為同一個化學物質。
2. 在電路圖中，元件擺放的位置可以任意擺放，用人眼是難以觀察得出來電路是否一樣，利用 isomorphism，在商業上判斷是否盜用智慧財產權/抄襲。
:::
## Section 10.4: Connectivity
### Paths
#### Definition
在一張圖中，從某一個節點透過邊(edge) travel 到另一個節點
途中經過的所有節點組合而成一個的 sequence

假設在圖 $G$ 裡，從 $u$ 到 $v$ 有個 path 的長度是 $n$
而這 $n$ 個邊(edge)分別是 $e_1,\;\dots\;,e_n$
節點就會是 $x_0=u,x_1,\;\dots\;,x_{n-1},x_n=v$
而這些節點會在邊裡面 $e_i$，其中 $i=1,\;\dots\;,n$

:::info
應用：
1. 定義訊息該怎麼在兩台電腦間傳遞
2. 有效率規劃郵件寄送的路線
:::

#### Terminology
- circuit：起始的點跟結束的點是同一個 ($u=v, n>0$)
- pass through：通過、透過(節點)
- traverse：走過(邊)
- simple：在一個 path 或 circuit 中沒有出現同樣的邊
- simple path/circuit：一個邊只能走過一次

### Connectedness
#### Undirected Graphs
在一個圖 $G$ 當中，讓兩個節點(vertices)都可以找到一條 path
就會說這個圖 $G$ 是 **connected**，否則就是 **disconnected**

當我們透過移除邊(edge)或節點(vertices)，
去製造一個 disconnected subgraph，這個動作就稱為 **disconnect**

#### Connected Components
對於 disconnected 的圖 $G$
必然是由數個不相交的區塊組成，而這些區塊就是 **connected component**
(一個 disconnected 的圖，必然會有兩個以上的 connected component)


#### Directed Graphs
在有向圖裡面，因為要考慮方向，所以 connected 又分成兩種
- strongly connected：$a,b$ 兩個點都滿足 path 從 $a$ 到 $b$，以及 $b$ 到 $a$
- weakly connected：把方向去掉之後(轉成無向圖)，可以符合 connected 的特性
:::info
若 digraph 滿足 strongly connected，就必定滿足 weakly connected。
反之，則不一定。
:::
:::success
可以利用 simple path，判斷兩個 Graph 是不是 Isomorphism
$G$ 不存在長度為 $3$ 的 simple path，但是 $H$ 存在長度為 $3$ 的 simple path，所以他們必定不是 Isomorphism。

**注意：如果都有出現長度一樣的 simple path 也不一定是 Isomorphism**
:::
### Counting Paths between Vertices
如果我們想要針對**長度**去計算從 $u$ 到 $v$ 有幾種路徑
我們可以利用矩陣乘法的方式去計算

矩陣 $A$ 每個數字都代表從 row 走到 column 的 path 有幾條
$A[0][0]$：$a$ 走到 $a\quad A[0][1]$：$a$ 走到 $b\dots$
$A[1][0]$：$b$ 走到 $a\dots$
$\quad\vdots$
$A[3][0]$：$d$ 走到 $a\dots$

我們如果要針對 path 長度求每個點到點之間有幾種方法的話
就會把矩陣 $A$ 拿去做冪次運算，$A^2$ 就是長度為 $2$ 的 path 有幾種
可以把 $A^2$ 寫成 $A\times A$，同理 $A^n=A^{n-1}\times A$

做矩陣乘法時，我們會把第一個矩陣的 row 乘到第二個矩陣的 column 上(一一對應元素)，並且把乘完的結果都相加
把 $A$ 矩陣當中每一格代表的意義寫出來，就很好理解了
舉 $A[0][0]$ 為例
把 $a$ 走到 $a$ 的步數乘上 $a$ 走到 $a$ 的步數(組合數用相乘)
加上 $a$ 走到 $b$ 的步數乘上 $b$ 走到 $a$ 的步數
加上 $a$ 走到 $c$ 的步數乘上 $c$ 走到 $a$ 的步數
$\quad\vdots$
全部加完之後，就是 $A[0][0]$ 的方法數了
而我們可以用這種方式去計算在任意長度下，從任意一點走到另一點的方法數
:::info
- $A^{2}$ 代表的意思是 length 為 $2$ 的 path 數量
-
:::
## Section 10.5: Euler and Hamiltonian Graphs
### Euler Paths and Circuits
- 一筆畫經過所有的 edge
#### Necessary and Sufficient Condition for Euler Paths and Circuits
- Euler paths $\iff$ 剛好兩個節點的 degree 是奇數
- Euler circuit $\iff$ 每個節點的 degree，必定是偶數

[哥尼斯堡七橋問題：什麽樣的圖形可以一筆畫？－李永樂](https://www.youtube.com/watch?v=QsMycO8B4M0)
### Hamilton Paths and Circuits
- 一筆畫經過所有的 vertice
- 沒有像 Euler path 或 circuit 一樣的奇偶特性
- 有一些可以觀察出來的特性
- 超過 $2$ 個的「單一 degree」一定沒有 **path**，因為一個當 start，一個當 end，就不可能再經過其他的 vertice
- 只有 $1$ 個的「單一 degree」一定沒有 **circuit**，因為沒辦法走回起始點
:::info
$K_{n}$ 是指complete simple graph
:::