# 2020-05-29 Chinese Postman & Ch3 (I) Matchings and Factors

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

[影片連結](
https://www.youtube.com/watch?v=ufTd8UrlxS0&list=PL8xY3250v6CR_mnR5_qh06WNMpqe7Ljav&index=2&t=0s)

## P.2 Chinese Postman Problem

* Seek a closed walk of minimum total length that uses all the edges.

>[name=Omnom][color=#00a000]traveling salesman：每個點至少走一次。
>Chinese Postman：每個邊至少走一次

## P.3,4

* If only two odd vertices, use Dijkstra's algorithm to find the shortest path between them.
* 有$2k$個 odd degree的點的話，就要兩兩用Dijkstra's algorithm找他們的shortest path，這時畫出輔助圖就是$2k$個點的complete graph，然後在complete graph中找出可以讓所有點的都可以兩兩一組配對最小總和的weight，(依講義範例是1配6，3配9)，最後再把這些邊加回去原本要找postman problem的graph


>[name=Omnom][color=#00a000]因為是看總和，所以不能用Kruskal的方式判斷

>[name=Omnom][color=#00a000]任意simple graph不會有奇數個odd vertices

## P.5 Matchings and Factors

* Matching是邊所形成的集合(以下記為$M$)，$M$任意邊沒有重複的端點
* $Def$: $M-saturated$：點有配對到就是saturated
* perfect matching:所有點都有配對到
* 註:講義的範例都不是perfect matching

## P.6

* Perfect matching$\Rightarrow$maximum matching，只是說可能會有不只一種配對的方式
* 反過來不一定，maximum可以看做是所有maximal情況底下挑出最好的，但不代表可以perfect matching

>[name=Omnom][color=#00a000]maximal: 在特定初始條件，所能找到最大的
>maximum:所有初始條件中，真正達到最大的

## P.7,8

* $Def$:
1. $M$-alternating path:
屬於M和不屬於M的edges交錯形成
2. $M$-augmenting path
一種$M$-alternating path，不過是unsaturated endpoints
3. Symmetric difference
$M _\Delta M'= (M-M')\cup(M'-M)$
>[name=Omnom][color=#00a000]就是Xor的樣子
>[Set](https://hackmd.io/TMUHk2TSROSo7BW8o7Ppqg#Set-Definition)

* Example:
$M _\Delta M'$得出的結果是粗線和細線但不包括重複的edge(e)

## P.9
* $Lemma$: Components of $M _\Delta M'$ is either path or even cycle

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

maximum degree: $\Delta(F)$
$\Delta (F)\leq 2$: $\rightarrow$ path or cycle
$∵ \Delta (M) , \Delta (M') \leq 1$
交錯的原因：$M-M'$是在$M$中，不能相鄰，同理$M'-M$
如果cycle是odd會造成最後的edge會被分到同一個matching裡，這違背matching的定義，所以不可能有odd cycle
</font>
:::

## P.10,11

* $Theorem \ 3.1.10$
Matching $M$ in graph $G$ is maximum $\Leftrightarrow$ $G$ has no $M$-augmenting path



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

$P ~~iff~~ Q \Leftrightarrow \neg P ~~iff~~ \neg Q$

$i.e.$ Matching $M$ in graph $G$ is NOT maximum $\Leftrightarrow$ $G$ has $M$-augmenting path

$\Leftarrow$:
by switching edges
$\Rightarrow$:
$|M'|>|M| \rightarrow |M'-M|>|M-M'|$
& by [Lemma](https://hackmd.io/1ggnrQdKQ-qg129pur--gg?both#P9)
$∴ \exists$ path with end-edges in $M'-M$ $\rightarrow$ $M$-augmenting path
</font>
:::

## P.12~14 Hall’s Matching Condition

* $Hall's~Theorem$:
$X,Y$ bigraph $G$ has a matching saturates $X$ $\Leftrightarrow$ $|N(S)| \geq |S|,\forall S\subseteq X$


$pf$ <font color=#ff0000>(待修)</font>
:::info

<font color=#000000>

$\Rightarrow$:(反證法)$P \Rightarrow Q$
Suppose $G$ has a matching that saturates $X$, and $|N(S)|\ngeq |S|$，根據pigeonhole原理，$|S|$如果大於$|N(S)|$，那$S$一定會有點會無法配到，因此矛盾。


$\Leftarrow$:$\neg P\Rightarrow \neg Q$
$i.e.~$: $X,Y$ bigraph $G$ has **no** matching saturates $X$ $\Rightarrow$ $\exists S\subseteq X,~s.t.~|N(S)| \ngeq |S|$

$M$是maximum matching 但沒辦法saturate所有的$X$，由
$Theorem \ 3.1.10$得知說$M$沒有augmenting path，所以$T$ is saturated.(如果$T$沒有saturated，代表會有augmenting path)
$|N(S)| = T = |S-\{u_1,...\}| \ngeq |S|$
(沒有解釋得很好，求大神補充)
</font>

:::

## P.15

* $Corollary\ 3.1.13$
$\forall k>0$, $k$-regular $X,Y$-bigraph has a perfect matching

* $pf$

:::info

<font color=#000000>

1. $|X|=|Y|$
[<font color=#ff0000> 2020-04-10 P.37</font>](https://hackmd.io/QIz8EtcKRqWANklnF4S-Fw#P37-Vertex-Degree-and-Counting-Conti)

2. let $S \subseteq X$
$m$ edges from $S$ to $N(S)$
$m=k|S| ∵ k$-regular
$m \leq k|N(S)|$ : $m$ edges對應到$N(S)$，從$N(S)$出發計算$k|N(S)|$ edges會包含前述的$m$ edges
satisfy Hall's Condition

combine 1. 2. Q.E.D.
</font>

:::

## P.16,17 Vertex Cover

* $Def$
set $Q \subseteq V(G)$，和$Q$相連的edge構成$E(G)$
* $|M|\leq |Q|$
* 一個點最多只能照顧一條有matching的edge


## P.18


證明optimal的情況: $|M|=|Q|$，$M$: maximum matching，$Q$: minimum size vertex cover

$pf$

:::info

<font color=#000000>

note: $|M| \leq |Q|$
用contradiction，假設$|M|= |Q|$不是optimal
1.
M 不是maximum matching，代表會有M'比M更大，違反不等式
2.
Q 不是minimum size vertex cover，代表會有Q'比Q更小，違反不等式

所以$|M|= |Q|$是optimal
</font>

:::

## P.19,20 <font color=#ff0000>絕對考 </font>
* $Theorem~ 3.1.16$
If $G$ is bipartite, then $|max ~ Matching|= |min ~ Vertex ~ Cover|$



For H':

$Q = R\cup T=R\cup (T-S)\cup S$
$Q'=R\cup (T-S)\cup N(S)$
if $|N(S)|$<$|S|$, 違反Q是最小的vertex cover的前提
因此, $|N(S)|\geq |S|$，符合Hall's condition，代表H'裡有matching $M_2$能saturate所有的T