# 竹科實中H202 33廖丞胤 上學期自主學習期末報告 主題:圖論

## 前言:

最一開始是想要利用自主學習這個機會來多學一點東西，而我本身剛好稍微有在練習演算法競賽的題目，加上自己對圖論的興趣比較濃厚，所以我就選擇了這個主題。

## 本學期學到了:

### [最低共同祖先 LCA(Lowest Common Ancestor)](https://hackmd.io/@H1deonbruH/ryoM0co_F)

我們引入倍增的想法 假設一個節點的父節點為$f_{i,0}$ 也就是i節點往上$2^0$個節點
那我們再用一點動態規劃的技巧 很顯然的我們可以得出一個下列式子
$f_{i,j}=f_{f_{i,j-1},j-1}$
用白話文講就是你往上$2^j$會等於你往上$2^{j-1}$後又再往上$2^{j-1}$
那有了這個陣列後我們把要求的兩個點中最深的那個拉到跟另一個一樣的高度
因為我們剛剛求完了$f$ 所以我們可以用倍增的方法在$O(\log N)$時間內做到
拉到相同高度後去二分搜需要拉高多少
如果拉到兩個節點都相同 表示有可能是LCA抑或是已經超過LCA 此時就不要把他往上拉
反之則將兩個節點都拉升
結束後再拉升一次即為LCA

如果我們在先前就愈處理好每個節點的深度 從這張圖就可以很直觀的看出
任兩點$i,j$的距離會是$h[i]+h[j]-2\times h[LCA(i,j)]$
:::spoiler 倍增
也就是把一個數用二進位表示後 第i個位數若為1則表示這個數在拆分成數個$n$互不相同的$(2^n)$時
必會有一個$n$為$i$ 而一個數$N$以二進制表後會有$\log N$個位數
:::

### [強連通分量 SCC(Strongly Conected Components)](https://hackmd.io/@H1deonbruH/H1h0IFzIF)

強連通分量內任兩點$i,j$必可找到$i\rightarrow j$與$j\rightarrow i$的路徑
而我們可以利用DFS演化出來的Tarjan演算法來快速的求出各個SCC
Tarjan的作法即:
先給定目前的節點一個$dfn$值(表示被遍歷到時的序號)
接下來維護其有向子樹中$dfn$的最小值$low$
如果所有的子節點都遍歷過了 且該節點的$dfn=low$
那麼這個節點就會是一個SCC中最早被遍歷到的點
SCC中剩餘的點就會是子節點的遍歷中 所有走到過的點

### [匈牙利演算法&二分圖最大匹配](https://hackmd.io/@H1deonbruH/SJhVlFQFt)

利用匈牙利演算法算出大量交疊的男女關係中最多可以配到多少對
而匈牙利演算法的核心概念就是增廣路徑
也就是不管對方是否已經有配對了 就去拆散他跟他的對象 然後再找他原本對像能否找到配對
可以的話就表示這樣做可以找到新的配對 所以就這樣安排
不行的話就表示拆開他們也不會讓全體的匹配數增加 把他們復原後尋找下一個可以的對象
對每個點都這麼做一次後最後的配對數必然最大

### [輕重鍊剖分](https://hackmd.io/@H1deonbruH/ry62oY2ct)


把樹切成一條條的鍊狀，鍊要往下連的時候優先連到"以那個節點為根的子樹內節點數最大"的那個節點
每次往下走剩下的節點數量必小於原本的$\frac{1}{2}$
那麼如果這樣做 一個點往下走的路徑必可以被拆成$\log N$數量級條鍊
任兩點間的所有節點即可以被表示成$\log N$數量級條鍊
而這麼大費周章的把樹切成一條條鍊就是為了要做一些動態的路徑維護及查詢
在這些鍊上套上一些資料結構如BIT、線段樹、樹堆等
就可以達到在$O(N+Q\log^2N)$內在線查詢、修改任兩點間的資訊(距離、最小最大值、XOR值等)

## 還在學或未來想學的

### 樹堆

二元樹和堆的結合
利用隨機的性質可以在期望值$O(\log N)$做到區間最大值、改值、反轉等變態的操作

### 樹分治

在樹上做分治 每次找到重心後每個子樹的大小不超過原本的一半
用來維護樹上的距離操作問題

### 帶權二分圖最優匹配

跟二分圖最大匹配有點類似 但是每對配對都有一個權值
最優匹配的意思就是要找到一個權值和最大的匹配

###

# 結語
一個學期一下就過去了，這學期算是有成功，學到了很多新的知識與技巧，雖然沒有原本計畫單上的那麼多，但我還是很開心能學到這麼多有趣的演算法，非常感謝老師，總是能夠提出一些有趣的主意讓我激盪出更多的想法。下個學期我會試著把我所學到的東西在生活中做應用，希望能夠學到更多有趣的新知識。