# DS Adv Graph

{%hackmd theme-dark %}

## Critical Path

### AOV Network
* G = <V,E> 為有向圖
* V 為事件
* E 為工作執行順序
* 求合理的工作順序 -> Topo Sort

### AOE Network
* G = <V,E> 為有向圖
* V 為事件
* E 為工作
* Edge Weight 為工作花費時間
* Critical Path length：找到完成整個 Project 最長所需時間

## MFMC

### 最大流：在一張邊權不為負的有向圖求源點到滙點的最大流量
* Dinic：複雜度 O(V^2E)，先在每一層對 S 做 BFS，然後 DFS 找出增廣流
* ISAP：複雜度 O(V^3)，在找增廣的同時做分層圖

### 最大流最小割

* 先找出最大流
* 得到殘餘流量

### Ford-Fulkerson
* 對殘餘流量 DFS，還有殘餘流量就走，最後有走到的就是源點那邊的子圖，沒走到就是滙點的子圖

### Edmond-Karp
* 改 BFS (Shortest Path)，優化找殘餘流量的過程

## 二分圖
* 旅行商問題：如何經過每個節點後回到起點(NP-hard)
* 著色問題：NP-Complete