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

前一篇：【資工考研】DSA: 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^{\prime })$ 為
   $G$ 的一個 spanning tree，定義
   $w(T)=\sum _{e\in E^{\prime }}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=\{u,v\}$ 加入

$E^{\prime }$ ，其中

$u\in S,v\notin S$ ，想當然我們每次都挑 weight 最小的邊，並且保證

$S$ 維持 connected
直到所有頂點都放入

$S$ 了，

$E^{\prime }$ 中的邊即形成一個 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
確實，而且他們的時間複雜度也雷同，同樣受到 priority queue 實作的影響

＼	$\mathrm{Initialization}$	$\mathrm{Extract}-\mathrm{Min}()$	$\mathrm{Decrease}-\mathrm{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
其中 Kosaraju's algorithm 需要兩次 DFS ，而 Tarjan's algorithm 只需要一次 DFS 即可

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

1. 在 DFS 的過程中，維持陣列 parent ，紀錄各頂點之 parent
2. 如果頂點
   $u$ 是 DFS spanning tree 的 root (parent[u] == nullptr) 並且其子點數量
   $>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}[u]=min\{\mathrm{disc}[u],\mathrm{disc}[w]\}$ ，其中
   $w$ 是
   $u$ 的某個 ancestor ，且存在一條從
   $u$ 的 descendant 連回到
   $w$ 的 back edge

這邊

$\mathrm{low}$ 值是演算法核心，如果

$\mathrm{low}[v]\ge \mathrm{disc}[u]$ ，表示從

$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 ，滿足

$\mathrm{\forall }v\in V$ ，

$s$ 可達

$v$ 且

$v$ 可達

$t$ (

$s$ 的 in-degree 為

$0$ ，

$t$ 的 out-degree 為

$0$)

$\mathrm{\forall }u,v\in V$ 若

$(u,v)\in E$ 則

$(v,u)\notin E$
令

$c:E\to {\mathbb{R}}^{\mathbb{+}}$ 為 capacity function ，

$f:E\to {\mathbb{R}}^{\mathbb{+}}\cup \left\{0\right\}$ 為 flow function 滿足：

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

則稱

$G$ 為一個 flow network,

$f$ 為

$G$ 之一 flow
定義

$\left|f\right|=\sum _{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=\{(u,v)\in V\times V|c(u,v)-f(u,v)>0\}$

而我們會稱

$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^{\ast }\right|(\left|V\right|+\left|E\right|))=O(\left|f^{\ast }\right|\left|E\right|)$ 其中

$f^{\ast }$ 即 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^{\ast }\right|$ 有關啊？
是的，這牽扯到該方法的大問題，那就是它挑 augmenting path 的方法沒有特別設計過
該方法完全有可能會不斷挑一些很爛的 augmenting path 使得執行效率大幅降低
就算圖本身很小，如果

$\left|f^{\ast }\right|$ 很大，那效率還是會很爛，並且就算只是把

$\left|f^{\ast }\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=\mathrm{\varnothing }$ ，滿足
   $s\in S,t\in T$ ，則稱
   $(S,T)$ 為
   $G$ 之 cut
2. $c(S,T)=\sum _{u\in S}\sum _{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. $\mathrm{\exists }\mathrm{cut}(S^{\prime },T^{\prime }),\left|f\right|=c(S^{\prime },T^{\prime })$

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

Tip

$(S,T)$ 為 minimum cut

$\iff \sum _{u\in S}\sum _{v\in T}f(u,v)=\sum _{u\in S}\sum _{v\in T}c(u,v)$ 且

$\sum _{u\in S}\sum _{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^{\ast }$ ，我們亦可利用解 maximum flow 的技巧

首先要把

$G$ 變成一個 flow network

$G^{\prime }$
辦法就是在左右兩邊加 source 跟 sink ，source 連到

$V_1$ 中所有點 sink 連到

$V_2$ 中所有點
視所有邊 capacity 都是

$1$ ，利用 Ford-Fulkerson method 求解

$G^{\prime }$ 之 maximum flow，所求即

$G$ 之 maximum matching

因為 capacity 都

$1$ ，所以使用 Ford-Fulkerson method 的時間複雜度也就

$O(\left|V\right|\left|E\right|)$

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

claim:

$G$ 中存在一組 matching

$M^{\prime }$ 使得

$\left|M^{\prime }\right|=\left|f\right|\iff G^{\prime }$ 具有整數值的 flow

$f$
(

$\Rightarrow$)

$\mathrm{\forall }(u,v)\in M,\text{ 若 }(u,v)\in M^{\prime }$ 則令

$f(s,u)=f(u,v)=f(v,t)=1$ ，否則令

$f(u,v)=0$
則

$f$ 為

$G^{\prime }$ 之 flow 且可驗證得

$\left|f\right|=\left|M^{\prime }\right|$
(

$\Leftarrow$)
給定

$f$ 為

$G^{\prime }$ 之整數值 flow ，定義

$M^{\prime }=\{(u,v)|u\in V_1,v\in V_2,f(u,v)>0\}$
則

$M^{\prime }$ 為

$G$ 之一組 matching 且可驗證得

$\left|M^{\prime }\right|=\left|f\right|$

因此欲求

$G$ 之 maximum matching 相當於求

$G^{\prime }$ 之 maximum flow
並且由於

$G^{\prime }$ 中每邊的 capacity 皆為整數，故可以使用 Ford-Fulkerson method 求

$G^{\prime }$ 之 maximum flow ，而得

$G$ 之 maximum matching

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

• 【資工考研】DSA: Graph (1)
• 【資工考研】DSA: Graph (2)