---
tags: 成大高階競技程式設計 2021
---

# 2021 Week17 - Cover & Independent set

註：:bulb: 代表相對少見、較進階或與主題關聯性較低的內容，讀者可自行斟酌觀看。

---

# 點覆蓋（Vertex Cover）

graph {
    node [label=""];
    
    A -- B;
    B -- C;
    A -- C;
    A -- D;
    A -- E;
    A, C [style=filled];
}

點覆蓋是圖的一個點集合，使得圖上所有邊都至少有一個端點在集合之中。

## 最小點覆蓋（Minimum Vertex Cover）

最小點覆蓋即為所有點覆蓋中點數最少的。

<hr class=dashed>

## 二分圖最小點覆蓋（Minimum Vertex Cover in bipartite graphs）

graph {
    rankdir=LR;
    subgraph cluster_X {
        style=dashed;
        label="X";
        A, B, C, D;
    }
    subgraph cluster_Y {
        style=dashed;
        label="Y";
        a, b, c, d;
    }
    
    A:ne -- b [style=bold];
    B -- c [style=bold];
    C:ne -- c;
    C:se -- d [style=bold];
    A:n -- a;
    A:e -- c;
    A:se -- d;
    D:e -- d;
    A, c, d [style=filled];
}

<hr class="dotted">

### Kőnig's theorem

:::danger
在任意的二分圖中，[最大匹配](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Matching#%E6%9C%80%E5%A4%A7%E5%8C%B9%E9%85%8D%EF%BC%88Maximum-Cardinality-Matching%EF%BC%89)之邊數等於最小點覆蓋的點數
:::

> #### 證明
> > 令 $M$ 為一個最大匹配，而 $C'$ 為圖的一個點覆蓋
>
> $C'$ 的一個點最多覆蓋 $M$ 中的一條邊，所以得知 $|C'|\ge |M|$，
> 因此我們如果可以建構一個 $C$，使得 $|C|=|M|$，則 $C$ 就是最小點覆蓋。
>
> > 令 $F$ 為以 $X$ 的非匹配點為起點的 $M$-交錯路徑的邊集合，令 $Z$ 為 $F$ 的邊的端點的點集合
> >
> > > 對於一匹配邊 $e$ 的二端點 $u, v$，若 $e\in F$，則 $u, v\in Z$，若 $e\notin F$，則 $u, v\notin Z$。
> > > （前者很顯然是對的；若是 $u\in Z$，假設 $e\notin F$，那應該有一條非匹配邊 $u\in e'$ 且 $e'\in F$，但根據 $F$ 的定義，可得知 $e\in F$，與假設矛盾，因此透過反證法可確定後者之正確性）
>
> 若是讓 $C=(X\setminus Z)\cup(Y\cap Z)$，
> 對於任意一條邊 $e$，**若是 $e\in F$**，則 $e_Y\in (Y\cap Z)$；
> **若 $e\notin F$ 且 $e\in M$**，則 $e_X\notin Z$，也就是 $e_X\in(X\setminus Z)$；
> **若 $e\notin F$ 且 $e\notin M$**，因為 $e\notin M$，所以 $e_x$ 是匹配點，
> 且 $e_x$ 對應的匹配邊不在 $F$ 中（否則 $e\in F$），
> 所以 $e_X\notin Z$，$e_X\in(X\setminus Z)$；
> 因此 $C$ 是圖的一個覆蓋（$|C|\ge|M|$）。
>
> $(X\setminus Z)$ 皆為匹配點，因為 $X$ 的非匹配點都屬於 $Z$，
> $(Y\cap Z)$ 也皆為匹配點，因為若是 $Z$ 中有 $Y$ 的非匹配點，則代表有 $M$-可擴增路徑，
> 且匹配邊的二端點同屬於或同不屬於 $Z$，所以一條匹配邊最多一個端點在 $C$ 之中，
> 因此 $|C|\le|M|$。
>
> 綜合上述之結論，$|C|=|M|$，$C$ 就是一個最小點覆蓋，
> 且最大匹配之邊數等於最小點覆蓋的點數。
>
> > 以上圖為例，$F=\{\overline{Dd},\ \overline{dC},\ \overline{Cc},\ \overline{cB}\}$，$Z=\{D,\ d,\ C,\ c,\ B\}$，
> > 所以 $C=\{A\}\cup\{c,\ d\}$。

因此二分圖最小點覆蓋問題，可透過[二分圖最大匹配](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Matching#%E4%BA%8C%E5%88%86%E5%9C%96%E6%9C%80%E5%A4%A7%E5%8C%B9%E9%85%8D%EF%BC%88Maximum-Cardinality-Bipartite-Matching%EF%BC%89)求得，並且證明中也給出了一種建構方法，
可以找出一個最小點覆蓋。

pair<vector<int>, vector<int>> Konig(const vector<vector<int>>& adjx, const vector<int>& mx, const vector<int>& my) {
    vector<int> cx{}, cy{};
    queue<int> qu{}; vector<bool> vis(adjx.size());
    for (int x{0}; x < adjx.size(); ++x)
        if (mx[x] == -1) qu.push(x), vis[x] = true;
    while (!qu.empty()) {
        auto x{qu.front()}; qu.pop();
        for (auto& y : adjx[x]) {
            if (vis[my[y]]) continue;
            qu.push(my[y]), vis[my[y]] = true;
            cy.push_back(y);
        }
    }
    for (int x{0}; x < adjx.size(); ++x)
        if (!vis[x]) cx.push_back(x);
    return {move(cx), move(cy)};
}

---

# 邊覆蓋（Edge Cover）

graph {
    node [label=""];
    
    A -- B [color=gray];
    B -- C [style=bold];
    A -- C [color=gray];
    A -- D [style=bold];
    A -- E [style=bold];
}

邊覆蓋是圖的一個邊集合，使得圖上所有點都至少連接著集合之中的一條邊。

> 如果有度數為 $0$ 的點則不存在邊覆蓋，這邊就不再討論此情況。

## 最小邊覆蓋（Minimum Edge Cover）

最小邊覆蓋即為所有邊覆蓋中邊數最少的。

:::danger
最小邊覆蓋之邊數等於點數扣掉[最大匹配](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Matching#%E6%9C%80%E5%A4%A7%E5%8C%B9%E9%85%8D%EF%BC%88Maximum-Cardinality-Matching%EF%BC%89)之邊數
:::

> #### 證明
>
> > 令 $C'$ 為圖的一個邊覆蓋，而 $M$ 為一個最大匹配
>
> 讓每個點都對應到一條相鄰並在 $C'$ 的邊，則假設總共有 $e_2$ 條邊被 $2$ 個點對應，
> $e_1$ 條邊被 $1$ 個點對應，$e_0$ 條邊沒有被任何點對應，
> 我們知道 $e_2+e_1+e_0=|C'|$ 且 $2\times e_2+e_1=|V|$，得到 $|V|-e_2+e_0=|C'|$，
> $|V|-e_2\le|C'|$，而這 $e_2$ 條邊剛好是一個匹配，因此 $|V|-|M|\le|C'|$，
> 所以只要能夠找到一個 $C$，使得 $|C|=|V|-|M|$，$C$ 就是一個最小邊覆蓋。
>
> 透過最大匹配 $M$，對於所有的非匹配點，我們都隨便找一條與之相鄰的邊，
> 組成一個邊集合稱為 $N$，並且 $|N|=|V|-2\times |M|$，
> 讓 $C=M\cup N$，則 $|C|=|M|+|N|=|M|+|V|-2\times |M|=|V|-|M|$，
> 因此 $C$ 就是一個最小邊覆蓋，且最小邊覆蓋之邊數等於點數扣掉最大匹配之邊數。

最小邊覆蓋問題，則是可以透過[最大匹配](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Matching#%E6%9C%80%E5%A4%A7%E5%8C%B9%E9%85%8D%EF%BC%88Maximum-Cardinality-Matching%EF%BC%89)求得，上面也給出了一種建構方法，
可以找到一個最小邊覆蓋。

---

# （點）獨立集（Indepedent (Vertex) set）

graph {
    node [label=""];
    
    A -- B;
    B -- C;
    A -- C;
    A -- D;
    A -- E;
    B, D, E [style=filled];
}

獨立集是圖的一個點集合，集合中的點兩兩不相鄰。

## 最大獨立集（Maximum Independent Set）

:::danger
最大獨立集之點數等於點數扣掉最小點覆蓋之點數
:::

> #### 證明
>
> 獨立集中的點兩兩不相鄰，代表一條邊至多一個端點在集合之中，
> 所以一個集合是獨立集若且唯若其補集是點覆蓋。
>
> > 令 $I'$ 為一個獨立集，$C$ 為一個最小點覆蓋
>
> $|I'|+|I'^c|=|V|$，$|I'|+|C|\le|V|$，$|I'|\le|V| - |C|$，
> 所以如果能找到一個獨立集 $I$，使得 $|I|=|V| - |C|$，$I$ 就是一個最大獨立集。
>
> 讓 $I=C^c$，則 $|I|=|V| - |C|$，$I$ 就是一個最大獨立集，
> 且最大獨立集之點數等於點數扣掉最小點覆蓋之點數。

透過上面的證明可以知道，先找到一個最小點覆蓋，其補集就是一個最大獨立集。

---

# 邊獨立集（Indepedent Edge set）

graph {
    node [label=""];
    
    A -- B [color=gray];
    B -- C [style=bold];
    A -- C [color=gray];
    A -- D [style=bold];
    A -- E [color=gray];
}

邊獨立集是圖的一個邊集合，且集合中的邊兩兩不相鄰。

> **詳見[*匹配*](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Matching)**

---

# Reference

* Wikipedia - [Kőnig's theorem (graph theory)](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory))

<style>

hr.thin {
height: 0.5px;
}

hr.dotted {
border-top: dotted;
height: .0em;
color: #777777;
background-color: #ffffff;
}

hr.dashed {
border-top: dashed;
height: .0em;
color: #777777;
background-color: #ffffff;
}

/* Gradient transparent - color - transparent */
hr.gradient {
border: 0;
height: 1px;
background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0));
}

/* Flaired edges, by Tomas Theunissen */
hr.flaired {
overflow: visible;
height: 30px;
border-style: solid;
border-color: black;
border-width: 1px 0 0 0;
border-radius: 20px;
background-color: #ffffff;
}
hr.flaired:before { /* Not really supposed to work, but does */
display: block;
content: "";
height: 30px;
margin-top: -31px;
border-style: solid;
border-color: black;
border-width: 0 0 1px 0;
border-radius: 20px;
}

</style>