# 2020-06-05 Chinese Postman & Ch3 (II) Matchings and Factors

###### tags: `圖論`

[影片連結](https://www.youtube.com/watch?v=jmuG3wT7cBw&feature=youtu.be)

## P.2 Independence nnumber

* $Def$
max size of independent set
* **Not** always equal the size of a partite set
## P.3 (<font color=#ff0000>符號重要</font>)

* $Notation$
$\alpha(G)$ : max independent set size(點的子集)
$\alpha'(G)$ : max matching size(邊的子集)
$\beta(G)$ : min vertex cover size(點的子集)
$\beta'(G)$ : min edge cover size(邊的子集)

>[name=Omnom][color=#00a000]
>$\alpha$看的是max
>$\beta$看的是min cover
>
>有「$'$」的是邊的子集
>否則為點的子集

* $Lemma ~ 3.1.21$:
$S \subseteq V(G)$ is independennt set $\Leftrightarrow \bar S$ is vertex cover, and hence $\alpha(G)+\beta(G)=n(G)$

$pf$
:::info
<font color=#000000>

$S$ is an independent set ⇒ every edge is incident to at least vertex of $\bar S$ .
$\bar S$ cover all edges ⇒ no edges joining vertices of $S$.
Thus, every maximum independent set is the complement of a minimum vertex cover.

</font>
:::

## P.4~8
$Theorem ~ 3.1.22$:
* If $G$ is a graph **without isolated vertices**, then $\alpha'(G)+\beta'(G)=n(G)$

* 思路:









$pf$

:::info
<font color=#000000>

1. <font color=#df0000>$\alpha'(G)+\beta'(G) \leq n(G)$</font>

$M$: maximum matching
給定一個maximum matching $M$，讓edge cover = $n(G)-|M|$。edge cover = $n(G)-2|M|+|M|$的意思是當edge cover選到有matching的edge時，就會選到$|M|$個，剩下的vertex數量就會是$n(G)-2|M|$個，因為當選到有matching的edge時，就會解決掉2個vertex，剩下沒被挑到的點所選到的edge都會和M的其中一點是有相連的，所以要再加回$|M|$。透過maximum matching所造出來的edge cover = $n(G)-|M|$，這裡不能保證edge cover是minimum，所以會得出$\beta'(G) \leq n(G)-\alpha'(G)$，會寫成小於等於是因為edge cover在挑的時候一定會至少是minimum edge cover。

~~>[name=Omnom][color=#00a000]"vertex cover"是不是應該改成edge cover？~~

>[name=Conan][color=#0000ff]已更改
2. <font color=#df0000>$\alpha'(G)+\beta'(G) \geq n(G)$</font>

給定一個minimum edge cover $L$，讓matching size = $n(G)-|L|$。
$L$: minimum edge cover
$|L|=\beta'(G)$

考慮$k$個disconnected star構成$L$
則$|L|=n(G)-k$ (不算中心，算star的端點數)

matching size為$k$ (一個star只能找一邊matching)

$\Rightarrow n(G)-|L| = n(G)-\beta'(G) = k \leq \alpha'(G)$(找出來的matching必定小於等於maximum matching)
$\Rightarrow \alpha'(G)+\beta'(G) \geq n(G)$
</font>
:::

## P.9

$Corollary$
$G$ is a bipartite graph with no isolated vertices,
then $\alpha(G) = \beta'(G)$.

$pf$

:::info
<font color=#000000>

By [<font color=#ff0000>$Lemma ~ 3.1.21$</font>](#P3-符號重要) & [<font color=#ff0000>$Theorem ~ 3.1.22$</font>](#P.4~8)

$\alpha(G ) + \beta (G) =n(G)= \alpha'(G ) + \beta ' (G)$

By [<font color=#ff0000>$Theorem ~3.1.16$</font>](https://hackmd.io/1ggnrQdKQ-qg129pur--gg#P1920-絕對考-)
bigraph: maximum matching = minimum vertex cover
$\alpha'(G)=\beta(G)$

$\Rightarrow \alpha(G)=\beta'(G)$

</font>
:::

## P.10~11 Dominating Set

dominating set 本身是點集合，支配的也是點，靠的是所有不在dominating set的點都會和他是neighbor


## P.12~15 Augmenting Path Algorithm (Hopcroft-Karp)

[影片連結1](https://www.youtube.com/watch?v=lM5eIpF0xjA)
[影片連結2](https://www.youtube.com/watch?v=HTJjGw3HCBM)

>[name=Omnom][color=#00a000]結果發現Hungarian algorithm好像也行
>matrix中，有連線就給0，其餘給1或$\infty$