考研相關文章參考資料為 wjungle 大神提供的筆記

L6 圖論

L6-1 種類與術語

定義
  • simple graph: 任意兩個相異頂點之間至多有一條邊，且不含自迴圈的圖
    • 否則可稱為 multigraph
  • Path: 不含重複點
    • close: Cycle
  • Trail: 不含重複邊
    • close: Circuit
定義
  • Subgraph
    • Induced subgraph: E′=E∩(V′×V′)E'=E\cap(V'\times V') (取點上所有屬於原圖的邊)
  • Spanning subgraph: 若 V′=VV'=V (取原圖所有點)
  • Connected component: 極大 Induced subgraph (盡可能大)
    • GG 的 component 個數記為 κ(G)\kappa(G)。
定義
  • Cut point/articulation point: 對連通圖 GG，移除頂點 vv 與其相鄰邊後，G−vG-v 不連通
  • Cut set: 對連通圖 GG，移除最小邊集合 X⊆EX\subseteq E 後圖變得不連通
  • Bridge: 單一邊 ee 本身構成 cut set
  • Biconnected graph: 不含 cut point 的連通圖稱為 biconnected graph。
  • Biconnected component: 圖 GG 的極大 biconnected induced subgraph 稱為一個 biconnected component。
定義
  • Complete graph: 設 ∣V∣=n|V|=n。若任意兩個相異頂點皆有一條邊相連，則 GG 稱為 complete graph，記為 KnK_n。
    • KnK_n 的邊數為 (n2)\displaystyle\binom{n}{2}。
  • Complete tournament: 若有向圖中任意兩個相異頂點之間恰有一條有向邊，則稱為 complete tournament，記為 Kn∗K_n^*。
    • nn 個帶標號頂點可形成的 complete tournament 數量為 2(n2)\displaystyle 2^{\binom{n}{2}}。
  • Complement graph: 對簡單圖 G=(V,E)G=(V,E)，其補圖記為 G‾=(V,E‾)\overline{G}=(V,\overline{E})，且對任意相異頂點 u,v∈Vu,v\in V，{u,v}∈E‾⟺{u,v}∉E\{u,v\}\in\overline{E}\Longleftrightarrow\{u,v\}\notin E
Note

設簡單圖 G=(V,E)G=(V,E) 且 ∣V∣=n|V|=n。

若 ∣E∣≥(n−12)+1|E|\ge\binom{n-1}{2}+1，則 GG 必為連通圖。

  • 1 個點 + Kn−1K_{n-1} + 1 條邊 (鴿籠原理最差情況)
定義
  • Clique: 圖 GG 的 complete subgraph 稱為 clique
    • maximal clique
  • Independent set: 任兩個頂點皆無邊相連的頂點集合
    • maximal independent set: set 可以只有一個點
  • Dominating set: 頂點集合 S⊆VS\subseteq V 使每個不在 SS 的頂點皆與 SS 中至少一個頂點相鄰
    • 頂點 Dominating 頂點
    • minimal dominating set
  • Vertex cover: 頂點集合 S⊆VS\subseteq V 圖中每條邊至少有一個端點屬於 SS
    • 頂點 Cover 邊
    • minimal vertex cover

L6-2 表示法與同構

定義
  • Degree: 對 v∈Vv\in V，deg⁡(v)\deg(v) 表示與 vv 相接的邊數。
  • Indegree 與 outdegree: 在有向圖中，id⁡(v)\operatorname{id}(v) 表示指向 vv 的邊數，od⁡(v)\operatorname{od}(v) 表示由 vv 指出的邊數。
  • k-regular graph: 所有頂點 v∈Vv\in V 皆滿足 deg⁡(v)=k\deg(v)=k。
定義

設 G1=(V1,E1)G_1=(V_1,E_1)、G2=(V2,E2)G_2=(V_2,E_2)。若存在雙射 f:V1→V2f:V_1\to V_2

且對任意 a,b∈V1a,b\in V_1，{a,b}∈E1⟺{f(a),f(b)}∈E2\{a,b\}\in E_1\Longleftrightarrow\{f(a),f(b)\}\in E_2

則稱 G1G_1 與 G2G_2 isomorphic (同構)，記為 G1≅G2G_1\cong G_2。

Note

同構圖具有下列不變性:

  • 頂點數與邊數
  • 由大到小排列的 degree sequence
  • 連通分量數與各分量的結構
  • cycle 等子圖結構
  • 對應頂點的鄰接關係與 degree
  • 補圖的同構關係

若任一不變性不同，兩圖必不同構；反之，不變性相同不一定保證同構。

  • 證明同構: 給出函數 ff (點的對應關係)
  • 證明不同構: 利用以上不變性
    • 某點周圍之點的 degrees
    • 某 cycle 經過的點的 degrees
    • 補圖不同構 (如果原圖邊數很多)

L6-3 圖之基本性質

定理

設 G=(V,E)G=(V,E) 為 simple graph 或 multigraph
則 ∑v∈Vdeg⁡(v)=2∣E∣\sum_{v\in V}\deg(v)=2|E|

  • 若 G=(V,E)G=(V,E) 為有向圖，則 ∑v∈Vid⁡(v)=∑v∈Vod⁡(v)=∣E∣\sum_{v\in V}\operatorname{id}(v)=\sum_{v\in V}\operatorname{od}(v)=|E|
Note

Maximal path: 無法再延伸的 path。

  • 每個有限圖皆存在 maximal path。
定理

設 G=(V,E)G=(V,E)。

  • 若對所有 v∈Vv\in V 皆有 deg⁡(v)≥2\deg(v)\ge2，則 GG 含有 cycle。
  • 若對所有 v∈Vv\in V 皆有 deg⁡(v)≥k\deg(v)\ge k，則 GG 含有長度至少為 k+1k+1 的 cycle。
定理

若 G=(V,E)G=(V,E) 為連通圖，則 ∣E∣≥∣V∣−1|E|\ge|V|-1

定理

設 G=(V,E)G=(V,E)，其中 V={v1,v2,…,vn}V=\{v_1,v_2,\ldots,v_n\}，AA 為 GG 的 adjacency matrix。

則對任意正整數 rr， (Ar)ij=從 vi 到 vj、長度為 r 的 walk 數(A^r)_{ij}=\text{從 }v_i\text{ 到 }v_j\text{、長度為 }r\text{ 的 walk 數}

Note

若 AA 為簡單無向圖 GG 的 adjacency matrix，則 GG 中三角形的個數為 16tr⁡(A3)\frac{1}{6}\operatorname{tr}(A^3)

  • 長度為 33 的 closed walk，每個三角形會被計算 66 次。

L6-4 Euler circuit 與 Hamilton cycle

定義
  • Euler circuit: 恰好經過圖中每一條邊一次的 circuit。
  • Hamilton cycle: 恰好經過圖中每一個頂點一次的 cycle。
定理

設 G=(V,E)G=(V,E) 為 simple graph 或 multigraph。
GG 具有 Euler circuit ⟺G\Longleftrightarrow G 為連通圖且 deg⁡(v)\deg(v) 為偶數 ∀v∈V\forall v\in V

若 G=(V,E)G=(V,E) 為有向圖，則
GG 具有 Euler circuit ⟺G\Longleftrightarrow G 為 strongly connected 且 id⁡(v)=od⁡(v),∀v∈V\operatorname{id}(v)=\operatorname{od}(v), \forall v\in V

定理

每個 complete tournament Kn∗K_n^* 皆具有 Hamiltonian path (HP)。

Note

  • KnK_n 具有 Euler circuit ⟺n\Longleftrightarrow n 為奇數。

  • KnK_n 具有 Hamilton cycle (HC)。

  • KnK_n 中相異 HC 的數量為 (n−1)!2\frac{(n-1)!}{2}

  • 當 nn 為奇數時，KnK_n 可分解為 n−12\frac{n-1}{2} 條彼此沒有共同邊的 HC。

Note
  • 判斷圖是否具有 HC: 嘗試畫出一條經過每個頂點一次的 cycle。
  • 判斷圖不具有 HC: 反設存在 HC。由於 HC 通過每個頂點時恰使用兩條相鄰邊，可利用此條件導出矛盾。

特殊圖:

  • PnP_n: 有 nn 個頂點的 path，長度為 n−1n-1。
  • CnC_n: 有 nn 個頂點的 cycle，長度為 nn。
  • WnW_n: 有 nn 個頂點的 wheel graph，由 Cn−1C_{n-1} 加上一個與環上所有頂點相鄰的中心頂點組成。
  • Gm,nG_{m,n}: m×nm\times n 的 grid graph
  • QnQ_n: nn 維 hypercube 或 nn-cube。其頂點可標為長度 nn 的 00-11 字串，兩頂點相鄰 ⟺\Longleftrightarrow 其字串恰有一個位元不同。
Note

QnQ_n 的性質:

  • 頂點數為 2n2^n。
  • QnQ_n 為 nn-regular graph，每個頂點的 degree 為 nn。
  • 邊數為 n⋅2n2=n⋅2n−1\frac{n\cdot2^n}{2}=n\cdot2^{n-1}
定理

設 G=(V,E)G=(V,E) 且 ∣V∣=n|V|=n。若對任意相異頂點 x,y∈Vx,y\in V，皆滿足deg⁡(x)+deg⁡(y)≥n−1\deg(x)+\deg(y)\ge n-1

則 GG 具有 Hamiltonian path (HP)。

  • Dirac 定理 (特例): 若對所有 v∈Vv\in V 皆有 deg⁡(v)≥n2\deg(v)\ge\frac{n}{2}，則 GG 具有 Hamiltonian cycle (HC)。
定理

設 G=(V,E)G=(V,E) 且 ∣V∣=n|V|=n。若任意兩個不相鄰頂點 x,yx,y 皆滿足 deg⁡(x)+deg⁡(y)≥n\deg(x)+\deg(y)\ge n

則 GG 具有 Hamiltonian cycle (HC)。

Note

設 G=(V,E)G=(V,E) 且 ∣V∣=n|V|=n。若 ∣E∣≥(n−12)+2|E|\ge\binom{n-1}{2}+2

則 GG 具有 Hamiltonian cycle (HC)。

  • 1 個點 + Kn−1K_{n-1} + 2 條邊
定義
  • Bipartite graph: 若 VV 可分割為 V=V1∪V2,V1∩V2=∅V=V_1\cup V_2,\quad V_1\cap V_2=\varnothing
    且 V1V_1、V2V_2 皆為 independent set
    • 記為 G=(V1∪V2,E)G=(V_1\cup V_2,E)。
  • Complete bipartite graph: 每個 V1V_1 中的頂點皆與每個 V2V_2 中的頂點相連
    • 記為 Km,nK_{m,n}，其中 m=∣V1∣m=|V_1|、n=∣V2∣n=|V_2|。
Note
  • Km,nK_{m,n} 的邊數為 mnmn。
  • Km,nK_{m,n} 具有 Euler circuit ⟺m,n\Longleftrightarrow m,n 皆為偶數。
Note

設 G=(V1∪V2,E)G=(V_1\cup V_2,E) 為 bipartite graph。

  • GG 具有 Hamiltonian cycle ⟹∣V1∣=∣V2∣\Longrightarrow |V_1|=|V_2|。
  • GG 具有 Hamiltonian path ⟹∣∣V1∣−∣V2∣∣≤1\Longrightarrow \left||V_1|-|V_2|\right|\le1。
  • Km,nK_{m,n} 具有 Hamiltonian cycle ⟺m=n≥2\Longleftrightarrow m=n\ge2。
  • Km,nK_{m,n} 具有 Hamiltonian path ⟺∣m−n∣≤1\Longleftrightarrow |m-n|\le1。
  • Kn,nK_{n,n} 中相異 Hamiltonian cycle 的數量為 12n!(n−1)!\frac{1}{2}n!(n-1)!

L6-5 平面圖

定義

若圖 G=(V,E)G=(V,E) 可在平面上重新繪製，使任兩條邊只可能在共同端點相交，且不產生 crossing，則稱 GG 為 planar graph。

定義
  • Elementary subdivision: 對圖 G=(V,E)G=(V,E) 的邊 e={a,b}e=\{a,b\}，移除 ee 後加入一個新頂點 zz，並加入邊 {a,z}\{a,z\} 與 {z,b}\{z,b\}。
  • Homeomorphic graph: 設 G1=(V1,E1)G_1=(V_1,E_1)、G2=(V2,E2)G_2=(V_2,E_2)。若 G1G_1 與 G2G_2 可分別經有限次 elementary subdivision 變為同構圖，則稱 G1G_1 與 G2G_2 為 homeomorphic (同胚)。
定理

Kuratowski 定理:
GG 為 planar graph ⟺\Longleftrightarrow GG 不具有與 K5K_5 或 K3,3K_{3,3} 同胚的 subgraph。

定義

設 G=(V,E)G=(V,E) 為 planar graph。平面嵌入後，邊所圍成的區域稱為 region 或 face。

  • Finite region: 有限區域。
  • Infinite region: 無限區域，又稱外部區域。
定理

Euler formula:
設 G=(V,E)G=(V,E) 為 connected planar graph，且 ∣V∣=v|V|=v、∣E∣=e|E|=e、rr 為 region 的數量，則 v−e+r=2v-e+r=2

Note

若 GG 為 planar graph，但不一定連通，則 v−e+r=1+κ(G)v-e+r=1+\kappa(G)

其中 κ(G)\kappa(G) 表示 GG 的 connected component 數量。

定理

設 G=(V,E)G=(V,E) 為 connected planar graph，∣V∣=v|V|=v、∣E∣=e|E|=e
則 32v≤e≤3v−6\frac{3}{2}v\le e\le3v-6

證明

令 NN 表示所有 region 的 degree 總和，則 2e=N≥3r2e=N\ge3r ，故 r≤23er\le\frac{2}{3}e

代入 Euler formula 得 2=v−e+r≤v−e+23e=v−13e2=v-e+r\le v-e+\frac{2}{3}e=v-\frac{1}{3}e

因此 e≤3v−6e\le3v-6。

Note

若連通圖 GG 滿足 e>3v−6e>3v-6，則 GG 為 nonplanar。

  • ex: K5K_5 為 nonplanar。
    • K5K_5 中 v=5v=5、e=10e=10，且 10>3⋅5−6=910>3\cdot5-6=9，故 K5K_5 為 nonplanar。
定理

設 G=(V,E)G=(V,E) 為 connected planar graph。若每個 cycle 至少含 kk 條邊，則 e≤kk−2(v−2)e\le\frac{k}{k-2}(v-2)

證明: 同樣利用不等式以及 Euler formula

Note
  • 若 GG 為 bipartite 或 triangle-free，則 e≤2v−4e\le2v-4。
  • ex: K3,3K_{3,3} 為 nonplanar。
    • K3,3K_{3,3} 中 v=6v=6、e=9e=9，且 9>2⋅6−4=89>2\cdot6-4=8，故 K3,3K_{3,3} 為 nonplanar。
定理

設 G=(V,E)G=(V,E) 為 connected planar graph，則 GG 中存在一個頂點的 degree 至多為 55。

證明: 設對所有 a∈Va\in V，皆有 deg⁡(a)≥6\deg(a)\ge6，則 2e=∑a∈Vdeg⁡(a)≥6v2e=\sum_{a\in V}\deg(a)\ge6v 矛盾 (nonplanar)。

L6-6 著色理論

定義
  • 對 GG 的頂點著色，使有邊相連的頂點具有不同顏色，稱為 proper coloring。
  • 若 GG 可用 nn 種 color 作 proper coloring，稱 GG 為 nn-colorable。
  • 使 GG 可 proper coloring 的最小 nn 稱為 GG 的 chromatic number，記作 χ(G)\chi(G)。
Note
  • χ(Kn)=n\chi(K_n)=n。
  • χ(Km,n)=2\chi(K_{m,n})=2。
  • χ(Pn)=2\chi(P_n)=2。
  • χ(Cn)={2,if n is even3,if n is odd\chi(C_n)=\begin{cases}2, & \text{if }n\text{ is even}\\3, & \text{if }n\text{ is odd}\end{cases}。
  • χ(Wn)=1+χ(Cn)\chi(W_n)=1+\chi(C_n)。
定理

四色問題:
設 G=(V,E)G=(V,E)。GG 為 planar graph ⟹\Longrightarrow GG 為 44-colorable。

  • 反向不一定成立
定理

GG 為 bipartite graph ⟺\Longleftrightarrow GG 為 22-colorable ⟺\Longleftrightarrow GG 中不含奇數長度的 cycle。

Note

P(G,λ)P(G,\lambda) 為使用 λ\lambda 種顏色，對圖 GG 做 proper coloring 的方法數

  • χ(G)=min⁡{λ∣P(G,λ)>0}\chi(G)=\min\{\lambda\mid P(G,\lambda)>0\}。
  • P(Kn,λ)=λ(λ−1)(λ−2)⋯(λ−n+1)P(K_n,\lambda)=\lambda(\lambda-1)(\lambda-2)\cdots(\lambda-n+1)。
  • P(Pn,λ)=λ(λ−1)n−1P(P_n,\lambda)=\lambda(\lambda-1)^{n-1}。
Note

拆邊黏點:

Note

若 G=G1∪G2G=G_1\cup G_2，且 G1∩G2=KnG_1\cap G_2=K_n，則

P(G,λ)=P(G1,λ)P(G2,λ)P(Kn,λ)P(G,\lambda)=\frac{P(G_1,\lambda)P(G_2,\lambda)}{P(K_n,\lambda)}

範例