# FINAL Exercise <font color=#ff00000>證明必考很重要</font>

###### tags: `MIDTERM`

## 2020 Graph Theory Final Exam Exercise

1. Prove or Disprove: If $T$ is minimum-weight spanning tree of weighted graph $G$, then $u,v$-path in $T$ is minimum weight $u,v$-path in $G$

>[name=Omnom][color=#00a000]考慮邊長1,1,1,2的梯形

>先disprove再說了
>[name=Conan][color=#0000ff]

3. Determine the minimum effort to trvael all the edges in $Fig.1$

[做法連結](https://hackmd.io/1ggnrQdKQ-qg129pur--gg#P34)

>[name=Omnom][color=#00a000]以上做法連結只是參考，此處太簡單應該用不到。
>Naïve方法就好

>[name=Neko][color=#FF00FF]如果要的話是要把k6弄出來喔?然後訂出每個pair?
>>[name=Omnom][color=#00a000]好像是這樣⋯⋯
>

4. Count the spanning trees in $Fig.2$. Draw all of them.

[單純計算數量的方式](https://hackmd.io/anobCEACS9axdBZk9L1tgg#P7-Matrix-Tree-Theorem)

>[name=Omnom][color=#00a000]將vertex編號會比較好找

5. Find out the single source shortest path from vertex S in $Fig.3$ by **Dijkstra's** algorithm. Draw the procedure step by step.

[Dijkstra](https://hackmd.io/anobCEACS9axdBZk9L1tgg#P1822-Dijkstra-Algorithm)


>[name=Omnom][color=#00a000]以下是個人解答，~~有誤還請幫忙指正~~
$\rightarrow$$\rightarrow$$\rightarrow$
$\rightarrow$$\rightarrow$$\rightarrow$

6. Determine the maximum number of matchings in the graph below

用老師最後一章投影片提到的算法
判斷是否還存在Augmenting Path

>[name=Omnom][color=#00a000]其中一種解
>因為完全找不到其他紅黑相間且頭尾是黑的augmenting path，所以答案是3

>其中一解
>
>[name=Conan][color=#0000ff]
>

>[name=Omnom][color=#00a000]好像也能用Hungarian algorithm處理
>$\pmatrix{ &a &b &c &d &e \\
f &&&&0 & \\ g &0 &&0 &&0 \\ h &0 &0 &&0 &0 \\ i &&&&0 & \\ j &&&&0 & }$
>最少3條直線($d,g,h$)可以包覆全部的0

## 報告的出題方向(考應用)

### Hungarian Algorithm

在$O(n^3)$時間中完成**bipartite** matching

[演算法流程](https://blog.csdn.net/u014754127/article/details/78086014)

[維基介紹](https://en.wikipedia.org/wiki/Hungarian_algorithm)

#### 應用：bipartite assignment

$e.g.$ graph vertex matching
人找工作
視網膜真假判別w
字跡比對等

### Ullmann Procedure

找到isomophic的子圖

[解釋較為清楚的連結](https://adriann.github.io/Ullman%20subgraph%20isomorphism.html#fn1)

[昶文提供](https://slideplayer.com/slide/5865095/)

>[name=Omnom][color=#00a000]概念簡單來說：
>如果vertices $v_i, v_j$彼此isomorphic，
>那麼neighbor也應當要isomorphic

#### 應用

>[name=Omnom][color=#00a000]可能和matching蠻相關的？

[參考連結](https://math.stackexchange.com/questions/120408/what-are-the-applications-of-the-isomorphic-graphs)
[有機化合物](https://www.sciencedirect.com/topics/chemistry/ullmann-reaction)
### Dependence Graph

通常用Directed Ascylic Graph (DAG)
表示彼此的dependency

#### 應用

[Topological sorting](https://en.wikipedia.org/wiki/Topological_sorting)

演算法講義內容

**DFS**

**BFS**

[維基超多example](https://en.wikipedia.org/wiki/Dependency_graph)

>
>偉哉演算法
>[name=Conan][color=#0000ff]
>

>[name=Omnom][color=#00a000]好險有修演算法