--- # System prepended metadata title: 離散數學 tags: [離散數學, NTNU, 109_Spring, 期末複習] --- # 離散數學 ###### tags: `109_Spring` `NTNU` `期末複習` `離散數學` ## Relation p.19 ## 9-6 ### 定義 chopper的草稿 偏序: 自反，傳遞，反對稱，不一定每個元素都可比較 全序:集合之中每個元素都可比較 良序:1.符合全序 2.需有最小元素 ### 哈斯圖 ![](https://i.imgur.com/EIFPeyD.png) ![](https://i.imgur.com/qSobw20.png) a:原圖 b:因為偏序集必為自反，故環必定出現，所以在圖上可省略 c:因為偏序集必具傳遞性，所以可以省略(1,3),(1,4).....等，確立方向為上後移走箭頭，形成哈斯圖 定義:經過以上步驟後得到一個簡化後卻可以包含所有訊息的圖，稱為哈斯圖 ![](https://i.imgur.com/Gne0Pke.png) ### 極大元與極小元 定義:在偏序集中不小/大於其他元素，稱之為極大/小元，在哈斯圖中象徵著頂/底元素 ![](https://i.imgur.com/fWsNzvI.png) 由圖可知，極小元為2跟5，故極小元不一定只有一個 ### 最大元與最小元 定義:在偏序集中大/小於其他元素，稱之為最大/小元，在哈斯圖中象徵著頂/底元素 ![](https://i.imgur.com/8ByStGh.png) 由圖可知，最小元為a，沒有最大元，故最大/小元是唯一的 ### 上界與下界 定義:若一個元素大/小於等於 在偏序集中**子集**中於其他元素，則稱該元素為子集的上/下界 ### 最小上界與最大下界 定義:若x為S的子集A的一個上界，並且x小於其他A的所有上界，則稱x為A的最小上界 ### 格 若偏序集S中的每對元素皆具有最小上界&最大下界，則稱S為格 ### 拓樸排序法 目的:將偏序集S轉化為與偏序關係相容的全序集 作法:找到當下的極小元放到全序集中，直到S為空集合 ![](https://i.imgur.com/D4jvFBZ.png) 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 ![](https://i.imgur.com/VJPulAu.png) + complete $n$ 個 vertex $n\times (n-1)\div2$ 條edge ![](https://i.imgur.com/tY6h0OG.png) + cycle （從 n = 3 開始） $n$ 個 vertex $n$ 條edge ![](https://i.imgur.com/amcU6Up.png) + hypercube $2^n$ 個 vertex $n\times 2^{n-1}$ 條edge ![](https://i.imgur.com/aaxxjSw.png) + wheel $n+1$ 個 vertex $2n$ 條 edge ![](https://i.imgur.com/djq1VwJ.png) ### 二分圖 如果一個簡單圖 $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 ![](https://i.imgur.com/eCZzdVZ.png) + 配對 一個簡單圖 $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)$ 為最大 ### 圖的表示法 + 相鄰矩陣（左下到右上） ![](https://i.imgur.com/LWI2flW.png) + 相鄰列表 ![](https://i.imgur.com/POJVY7E.png) ![](https://i.imgur.com/oVvd2D0.png) + 關聯矩陣 ![](https://i.imgur.com/JXoCReA.png) ### 同構 當兩個圖形的頂點跟邊可以找到一個一對一的對應關係時，這兩個圖可以被視為完全相同的，稱為同構（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$，兩個集合有交集就連一條線，反之不連線，最後得出來的圖即為交集圖。 ![](https://i.imgur.com/Kp9BujD.png) ### 正規圖（Regular graph） 圖中每個點的 degree 都一樣 ![](https://i.imgur.com/m9Uhj6W.png) ### 補圖（Complement graph） 圖G的補圖G^為圖G的完整圖扣掉圖G有的點 #### 自補圖 跟補圖同構