---
# System prepended metadata

title: 2020-05-22 Trees & Distance II
tags: [圖論]

---

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


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

![](https://i.imgur.com/5FxD6hH.png =80%x)

**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)$
![](https://i.imgur.com/a8SlJHw.png =80%x)





## P.5
![](https://i.imgur.com/wXCj2Ia.png =80%x)

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



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


## P.6

![](https://i.imgur.com/GBvdqvr.png)


>
>老師好像有打錯，修改成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$
![](https://i.imgur.com/k0LKOGj.png =70%x)$Fig.1$

$proof$:


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

![](https://i.imgur.com/XNDq1Cv.jpg =30%x)$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
![](https://i.imgur.com/LN3UNEP.png)

$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**

![](https://i.imgur.com/BjJ49iS.png)

![](https://i.imgur.com/YpsbKBg.jpg =60%x)


>[name=Omnom][color=#00A000]graceful doens't infer it's caterpillar
>![](https://i.imgur.com/C3gvt9t.png =60%x)
>

:::spoiler informal proof
![](https://i.imgur.com/qe4DyqM.png)
:::



## 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
* 演算法投影片範例:(參考用)
![](https://i.imgur.com/GZNJD0M.png)

![](https://i.imgur.com/sc1YqPC.png=60%x)

[流程細節參考第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


![](https://i.imgur.com/igNj64G.png=80%x)

![](https://i.imgur.com/7WoAaoj.png=80%x)



# 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$合併
        ![](https://i.imgur.com/ia2xyXT.png)

* **Isomorphism rule**
    - $v,w$ 和 $v',w'$數值分別一樣，故合併
        ![](https://i.imgur.com/UNOtOIz.png)
    - $v,w$的successor表現都一樣，可合併
        ![](https://i.imgur.com/ASeP9xW.png)

>[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.
![](https://i.imgur.com/icRDZ9L.png =80%x)
![](https://i.imgur.com/Fa2vezQ.png =50%x)


## P.42~43
* Case 2: $B_1$ and $B_2$ have different root.
![](https://i.imgur.com/HsqdQjK.png =80%x)
![](https://i.imgur.com/TDY7FkL.png =50%x)

* $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$