# 【資工考研】DSA: Graph (3) MST + Articulation Point + Flow Network

[前一篇：【資工考研】DSA: Graph (2)](https://hackmd.io/@RyoukiWei/graph_2)

1. Graph Representations
2. BFS & DFS
3. Shortest Path Problem
4. Minimum Spanning Tree
5. Articulation Point
6. Flow Network

## Minimum Spanning Tree

給定 $G = (V,E)$ 為一個 undirect weighted graph

1. 若 $H$ 為 $G$ 的一個 spanning subgraph 且 $H$ 為 tree 則稱 $H$ 為 $G$ 的一個生成樹
2. 假設 $T = (V,E')$ 為 $G$ 的一個 spanning tree，定義 $w(T) = \sum\limits_{e\in E'}w(e)$ ，其中 $w(e)$ 為 $e$ 的 weight，稱 $w(T)$ 為 $T$ 之權重
3. 若 $T$ 為 $G$ 之 spanning tree 中擁有最小權重者，稱之為 $G$ 之最小生成樹 (minimum spanning tree)

簡單講，生成樹本身會是樹，並且頂點與原圖一樣，就差它可能從原圖上拔掉了一些邊
樹本身是 acyclic 的，並且至少需要有 $\left| V \right| - 1$ 條邊
求 MST 即要使這些邊的成本總和最小

MST 能夠應用在城市電網佈局或是交通建設等使成本最小化的問題上，是個重要的問題

### Kruskal's Algorithm

採用 greedy 的策略求出 MST

每次挑選 weight 最小的邊加入 MST $T$，過程中必須保證加入的邊不會使 $T$ 出現 cycle

struct Edge
{
    int from, to, weight;
};

struct Graph
{
    int num;
    std::vector<Edge> edges;

    explicit Graph(int n) : num(n) {}

    void addEdge(int u, int v, int w)
    {
        edges.push_back({u, v, w});
        edges.push_back({v, u, w});
    }
};

std::vector<Edge> kruskalMST(const Graph &g)
{
    if (g.num < 2)
        return {};

    DisjointSet<int> ds(g.num);
    std::vector<Edge> mst;
    mst.reserve(g.num - 1);

    // Sort all edges in non-decreasing order of their weights.
    // Sorting is essential to always pick the smallest edge first.
    auto edgesNew = g.edges;
    std::sort(edgesNew.begin(), edgesNew.end(),
              [](const Edge &a, const Edge &b)
              {
                  return a.weight < b.weight;
              });

    for (const auto &edge : edgesNew)
    {
        // If the edge connects two different components (no cycle), add it to MST.
        // The `unionSets` function returns true if the edge connects two different sets (no cycle).
        if (ds.unionSets(edge.from, edge.to))
        {
            mst.push_back(edge);
            if (mst.size() == g.num - 1)
                break;
        }
    }

    return mst;
}

這邊，我們使用 disjoint set 來輔助檢查
我們可以將 $T$ 中所有 component 視為一個 set，在檢查每次加入 $e = (u,v)$ 會不會產生 cycle 時，相當於判斷 $u$ 跟 $v$ 是否在同一個 set 中，若不屬於同個 set 表示可以加入 $e$

在 `unionSets` 我們就會去比 `find(u)` 是否等於 `find(v)` 了

以下提供一個簡易的 disjoint set 實作：

/**
 * @class DisjointSet
 * @brief A generic implementation of the Disjoint Set data structure with
 *        path compression and union by rank for efficient set operations.
 *
 * @tparam T The type of elements in the disjoint set. Typically, this will be an
 *           integral type such as int or size_t.
 */
template <typename T>
class DisjointSet
{
    static_assert(std::is_integral<T>::value, "This DisjointSet implementation requires an integral type.");

private:
    std::vector<T> parent;
    std::vector<int> rank;

public:
    /**
     * @brief Constructor, initialize disjoint set with `n` elements (`0` to `n-1`)
     * @param n The number of elements.
     */
    explicit DisjointSet(size_t n) : parent(n), rank(n)
    {
        std::iota(parent.begin(), parent.end(), 0);
    }

    /**
     * @brief Union operation by rank. Merges the sets containing elements `x` and `y`.
     * @param x An element in the first set to be merged.
     * @param y An element in the second set to be merged.
     * @return `true` if the sets were merged successfully, or `false` if `x` and `y`
     *         were already in the same set.
     */
    bool unionSets(T x, T y)
    {
        T rootX = find(x);
        T rootY = find(y);

        if (rootX == rootY) // Already in the same set
            return false;

        if (rank[rootX] < rank[rootY])
            std::swap(rootX, rootY);
        parent[rootY] = rootX;

        if (rank[rootX] == rank[rootY])
            ++rank[rootX];

        return true;
    }

    /**
     * @brief Find operation with path compression. Finds the root of the set containing `x`.
     * @param x The element whose set root is to be found.
     * @return The root of the set containing `x`.
     */
    T find(T x)
    {
        using UnsignedT = typename std::make_unsigned<T>::type;
        assert(static_cast<UnsignedT>(x) < parent.size() && "Index out of bounds");
        return parent[x] != x ? parent[x] = find(parent[x]) : parent[x];
    }
};

雖然排序需要 $O(\left| E \right|\lg \left| E \right|)$ 的時間，但如果邊不多 (通常啦，課本就這樣)，我們可以改說是 $O(\left| E \right|\lg \left| V \right|)$

disjoint set 所需時間是 $O(\left| E \right|\alpha (\left| V \right|))$ ，而 $\alpha (\left| V \right|)$ 成長非常緩慢

所以我們直接就說時間複雜度是 $O(\left| E \right|\lg \left| V \right|)$

### Prim's Algorithm

也是採用 greedy 的策略，但不同的是，我們每次從 $V$ 中任選一點形成集合 $S$ ，每次選取 $e = \left\{ u,v \right\}$ 加入 $E'$ ，其中 $u\in S, v\notin S$ ，想當然我們每次都挑 weight 最小的邊，並且保證 $S$ 維持 connected
直到所有頂點都放入 $S$ 了，$E'$ 中的邊即形成一個 MST

// Don't mind
struct pair_hash
{
    template <class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2> &pair) const noexcept
    {
        auto hash1 = std::hash<T1>{}(pair.first);
        auto hash2 = std::hash<T2>{}(pair.second);
        return hash1 ^ (hash2 << 1);
    }
};

struct Graph
{
    int num;
    std::vector<std::vector<int>> adjList;
    std::unordered_map<std::pair<int, int>, int, pair_hash> edgeWeights;

    struct Vertex
    {
        int id;
        int key;
        bool inMST;
        Vertex *pi;

        Vertex(int id) : id(id), key(INT_MAX), pi(nullptr), inMST(false) {}
    };

    std::vector<Vertex> vertices;

    Graph(int n) : num(n), adjList(n), vertices(n) {}

    void addEdge(int u, int v, int weight)
    {
        adjList[u].push_back(v);
        adjList[v].push_back(u);
        edgeWeights[{u, v}] = weight;
        edgeWeights[{v, u}] = weight;
    }

    int w(int u, int v) const noexcept
    {
        auto it = edgeWeights.find({u, v});
        if (it != edgeWeights.end())
            return it->second;
        return INT_MAX; // If edge doesn't exist, treat as ∞
    }

    struct CompareKey
    {
        bool operator()(const Vertex *u, const Vertex *v)
        {
            return u->key > v->key;
        }
    };
};

std::vector<Graph::Vertex *> primMST(Graph &g)
{
    for (int i = 0; i < g.num; ++i)
    {
        g.vertices[i].key = INT_MAX;
        g.vertices[i].pi = nullptr;
        g.vertices[i].inMST = false;
    }

    g.vertices[0].key = 0;

    std::priority_queue<Graph::Vertex *, std::vector<Graph::Vertex *>, Graph::CompareKey> pq;
    for (int i = 0; i < g.num; ++i)
    {
        pq.push(&g.vertices[i]);
    }

    std::vector<Graph::Vertex *> mstV;

    while (!pq.empty())
    {
        Graph::Vertex *u = pq.top();
        pq.pop();

        u->inMST = true;
        mstV.push_back(u);

        for (int v : g.adjList[u->id])
        {
            if (!g.vertices[v].inMST)
            {
                const int weight = g.w(u->id, v);
                if (g.vertices[v].key > weight)
                {
                    pq.push(&g.vertices[v]);
                    g.vertices[v].key = weight;
                    g.vertices[v].pi = u;
                }
            }
        }
    }

    return mstV;
}

你會發現，這演算法怎麼這麼像 [Dijkstra](https://hackmd.io/@RyoukiWei/graph_2#Dijkstras-Algorithm)
確實，而且他們的時間複雜度也雷同，同樣受到 priority queue 實作的影響

| ＼ | $\mathrm{Initialization}$ | $\mathrm{Extract-Min()}$ | $\mathrm{Decrease-Key}$ | Total |
| :---: | :---: | :---: | :---: | :---: |
| Array | $\theta (\left\| V \right\|)$ | $O(\left\| V \right\|^2)$ | $O(\left\| E \right\|)$ | $O(\left\| V \right\|^2)$ |
| Binary Heap | $\theta (\left\| V \right\|)$ | $O(\left\| V \right\|\lg \left\| V \right\|)$ | $O(\left\| E \right\|\lg \left\| V \right\|)$ | $O(\left\| V \right\|\lg \left\| V \right\| + \left\| E \right\|\lg \left\| V \right\|)$ |
| Fibonacci Heap | $\theta (\left\| V \right\|)$ | $O(\left\| V \right\|\lg \left\| V \right\|)$ | $O(\left\| E \right\|)$ | $O(\left\| V \right\|\lg \left\| V \right\| + \left\| E \right\|)$ |

### Borůvka (Sollin)'s algorithm

這個以考試來說偏冷門
簡單來說，就是改看成一群樹 (森林)，一開始樹都是只有各個頂點，我們一直合併樹的方式直到最後只剩一棵樹即為所求

它也是 greedy 策略，每次都挑成本最小的

時間複雜度也是 $O(\left| E \right| \lg \left| V \right|)$

下面是我大致寫的，應該是對的吧…… 如果我自己沒理解錯
(我對它也不熟)

struct Edge
{
    int from, to, weight;
};

struct Graph
{
    int num;
    std::vector<Edge> edges;

    explicit Graph(int n) : num(n) {}

    void addEdge(int u, int v, int w)
    {
        edges.push_back({u, v, w});
        edges.push_back({v, u, w});
    }
};

std::vector<Edge> boruvka(const Graph &g)
{
    int n = g.num; // number of components
    DisjointSet<int> ds(g.num);
    std::vector<Edge> mst;

    while (n > 1)
    {
        std::vector<Edge> cheapest(g.num, {-1, -1, INT_MAX});

        for (const auto &edge : g.edges)
        {
            const int u = ds.find(edge.from);
            const int v = ds.find(edge.to);

            if (u != v) // Edge connects different components
            {
                if (edge.weight < cheapest[u].weight)
                    cheapest[u] = edge;
                if (edge.weight < cheapest[v].weight)
                    cheapest[v] = edge;
            }
        }

        for (const auto &edge : cheapest)
        {
            if (edge.from != -1 && edge.to != -1)
            {
                const int u = ds.find(edge.from);
                const int v = ds.find(edge.to);

                if (u != v)
                {
                    mst.push_back(edge);
                    ds.unionSets(u, v);
                    --n;
                }
            }
        }
    }

    return mst;
}

因為它真的很冷門，如果不太會可以選擇跳過

### MST 常考觀念

MST 選擇題之類的啊，很愛考一些觀念，舉幾個：

1. 如果 $G$ 所有邊的權重皆不相同，則 MST 必定唯一；second best MST 不一定唯一。如果有相同權重 MST 可能不唯一 (所以上述幾種演算法得出的 MST 可能長得不一樣，不過權重和倒是一定一樣，畢竟是最小了)
2. 對 $G$ 任何 cycle $C$ ，如果 $C$ 有一個邊，沒有任何其他 $C$ 中的邊權重比它大，那麼該邊必定不屬於 $G$ 之任何一棵 MST
3. 下列敘述為 False： $G$ 中唯一最大的邊必定不在任何一棵 MST
4. 下列敘述為 False： $C$ 中唯一最小的邊必定屬於 MST
5. 圖之切集中唯一最小的邊必定屬於 MST
6. 圖中唯一最小的邊必定屬於 MST
7. 承上，該圖中唯一第二小的邊亦必在 MST 中

## Articulation Point

無向連通圖中，如果移除某頂點會圖的分量變多，該點稱為 articulation point (關節點)
去掉某頂點會使圖不連通，則稱為 cut vertex (切點)
兩者基本上是差不多的，我們以下就當一樣

cut vertex 的集合為 vertex cut (點切集)
定義 vertex connectivity (點連通度) $\lambda (G)$ 為最少移除多少頂點可使圖不連通
可想而知，$0\le \lambda (G) \le \left| V \right| - 1$
連通圖至少三頂點且沒有 cut vertex 時稱該圖為 biconnected

不存在 cut vertex 的無向連通圖為 biconnected graph
biconnected component 指為 biconnected graph 的 maximal induced subgraph (極大誘導子圖)

像網路結構之類的，如果有 articulation point ，表示該節點掛掉了會是大災難
所以確保其為 biconnected graph 是重要的

以下介紹找出 articulation point 的方法

### Naive Approach

最簡單的且直覺的想法，就是把每個頂點都移除看看，看會不會使圖不連通
為此需要遍歷圖 $\left| V \right|$ 次，時間複雜度會是 $O(\left| V \right|^2 + \left| V \right|\left| E \right|)$

以演算法來說，還有改進空間，然而對人眼判別來說，這樣的方法就相當夠用了，而且通常考試給的圖並不大
只是要你找出 articulation point 的話，用此方法反而更快

### Tarjan's Algorithm

我們之前有講過[如何找出所有 strongly connected component](https://hackmd.io/@RyoukiWei/graph_1#%E6%89%BE%E5%87%BA%E6%89%80%E6%9C%89-strongly-connected-component)
其中 Kosaraju's algorithm 需要兩次 DFS ，而 Tarjan's algorithm 只需要一次 DFS 即可

現在，雖然問題變成無向圖，但我們依舊能使用其想法：

1. 在 DFS 的過程中，維持陣列 `parent` ，紀錄各頂點之 parent
2. 如果頂點 $u$ 是 DFS spanning tree 的 root (`parent[u] == nullptr`) 並且其子點數量 $\gt 1$ ，則 $u$ 為一個 articulation point
3. 如果 $u$ 不是 DFS spanning tree 的 root 且其子點 $v$ 之子樹 (以 $v$ 為 root 的子樹) 中不存在任何 back edge 能連回 $u$ 所在的 DFS spanning tree 中的 ancestors ，我們需要將這些節點的 discovery time 記錄下來 (存在 `disc` 中)
4. 對每個 $u$ ，找出以 $u$ 為 root 的子樹中可以到達且最早被拜訪的節點 (discovery time 最小的節點)，我們定義 $\mathrm{low}\lbrack u \rbrack = \min\left\{ \mathrm{disc}\lbrack u \rbrack, \mathrm{disc}\lbrack w \rbrack \right\}$ ，其中 $w$ 是 $u$ 的某個 ancestor ，且存在一條從 $u$ 的 descendant 連回到 $w$ 的 back edge

這邊 $\mathrm{low}$ 值是演算法核心，如果 $\mathrm{low}\lbrack v \rbrack \ge \mathrm{disc}\lbrack u \rbrack$ ，表示從 $v$ 的子樹沒有 back edge 可以連回 $u$ 或是其 ancestors ，表示 $u$ 是 articulation point

enum class Color
{
    WHITE,
    GRAY,
    BLACK,
};

struct Graph
{
    int num;
    struct Vertex
    {
        int disc;
        int low;
        Color color;
        Vertex *pi;
    };

    std::vector<std::vector<int>> adjList;
    std::vector<Vertex> vertices;

    Graph(int n) : num(n), adjList(n), vertices(n) {}

    void addEdge(int u, int v)
    {
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
};

void DFSVisit(Graph &g, int u, int &time, std::unordered_set<int> &arPoints);

std::unordered_set<int> findArticulationPoints(Graph &g)
{
    for (auto vertex : g.vertices)
    {
        vertex.disc = -1;
        vertex.low = -1;
        vertex.color = Color::WHITE;
        vertex.pi = nullptr;
    }

    int time = 0;
    std::unordered_set<int> arPoints;

    for (int u = 0; u < g.num; ++u)
    {
        if (g.vertices[u].color == Color::WHITE)
            DFSVisit(g, u, time, arPoints);
    }

    return arPoints;
}

void DFSVisit(Graph &g, int u, int &time, std::unordered_set<int> &arPoints)
{
    auto &vertex = g.vertices[u];
    vertex.color = Color::GRAY;
    vertex.disc = vertex.low = ++time;

    int children = 0;

    for (int v : g.adjList[u])
    {
        auto &neighbor = g.vertices[v];

        if (neighbor.color == Color::WHITE)
        {
            neighbor.pi = &vertex;
            ++children;

            DFSVisit(g, v, time, arPoints);

            vertex.low = std::min(vertex.low, neighbor.low);

            // Case 1: Root node with multiple children
            if (!vertex.pi && children > 1)
                arPoints.insert(u);

            // Case 2: Non-root node
            if (vertex.pi && neighbor.low >= vertex.disc)
                arPoints.insert(u);
        }
        else if (&neighbor != vertex.pi)
            // back edge
            vertex.low = std::min(vertex.low, neighbor.disc);
    }

    vertex.color = Color::BLACK;
}

考慮下圖：


我們使用上述演算法來找出 articulation points

int main()
{
    Graph g(10);

    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 4);
    g.addEdge(3, 5);
    g.addEdge(5, 6);
    g.addEdge(5, 7);
    g.addEdge(6, 7);
    g.addEdge(7, 8);
    g.addEdge(7, 9);

    auto articulationPoints = findArticulationPoints(g);

    for (int vertex : articulationPoints)
    {
        std::cout << vertex << ", ";
    }
    std::cout << "\n";

    return 0;
}


## Flow Network

給定有向圖 $G = (V,E)$ ，其上有兩點 $s, t \in V$ ，其中 $s$ 稱作 source ， $t$ 稱作 sink ，滿足 $\forall v\in V$ ， $s$ 可達 $v$ 且 $v$ 可達 $t$ ($s$ 的 in-degree 為 $0$ ， $t$ 的 out-degree 為 $0$)
$\forall u,v\in V$ 若 $(u,v)\in E$ 則 $(v,u)\notin E$
令 $c: E \rightarrow \mathbb{R^+}$ 為 capacity function ， $f: E \rightarrow \mathbb{R^+}\cup \left\{ 0 \right\}$ 為 flow function 滿足：

1. **cpacity constraint**: $\forall u,v \in V, 0\le f(u,v)\le c(u,v)$
2. **flow conservation**: $\forall u\in V-\left\{ s,t \right\}, \sum\limits_{v\in V} f(v,u) = \sum\limits_{v\in V} f(u,v)$ (每點流入等於流出)

則稱 $G$ 為一個 flow network, $f$ 為 $G$ 之一 flow
定義 $\left| f \right| = \sum\limits_{v\in V} f(s,v)$ 為 $f$ 之 value

Flow network 直覺看來就像是許多管線串連的網路，它有個水源起點 $s$ ， $t$ 為終點池
那麼該怎麼求出從起點所能流出的最大總流量呢 (求 $G$ 上具有最大 value 之 flow)？這個問題便是 the maximum flow problem


## Residual Network

給定 flow network $G = (V,E)$ ，流量為 $f$
$G$ 之 residual network $G_f = (V,E_f)$ ，其中 $E_f = \left\{ (u,v)\in V\times V | c(u,v) - f(u,v) \gt 0 \right\}$

而我們會稱 $G_f$ 上 $s$ 到 $t$ 的 simple path 為 augmenting path

### Ford-Fulkerson method

1. 找 augmenting path $P$
2. $P$ 上最小的權重 $w$ 順邊 $-w$ 反邊 $w$
3. 重複 1. 跟 2. 直到不存在 $P$ 可找

其策略即 greedy ，我們每次能挑滿就挑滿，然後去更新 residual network

先寫好前置作業
`FlowNetwork` 的部份我覺得其實沒特別需要寫
雖然演算法過程中要兩邊更新 但實際上更新一邊就能看出東西了 所以我就寫個樣子

struct FlowEdge
{
    int from, to, flow, capacity;
};

struct FlowNetwork
{
    int num;
    std::vector<std::vector<int>> adjList;
    std::vector<FlowEdge> edges;

    FlowNetwork(size_t n) : num(n), adjList(n) {}

    void addEdge(int from, int to, int capacity)
    {
        edges.push_back({from, to, 0, capacity});
        adjList[from].push_back(edges.size() - 1);
    }
};

struct ResidualEdge
{
    int from, to, capacity;
};

struct ResidualNetwork
{
    int num;
    std::vector<std::vector<int>> adjList;
    std::vector<ResidualEdge> edges;

    ResidualNetwork(const FlowNetwork &G) : num(G.num), adjList(G.adjList)
    {
        for (const auto &edge : G.edges)
        {
            edges.push_back({edge.from, edge.to, edge.capacity - edge.flow});
            adjList[edge.from].push_back(edges.size() - 1);

            edges.push_back({edge.to, edge.from, edge.flow});
            adjList[edge.to].push_back(edges.size() - 1);
        }
    }

    void augmentFlow(int idx, int amount)
    {
        edges[idx].capacity -= amount;
        edges[idx ^ 1].capacity += amount;
    }
};

// Use DFS to find the augmenting path
bool findAugmentingPath(ResidualNetwork &Gf, int s, int t, std::vector<int> &path, std::vector<bool> &visited, int u)
{
    if (u == t)
        return true;

    visited[u] = true;

    for (int idx : Gf.adjList[u])
    {
        const auto &edge = Gf.edges[idx];
        if (!visited[edge.to] && Gf.edges[idx].capacity > 0)
        {
            path[edge.to] = idx;
            if (findAugmentingPath(Gf, s, t, path, visited, edge.to))
                return true;
        }
    }

    return false;
}

再來看演算法的部份就會簡單多了

int fordFulkersonMethod(const FlowNetwork &G, int s, int t)
{
    int maxFlow = 0;
    ResidualNetwork Gf(G);

    while (true)
    {
        std::vector<int> path(Gf.num, -1);
        std::vector<bool> visited(Gf.num);

        if (!findAugmentingPath(Gf, s, t, path, visited, s))
            break;

        int pathFlow = INT_MAX;
        for (int v = t; v != s;)
        {
            const int idx = path[v];
            pathFlow = std::min(pathFlow, Gf.edges[idx].capacity);
            v = Gf.edges[idx].from;
        }

        // Update Gf
        for (int v = t; v != s;)
        {
            const int idx = path[v];
            Gf.augmentFlow(idx, pathFlow);
            v = Gf.edges[idx].from;
        }

        maxFlow += pathFlow;
    }

    return maxFlow;
}

時間複雜度為 $O(\left| f^* \right|(\left| V \right| + \left| E \right|)) = O(\left| f^* \right|\left| E \right|)$ 其中 $f^*$ 即 maximum flow

例如下圖：


int main()
{
    FlowNetwork G(6);

    G.addEdge(0, 1, 10);
    G.addEdge(0, 2, 5);
    G.addEdge(1, 2, 4);
    G.addEdge(1, 3, 4);
    G.addEdge(1, 4, 5);
    G.addEdge(2, 4, 9);
    G.addEdge(4, 3, 6);
    G.addEdge(3, 5, 10);
    G.addEdge(4, 5, 8);

    int maxFlow = fordFulkersonMethod(G, 0, 5);

    std::cout << "Maximum Flow: " << maxFlow << "\n";

    return 0;
}


> [!Note]
> 依據原始問題的定義，每邊的 capacity 可為任意實數，但 Ford-Fulkerson method 只適用於每邊的 capacity 皆為有理數時

### Edmonds-Karp Algorithm

看上面 Ford-Fulkerson method 就會發現，這時間複雜度怎麼還跟問題答案 $\left| f^* \right|$ 有關啊？
是的，這牽扯到該方法的大問題，那就是它挑 augmenting path 的方法沒有特別設計過
該方法完全有可能會不斷挑一些很爛的 augmenting path 使得執行效率大幅降低
就算圖本身很小，如果 $\left| f^* \right|$ 很大，那效率還是會很爛，並且就算只是把 $\left| f^* \right|$ 放大，同個網路的效率也會有所不同

考慮下面這個極端情況：


如果每次都挑到經過 $(u,v)$ 再 $(v,u)$
可想而之會多跑超級多回
聽起來就不夠聰明對吧，給你挑，你一眼就知道怎麼挑

Edmonds-Karp 的想法就只差在，它在挑走哪條 augmenting path 時是用 BFS 挑的
所以他的時間複雜度為 $O(\left| V \right|\left| E \right|(\left| V \right| + \left| E \right|)) = O(\left| V \right|\left| E \right|^2)$

### Maximum Flow and Minimum Cut

給定 $G= (V,E)$ 為 flow network，$s$ 為 source， $t$ 為 sink

1. 若 $(S,T)$ 為 $V$ 之 partition ，即 $S\cup T = V$ 且 $S\cap T = \emptyset$ ，滿足 $s\in S, t\in T$ ，則稱 $(S,T)$ 為 $G$ 之 cut
2. $c(S,T) = \sum\limits_{u\in S}\sum\limits_{v\in T} c(u,v)$ 稱作 $\mathrm{cut} (S,T)$ 之 capacity

若 $f$ 為 $G$ 上的 flow，下列敘述等價：

1. $f$ 為 $G$ 之 maximum flow
2. $G_f$ 中不含 augmenting path
3. $\exists \mathrm{cut} (S',T'), \left| f \right| = c(S',T')$

也就是說，我們上面求 maximum flow 的同時，也能解出 minimum cut
考試都有可能問，要知道這兩個問題是同一件事

> [!Tip]
> $(S,T)$ 為 minimum cut $\Leftrightarrow \sum\limits_{u\in S}\sum\limits_{v\in T} f(u,v) = \sum\limits_{u\in S}\sum\limits_{v\in T} c(u,v)$ 且 $\sum\limits_{u\in S}\sum\limits_{v\in T} f(v,u) = 0$

### Maximum Matching

給定 $G = (V_1\cup V_2, E)$ 為 biparite graph (離散必考內容，不知道這是什麼的請趕快知道)，若 $M\subseteq E$ 滿足 $M$ 中的邊皆不具共同端點，則稱 $M$ 為 $G$ 之 bipartite matching
如果想求 $G$ 上的 maximum bipartite matching $M^*$ ，我們亦可利用解 maximum flow 的技巧

首先要把 $G$ 變成一個 flow network $G'$
辦法就是在左右兩邊加 source 跟 sink ，source 連到 $V_1$ 中所有點 sink 連到 $V_2$ 中所有點
視所有邊 capacity 都是 $1$ ，利用 Ford-Fulkerson method 求解 $G'$ 之 maximum flow，所求即 $G$ 之 maximum matching

因為 capacity 都 $1$ ，所以使用 Ford-Fulkerson method 的時間複雜度也就 $O(\left| V \right|\left| E \right|)$

簡單講一下為什麼可以這樣 (~~嘴砲證明法~~)：

> claim: $G$ 中存在一組 matching $M'$ 使得 $\left| M' \right| = \left| f \right| \Leftrightarrow G'$ 具有整數值的 flow $f$
> ($\Rightarrow$)
> $\forall (u,v)\in M, \text{ 若 } (u,v)\in M'$ 則令 $f(s,u) = f(u,v)=f(v,t)=1$ ，否則令 $f(u,v) = 0$
> 則 $f$ 為 $G'$ 之 flow 且可驗證得 $\left| f \right| = \left| M' \right|$
> ($\Leftarrow$)
> 給定 $f$ 為 $G'$ 之整數值 flow ，定義 $M' = \left\{ (u,v) | u\in V_1, v\in V_2, f(u,v) \gt 0 \right\}$
> 則 $M'$ 為 $G$ 之一組 matching 且可驗證得 $\left| M' \right| = \left| f \right|$
>
> 因此欲求 $G$ 之 maximum matching 相當於求 $G'$ 之 maximum flow
> 並且由於 $G'$ 中每邊的 capacity 皆為整數，故可以使用 Ford-Fulkerson method 求 $G'$ 之 maximum flow ，而得 $G$ 之 maximum matching

## 【資工考研】DSA: Graph 全系列

- [【資工考研】DSA: Graph (1)](https://hackmd.io/@RyoukiWei/graph_1)
- [【資工考研】DSA: Graph (2)](https://hackmd.io/@RyoukiWei/graph_2)