# CSES Chess Tournament 題解與證明

:::success
題目

https://cses.fi/problemset/task/1697/
:::

## 演算法

不斷選取目前度數最大的點 $S$，假設度數為 $s$，與除了 $S$ 以外度數前 $s$ 大的人建邊，並繼續做下去直到所有人的度數都為 $0$，代表可以成功建圖。若演算法執行過程中發現有某個 $S$ 無法和度數前 $s$ 大的人建邊（例如：剩下的人不夠多），代表這不是合法的度序列。

## 正確性證明

假設 $A = \{s, t_{1}, t_{2}, \ldots, t_{s}, d_{1}, d_{2}, \ldots, d_{n}\}$ 是一個非嚴格遞減的序列，$A' = \{t_{1}-1, t_{2}-1, \ldots t_{s}-1, d_{1}, d_{2}, \ldots d_{n}\}$ 是一個度序列。

對 $A$ 來說可以對應到一個圖 $G$ 有點集 $\{S, T_{1}, T_{2}, \ldots, T_{s}, D_{1}, D_{2}, \ldots, D_{n}\}$，但我們尚不知道 $S$ 與其他點的相鄰情況，假設目前有兩種情況：
### Case 1
$S$ 與 $T_{1}, T_{2}, \ldots, T_s$ 相鄰。此時將 $G$ 刪去 $S$ 的新圖度序列就是 $A'$。若 $A'$ 可以構成簡單圖，則 $A$ 顯然也能構成簡單圖。
### Case 2
$S$ 至少與 $D_{x}\,(1 \le x \le n)$ 其中一個點相連，這代表存在一個 $T_{y}\, (1 \le y \le s)$ 使得 $S$ 與 $T_{x}$ 不相鄰。根據前提我們可知 $t_{y} \ge d_{x}$，我們再分兩個情況討論：
#### Case 2-1
$t_{y} = d_{x}$。我們可以將 $T_{y}$ 與 $D_{x}$ 交換，這樣不會使得 $A$ 改變。
#### Case 2-2
$t_{y} > d_{x}$。這代表存在一個點 $W$ 使得 $W$ 與 $T_{y}$ 相鄰，但 $W$ 與 $D_{x}$ 不相鄰。這樣我們可以把邊 $SD_{x}$、$WT_{y}$ 刪除，加上邊 $ST_{y}$、$WD_{x}$，這樣不會使得 $A$ 改變。

由上可知 $S$ 只要與任何一個非 $T_{1}, T_{2}, \ldots T_{s}$ 的點相鄰，則我們總有一個交換的方法使得讓 $S$ 多和 $T_{1}, T_{2}, \ldots T_{s}$ 其中一點相鄰，會到 Case 1。最終，$A$ 是否為合法度序列就由 $A'$ 決定，可以遞迴下去地做。

:::info
參考資料

- [其他度序列的性質](https://mathworld.wolfram.com/GraphicSequence.html)
- [證明方法](https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm)
:::

{%hackmd @temmie950807/r1KCzgjFh %}
{%hackmd @temmie950807/Prove_Style %}