# 離散數學
###### tags: `109_Spring` `NTNU` `期末複習` `離散數學`

## Relation
p.19

## 9-6
### 定義
chopper的草稿

偏序: 自反，傳遞，反對稱，不一定每個元素都可比較

全序:集合之中每個元素都可比較

良序:1.符合全序 2.需有最小元素

### 哈斯圖



a:原圖
b:因為偏序集必為自反，故環必定出現，所以在圖上可省略
c:因為偏序集必具傳遞性，所以可以省略(1,3),(1,4).....等，確立方向為上後移走箭頭，形成哈斯圖

定義:經過以上步驟後得到一個簡化後卻可以包含所有訊息的圖，稱為哈斯圖


### 極大元與極小元

定義:在偏序集中不小/大於其他元素，稱之為極大/小元，在哈斯圖中象徵著頂/底元素


由圖可知，極小元為2跟5，故極小元不一定只有一個

### 最大元與最小元

定義:在偏序集中大/小於其他元素，稱之為最大/小元，在哈斯圖中象徵著頂/底元素


由圖可知，最小元為a，沒有最大元，故最大/小元是唯一的

### 上界與下界

定義:若一個元素大/小於等於 在偏序集中**子集**中於其他元素，則稱該元素為子集的上/下界

### 最小上界與最大下界

定義:若x為S的子集A的一個上界，並且x小於其他A的所有上界，則稱x為A的最小上界

### 格

若偏序集S中的每對元素皆具有最小上界&最大下界，則稱S為格

### 拓樸排序法

目的:將偏序集S轉化為與偏序關係相容的全序集

作法:找到當下的極小元放到全序集中，直到S為空集合


step1. 找到極小元1，移出
step2. 找到極小元2和5，隨便選一個後移出
step3. 找到極小元2，移出
剩下不想寫

最後生成
1<5<2<4<20<12 的相容全序集

## 圖 ( Graphs )
### 定義
+ 圖 $G=(V,E)$ 是由頂點的非空集合 $V$（vertex/node）和邊的集合 $E$（edge）所構成，每個邊都相關於一個或兩個頂點，稱為這個邊的端點（endpoint），而我們稱這個邊連結（connect）它的端點。

+ 沒有迴圈（loop）和重邊（multiple edges）的稱為簡單圖（simple graph）
+ 迴圈：連結某頂點到同一頂點的邊
+ 重邊：邊連結到相同的一對頂點

+ 如果鄰接關係是對稱（symmetric）的，則該圖為無向（undirected）的

+ 在無向圖中
+ 如果頂點 $v$ 和 $u$ 被一條邊連結著，我們稱 $u$ 和 $v$ 為相鄰的/$u$ 是 $v$ 的鄰居/$v$ 是 $u$ 的鄰居
+ 與頂點 $u$ 相鄰的邊個數（$\text{#neighbor of u}$）為 $u$ 的分支度（degree）記為 $\text{deg}(u)$
+ 所有 $u$ 的鄰居的集合稱為 $u$ 的鄰域，寫作 $\text{N}(u)$

+ degree 為 0 的稱為 isolated，為 1 的稱為 pendent
+ 無向圖的 loop 的 degree 要算兩次（出發一次回來一次）

+ 定理 握手定理
令 $G=(V,E)$ 為一個無向圖，則 $\sum_{v\in V} deg(v) = 2|E|$
+ 推論
無向圖中分支度為奇數的頂點有偶數個
$p.f.$
令 $G=(V,E)$ 為一個無向圖，令 $V_1,V_2$ 分別為奇數分支度及偶數分支度的頂點的集合
+ 由握手定理，得 $2|E|=\sum_{v\in V_1} deg(v)+\sum_{v\in V_2} deg(v)$
+ 因為 $2|E|-\sum_{v\in V_2} deg(v)$ 為偶數，且 $v\in V_1$ $deg(v)$ 為奇數，所以可以得到 $|V_2|$ 為偶數

### 特殊圖形
+ path
$n$ 個 vertex
$n-1$ 條 edge
+ complete
$n$ 個 vertex
$n\times (n-1)\div2$ 條edge
+ cycle （從 n = 3 開始）
$n$ 個 vertex
$n$ 條edge
+ hypercube
$2^n$ 個 vertex
$n\times 2^{n-1}$ 條edge
+ wheel
$n+1$ 個 vertex
$2n$ 條 edge

### 二分圖
如果一個簡單圖 $G$ 能將頂點集 $V$ 分成兩個不相交的子集合 $V_1$ 和 $V_2$，使得圖中每個邊分別連結 $V_1$ 的一個頂點和 $V_2$ 的一個頂點，則稱為二分圖（bipartitle），$(V_1,V_2)$ 稱為 $G$ 的點集合 $V$ 的二分子集（bipartition）
+ 定理
一個簡單圖為二分圖 $i.f.f.$ 能用兩個顏色來為所有頂點著色使得兩相鄰頂點皆不同色
$p.f.$
假設 $G=(V,E)$ 為簡單二分圖，$V=V_1\cup V_2$，其中 $V_1$ 和 $V_2$ 為不相交子集，且每個 $E$ 中的邊都連結一個 $V_1$ 的頂點和一個 $V_2$ 的頂點。將 $V_1$ 中的每個頂點塗上一種顏色， $V_2$ 中的每個頂點塗上另一種顏色。
現在假設能用兩個顏色來為所有頂點著色使得兩相鄰頂點皆不同色，令其中一種顏色形成的集合為 $V_1$，另一種顏色的集合為 $V_2$ ，則 $V_1$ 和 $V_2$ 為不相交的集合，而且 $V=V_1\cup V_2$，每個邊都連結$V_1$ 和 $V_2$的一個頂點，因為沒有任何相鄰的頂點同時在 $V_1$ 或 $V_2$ 中，圖 $G$ 即為二分圖。

+ 完全二分圖
$K_{m,n}$ 為 $|V_1|=m,|V_2|=n$ 的二分圖，且 $V_1$ 中每個頂點都與 $V_2$ 中每個頂點相連接。
$m+n$ 個 vertex
$m\times n$ 條edge

+ 配對
一個簡單圖 $G=(V,E)$ 的配對（matching）$M$ 是 $E$ 的子集合，使得沒有兩個邊接合到同一個頂點
+ 完全配對
今天將這個簡單圖二分為 $(V_1,V_2)$ ，如果 $V_1$ 中每個頂點都是配對中的某個端點（$|V_1|=|M|$）則稱為完全配對

+ 霍爾婚姻定理
一個 $(V_1,V_2)$ 的二分圖 $G=(V,E)$ 中，存在由 $V_1$ 到 $V_2$ 的完全配對 $i.f.f.$ $\forall A\subseteq V_1,|N(A)|\geq|A|$
$p.f.$

+ 最大配對
一個簡單圖 $G=(V,E)$ 及一個函式 $w:E\rightarrow R$ ，尋找一個配對 $M$ 使得 $\sum_{e\in M}w(e)$ 為最大

### 圖的表示法
+ 相鄰矩陣（左下到右上）
+ 相鄰列表


+ 關聯矩陣

### 同構
當兩個圖形的頂點跟邊可以找到一個一對一的對應關係時，這兩個圖可以被視為完全相同的，稱為同構（isomorphic）。
+ 定義
兩個簡單圖 $G_1=(V_1,E_1),G_2=(V_2,E_2)$ 如果存在一個從 $V_1$ 到 $V_2$ 的一對一函數 $f$ 使得所有在 $V_1$ 中的頂點 $a$ 到 $b$，當他們在圖 $G_1$ 中相鄰時 $i.f.f.$ $f(a)$ 和 $f(b)$ 在圖 $G_2$ 中也相鄰的，此時稱 $G_1$ 和 $G_2$ 同構，反之稱為非同構（nonisomorphic）。
其中， $f$ 稱為同構函數，

## 鴿籠原理
若 $k$ 為正整數，如果有 $k+1$ 或更多的物件要放進 $k$ 個盒子中，則至少一個盒子包含 $2$ 個或更多物件
+ 廣義鴿籠原理
如果 $N$ 個物件放入 $k$ 個盒子，則至少有一個盒子包含至少 $\lceil N/k\rceil$ 個物件

## 拉姆賽定理
假設有 $6$ 個人，每兩個人包含兩個敵人或是兩個朋友，則會有三個共同朋友或是三個共同敵人
（在 graph 有另一種問法）設 $G$ 為一個有 $6$ 個節點的圖，則存在一個子圖 $G^{'}$ 為 $K_3$
$p.f.$
設 $w$ 為六個人之一，by鴿籠原理，$w$有$3$個朋友或$3$個敵人，設那$3$個人分別為$x,y,z$
+ 因為對稱性，所以假設$x,y,z$為$w$的朋友
+ 如果 $x,y,z$ 為共同敵人，則符合假設
+ 否則（至少其中兩個互為朋友），再加上$w$，則符合假設有三個朋友

## 圖的聯通性
### 路徑（path）
指一個由邊所形成的序列，從圖的一個頂點出發，沿著圖形的邊，經由一個頂點移動到下一個頂點

### 圖學中不同的說法
- path $\leftrightarrow$ walk
- circuit $\leftrightarrow$ closed walk （起點跟終點不一樣的 path/walk）
- simple path $\leftrightarrow$ trail （沒有重複的邊）
- elementary path $\leftrightarrow$ path （沒有重複的頂點）
- circuit with no repeated vertices $\leftrightarrow$ cycle

### 子圖
+ 如果一個無向圖有一條 path 連結所有圖中不同的節點，則稱為連通。反之稱為不連通
+ $G=(V,E)\ 的子圖\ G'=(V',E'), V'\subseteq V\ 且\ E'\subseteq E$
+ 承上，如果 $G'\neq G$ 則稱 $G'$ 為真子圖
+ 圖 $G$ 的（連結）元件為一個 $G$ 的連通子圖其不為其他 $G$ 的連通子圖的真子集（proper subset $\subset$）

#### 問題討論
設 $G$ 為一個有 $n$ 個節點與 $m$ 個邊的簡單圖（假設$n>1$）
- 如果 $G$ 為連通的，$m$ 的最大/小值會是多少？
- $\frac{n\times(n-1)}{2}$ / $n-1$
- 如果 $G$ 有 $k$ 個元件，$m$ 最大/小值為多少？（depend on $n, k$）
- $\frac{(n-k+1)\times(n-k)}{2}$/

### 尤拉迴路/路徑（Eulerian circuit / path）
+ 在圖 $G$ 中包含所有邊的 single circuit 稱為尤拉迴路
+ 在圖 $G$ 中包含所有邊的 single 路徑稱為 尤拉路徑

#### 定理
一個連通多重圖（connected multigraph）有尤拉迴路
i.f.f.
每一個節點的 degree 必須為偶數

設 $G$ 為一個每個節點的分歧度都是偶數的連通圖，則 $G$ 有一個尤拉迴路
（以下證明）

#### 定理
一個多重圖存在尤拉路徑但不存在尤拉迴路 i.f.f. 圖中洽有兩個節點的 degree 為奇數。

### 哈密頓迴路/路徑（Hamiltonian circuits / paths）
+ 在圖 $G$ 中包含所有點的 single circuit 稱為哈密頓迴路
+ 在圖 $G$ 中包含所有點的 single 路徑稱為哈密頓路徑
+
#### 定理
如果 $G$ 為一個有 $n$ 個點（$n\geq3$），使得所有 $G$ 中點的 degree 至少為 n/2 ，則 $G$ 有一個哈密頓迴路

如果 $G$ 為一個有 $n$ 個點（$n\geq3$），使得所有 $G$ 中不相鄰兩點 $u,v$ 使得 deg(u)+deg(v)$\geq$ 2，則 $G$ 有一個哈密頓迴路

## 補充
### 交集圖（Intersection Graph）
有一群集合　$A_1, A_2, ..., A_n$，兩個集合有交集就連一條線，反之不連線，最後得出來的圖即為交集圖。

### 正規圖（Regular graph）
圖中每個點的 degree 都一樣

### 補圖（Complement graph）
圖G的補圖G^為圖G的完整圖扣掉圖G有的點
#### 自補圖
跟補圖同構

<!-- This is the the end of the note. -->