大綱

• 各種圖
• 各種問題
• 中間穿插各種題目

如果有時間的話

• 線性規劃
• 趣題選講

其實就是很一般的圖論而已，也沒有什麼「進階」的。

圖論關鍵

• 知識 - 多記結論
• 應變 - 臨場發揮
• 拿紙出來用力畫啊

圖的種類

樹

樹的定義

有各種版本

• 沒有環的連通圖。
• 沒有環，且加一條邊就會有環。
• 任兩個點都有唯一的簡單路徑。這通常是出題著要出樹的題目，不想直接寫。

樹的子樹區間

先看一個題目

先觀察一下！

重點就是如何把一棵樹壓平

把樹壓平

int time_stamp = 0;
void dfs(int u) {
  start[u] = time_stamp;
  for (v: adj[u]) {
    dfs(v);
  }
  end[u] = ++time_stamp;
}

Example

樹分治

• 先講解一下題目。
• 這種跟路徑有關的問題通常有兩種做法， 一種是直接枚舉兩個端點。TLE。 一種是枚舉 LCS (或說路徑上一點)。
• 先說一下這題枚舉 LCS 大致作法。
• 用普通分治解說一下複雜度，說明最大的子樹不能太大。

int dfs(int v) {
    int total = 0, biggest = 0;
    for (u: adj[v]) {
        int t = dfs(u);
        biggest = max(biggest, t);
        total += t;
    }
    biggest = max(biggest, V - total - 1);
    return total + 1;
}

Time complexity

\[ T(n) = \sum T(n_i) + f(n) \]

\[ T(n) \approx f(n) \log n \]

回到原來那一題

重點: 如何合併

啟發式合併

樹分治要找重心，很煩。

在適當的條件下可以用啟發式合併，不用找重心，DFS 下去合併上來就好了。

回到原來那一題

樹鍊剖分

把所有樹上的邊分成輕/重鍊。

• 每個點往他最大子樹連的邊是重邊。
• 每個點往他最大子樹連的邊是輕邊。

小結

把重邊開成線段樹等等。

輕邊直接算答案。

Link-cut tree

把重邊用 Splay tree, treap 等等可以 split 的資料結構維護。

可以拔邊

平面圖

平面圖的定義

存在一個畫在平面的方法使得任兩條邊至多只在頂點相交。

比如正八面體是平面圖。但 \( K_{3, 3} \) 不是。

• 畫正八面體，不是立體的嗎？
• 所有多面體都是平面圖，投影。
• K33 常見的題目，井接水管。

性質一： 邊很少

• 說明「面」
• 證明 th2， 3F < 2E。
• 平均概念說明 th3.

每次都找度數最小的那個點。

枚舉完這個點就拔掉。

拔了這個點之後還是一個平面圖。

性質二： Forbidden Graph

• K5 證明 => 歐拉。
• K3,3 證明 => 沒有 3 環。

競賽圖

競賽圖的定義

「有向完全圖」

有沒有可能無解？

一定有環？

• 無解 => 最無聊的情況， 1 > 2 > 3
• 若無環 => 總有最大的 (SCC)
• 有環 => 3 環。

二分圖

二分圖的定義

可以分成兩團 \( A, B \) 的圖。同在一團的兩個點 \( u, v \) 沒有邊。

也可以說是能黑白染色的圖。

判斷一個圖是不是二分圖

黑白染色。

令 \( b_i = \sum a_i \) ，題目等於跟你講 \( b_i, b_j \) 是否同奇偶。

你跟我一樣 \( \implies \) 併查集

不一樣呢？

• 做前綴和。 sum(a_i) = b_j - b_i
• 先考慮同奇偶。
• 不同奇偶，多一個點。

圖的問題

Complexity classes

我們都希望所有問題都可以在 Polynomial time 完成。

事與願違，有些問題一直找不到多項式演算法，又證不了不存在。

假設我們有個超強的電腦。

Nondeterministic Turing machine

幸運值 Max, 永遠選到最快到終點的一條搜索路徑。

普通電腦多項式可以解的就叫 P, Nondeterministic Turing machine 可以在多項式解的就叫 NP

NP = P ?

NPC

NP 裡最難的一些問題就叫做 NPC

如果這些問題在 P ，所有 NP 問題都在 P， P = NP

Cook-Levin Theorem

2-SAT

給你一個像以下的式子

布林恆等式

\[ A \lor B \iff \lnot A \rightarrow B \iff \lnot B \rightarrow A \]

\[ A \to B, B \to C \quad \vdash \quad A \to C \]

• -> = 則
• A or B = 沒有 A 一定要 B ，舉個例子說明。

• 一致就是不會自相矛盾
• A -> not A 慘
• 舉一下剛剛的例子。

建模

也就是這些 \( \square \to \square \) 不能讓 \( x_i, \lnot x_i \)在同一個環

SCC，用 tarjan 等等演算法 \( \ord{n} \)

怎麼轉成 2-SAT

• x_i or x_i
• x_i or x_j
• not x_i or not x_j
• not x_i or not x_i

3-SAT

雖然只差一點，但是個 NP 問題。

Coloring

• 點塗色：把每個點塗一個顏色，使得任兩個相鄰的點都不同色。
• 邊塗色：把每個邊塗一個顏色， 使得一個點出去的邊都不同色。

都是 NPC Problem

點著色

• deg k 的圖一定可以用 k+1 個顏色塗。
• 幾乎已經對了，可能是完全圖嗎？
• 跟平面圖那題很像！

邊著色

• deg k 的圖一定可以用 k+1 個顏色塗。
• 邊就沒有那麼顯然了。
• 概念複雜，我們用下面這個題目介紹。

答案是 \( d \).

一個邊一個邊加上去。

• 如果兩個人有共同缺的顏色 -> easy.
• 如果沒有 設 x, y 塗 x
• 另一個點出去 x 邊改 y
• 另一個點出去 y 邊改 x ...
• 只會回到原來的點 or 可以塗。

Euler path

Example

有解的條件

觀察一個路徑 \( v_1 \to v_2 \to \cdots \to v_n \)

每一個中間走到的點 \( +2 \) ，兩端 \( +1 \)。

Algorithm

vector<int> ans;
void dfs(int v) {
    for (e: adj[v]) {
        if (not e.visit) {
            dfs(e.dest);
        }
    }
    ans.push_back(v);
}

• 把原始的邊和目標的邊做 Xor
• 小心連通的陷井。

Hamiltonian path

一條路徑走過所有的點恰好一次。

NPC Problem。

通常的做法是狀態壓縮 DP， \( \ord{2^n n^2} \)

Matching

幫每個點做配對，一個點只能配一次。

也可以想成是一些不相交的邊集。

二分圖上的匹配問題。

可以轉成 Flow 來解。

也可以用交錯路徑來想。

交錯路徑

一個匹配是最大匹配若且為若他沒有交錯路徑。

一般圖匹配

交錯路徑上會有奇環

縮花，非常複雜。

帶權完美匹配

二分圖可以轉成 Cost flow。

一般圖可以先找一個完美匹配在找負環。

或著點數小的時候可以狀態壓縮 DP。

• 通常會要求最大匹配。
• 定義負環。

很像 Euler cycle。

• 把他補成沒有奇點。
• 一次補兩個點。補外面的點不會比較好。
• 用最短路來補。
• Matching

一些相關的問題

• 最大獨立點集：一個最大的點集 \( V' \) 使得裡面的點都不相鄰。其大小記做 \( I(G) \)。
• 最大匹配數：前面定義過了。其大小記做 \( M(G) \)。
• 最小點覆蓋：最小的一個點集，使得所有的邊都至少與點集裡的一個點相鄰。其大小記做 \( C_v(G) \)。
• 最小邊覆蓋：最小的一個邊集，使得所有的點都至少與邊集裡的 一個邊相鄰。其大小記做 \( C_e(G) \)。

• 互不衝突的點。
• 很像壓紙。

• 點覆蓋的補集就是獨立點集。
• 先找一個最大匹配，補成邊覆蓋。 M + M + V - 2M = V

Counting

Prüfer sequence

• 1 2 1 2 6
• 最後一定是最大的數。

• 用扣的
• 慢慢 DP
• 第一個點的連通塊
• A[n] = 2^C(E, 2) - sum A[k] C(v, k-1) 2^C(v-k-1, 2)

• V^3
• 枚舉 E
• 合併起來 E Sqrt(E)

• 用扣的

Linear Programming

Problem description

example

Maximize \( x_1 - 2 x_2 + x_3 \)

Subject to \[ \begin{align} x_1 + x_2 - x_3 & \leq 7 \\ -x_1 - x_2 + x_3 & \leq -7 \\ x_1 - 2 x_2 + 2 x_3 & \leq 4 \\ x_1, x_2, x_3 & \geq 0 \\ \end{align} \]

Problem description

Maximize \( \mathbf{c} \cdot \mathbf{x} \)

Subject to \[ \mathbf{A} \mathbf{x} \leq b, \; \mathbf{x} \geq \mathbf{0} \]

Example - s-t shortest path

Min \( d_t \)

Subject to \[ \begin{align} d_v & \leq d_u + w(u, v) \\ d_s & = 0 \\ \end{align} \]

Dual Problem

Maximize \( \mathbf{c} \cdot \mathbf{x} \) Subject to \[ \mathbf{A} \mathbf{x} \leq b, \; \mathbf{x} \geq \mathbf{0} \]

Minimize \( \mathbf{b} \cdot \mathbf{y} \) Subject to \[ \mathbf{A}^T \mathbf{y} \leq c, \; \mathbf{x} \geq \mathbf{0} \]

\[ \mathbf{c} \cdot \mathbf{x} = \mathbf{b} \cdot \mathbf{y} \]

Example - Dual problem of weighted matching

Simplex

A non-polynomial algorithm to solve linear programming.

Slack form

Maximize \( 3x_1 + x_2 + 2x_3 \) Subject to \[ \begin{align} x_1 + x_2 + 3x_3 & \leq 30 \\ 2x_1 + 2x_2 + 5x_3 & \leq 24 \\ 4x_1 + x_2 + 2 x_3 & \leq 36 \\ x_1, x_2, x_3 & \geq 0 \\ \end{align} \]

Slack form

Maximize \( 3x_1 + x_2 + 2x_3 \) Subject to \[ \begin{align} 30 - x_1 - x_2 - 3x_3 & = x_4 \\ 24 - 2x_1 - 2x_2 - 5x_3 & = x_5 \\ 36 - 4x_1 - x_2 - 2 x_3 & = x_6 \\ x_1, x_2, x_3, x_4, x_5, x_6 & \geq 0 \\ \end{align} \]

Maximize \( 3x_1 + x_2 + 2x_3 \) Subject to \[ \begin{align} 30 - x_1 - x_2 - 3x_3 & = x_4 \\ 24 - 2x_1 - 2x_2 - 5x_3 & = x_5 \\ 36 - 4x_1 - x_2 - 2 x_3 & = x_6 \\ \end{align} \]

Let us increase \( x_1 \). How much can we?

結論

• 這個 form 被 \( n \) 個變數決定。
• 當 \( \mathbf{c} \) 每個分量都小於 \( 0 \)，就是 最佳解
• 此時的 \( \mathbf{c} \) 是 dual problem 的答案。