# 2020-05-22 Trees & Distance II
###### tags: `圖論`

[video](https://www.youtube.com/watch?v=YvbZzzWg2Ps&feature=youtu.be)
## P.3 Contraction


**Contraction** of edge $e$ in graph $G$ denoted as $G \cdot e$

$def:$ **replacement** of $u,v$ with single vertex whose incident edges excluding $e$ are incident to $u,v$

* Contracting an edge may produce multiple edges and loops.

## P.4

$Proposition$

$\tau(G)$ denote num of spanning tree

If $e \in E(G)$ isn't loop then $\tau(G)=\tau(G-e)+\tau(G \cdot e)$

## P.5

* When $e$ is a loop, we cannot apply this recurrence.

>[name= ][color=#00a000]一個 Graph 是 tree 的時候，就不繼續做recurrence ，直接回傳1，因為tree本身就是唯一的spanning tree

## P.6


>
>老師好像有打錯，修改成row 0 和col 0 比較符合圖中的狀況
>[name=Conan][color=#0000ff]

>[name=Omnom][color=#00a000][laplacian matrix](https://zh.wikipedia.org/wiki/调和矩阵) 又出現了😂
>[補充](http://www.csie.ntnu.edu.tw/~u91029/Graph3.html#5)

## P.7 Matrix Tree Theorem

$Theorem$

[矩陣樹定理](https://zh.wikipedia.org/wiki/矩阵树定理#举例)

* $$\tau (G) = (-1)^{s+t}\ det\ Q^*$$

$G$: loopless graph
$Q$: correspond $Laplacian ~Matrix$

$Q^*$: $Q$ delete a row and a column

## P.8 Graceful Labeling

$Def$:
Graph $G$ with **$m$ edges**.
把Vertices $V(G) \in \{0,...,m\}$作編號，$s.t.$ edge兩端編號相減取絕對值會會剛好$\{1,...,m\}$都出現

## P.9, 10

$Theorem\ 2.2.16:$ If tree $T$ of $m$ edges has graceful labeling, then $K_{2m+1}$ has a decomposition into $2m+1$ copies of $T$
$Fig.1$

$proof$:

>
>把左邊tree放到上面右邊的圖繞一圈
>[name=Conan][color=#0000ff]

$Fig. 2$

>[name=Omnom][color=#00a000]
>* $K_{2m+1}$中有$(2m+1)m$個edges
>* 將$Fig. 2$(單純示意)$K_{2m+1}$中的點標示後，可以發現左、右半部對稱，只要考慮$T$從其中一邊開始繞著$K_{2m+1}$旋轉即可
>* 將grace labeling後的$T$稍加排列，edge上的差值再減一後會是$Fig.1$中間隔的vertex數

## P.11, 12 Caterpillar

$def:$ **Caterpillar** is a tree $s.t.$ $\exists$ a path (**spine**) incident to every edge

$Theorem:$ A tree is a caterpillar $\iff$ doesn't contain tree Y

$proof$:

:::info
<font color=#000000>

把caterpillar的leaf砍掉，$\Delta (G')\leq 2$，也就是simple path，不可能變成Y

如果$G$砍掉leaf後變成$G'$，
$\Delta (G')\geq 3$ $~~iff~~$ $Y \subseteq G$ $\iff$ $\Delta (G')\leq 2$ $~~iff~~$ $Y \nsubseteq G$

把caterpillar的leaf砍掉，會剩下path $\iff$$\Delta (G')\leq 2$

</font>
:::

### Bonus
proof that if graph $G$ is **caterpillar** then $G$ has **graceful labeling**



>[name=Omnom][color=#00A000]graceful doens't infer it's caterpillar
>
>

:::spoiler informal proof
:::

## P.14 Kruskal's Algorithm

* Find the minimum spanning tree of a **weighted connected** graph

>[name=Omnom][color=#00a000]Prim: 從任意vertex開始grow tree，選連接tree 的最小的邊
>Kruskal: 一直選不會形成cycle的最小的edge

>以上皆須注意不能讓tree形成cycle
>Prim會像一棵tree一直長出來
>Kruskal則是多棵tree最後merge在一起
>[name=Conan][color=#0000ff]

## P.18~22 Dijkstra Algorithm
* 計算一個starting point到其他point的shortest path
* Only work with **nonnegtive** edge
* 演算法投影片範例:(參考用)


[流程細節參考第5題](https://hackmd.io/4O6Gj0ETRQOooKYLw051PQ?both#2020-Graph-Theory-Final-Exam-Exercise)

## P.24 Binary Decision Diagrams (BDD)
* Idea: skip redundant fragment of a binary decision tree.
* DAG(directed acylic graph) with outdegree of 2

## P.26 27

* 實線是1，虛線是0



# P.29
$\wp$-ordered binary decision diagram defined as:

$\mathfrak{B} = (V, V_I, V_T, succ_0, succ_1, var, val, v_0)$

# P.30

# P.31~34
* **Elimination rule**
- $v$ true或false都是$w$，直接$v,w$合併

* **Isomorphism rule**
- $v,w$ 和 $v',w'$數值分別一樣，故合併
- $v,w$的successor表現都一樣，可合併

>[name=Omnom][color=#00a000]垂直整合、水平整合(X

## P.35

* root都一樣比較好做

## P.36~38 ITE operator
* If-then-else: If $g$ then $f_1$ else $f_2$

$$ITE(g,f_1,f_2) = (g\land f_1) \lor (\neg g \land f_2)$$

* Shannon Expansion:

$$f= (z \land f|_{z=1}) \lor (\neg z \land f|_{z=0})$$
$$f_z=ITE(z,f_{succ_1(z)},f_{succ_0(z)})$$

## P.40~41
* Case 1: $B_1$ and $B_2$ have the same root.

## P.42~43
* Case 2: $B_1$ and $B_2$ have different root.

* $B_2$要再往下長

## P.44~52 Example(待修)

>[color=#0000ff]請先化成SOP形式用卡諾圖先看答案或驗算，否則你會很沒有方向
>邏設教過不要忘了
>結論: 卡諾圖真香w
>[name=Conan]

>[name=Omnom][color=#00a000]：「簡單布林代數化簡、加上Patrick Method就好啦」(所以他的貢獻在哪裡？)
>：「好的大一是大四的一半」

>[color=#FF00FF]樓上這句話真有道理
>[name=Neko]

| | 0 | 1 |
| ---- | --- | --- |
| 00 | 1 | 1 |
| 01 | 1 | 0 |
| 11 | 1 | 1 |
| 10 | 1 | 1 |

$-x_1+x_2-x_3$