# 數學專題報告:圖論
## 前言
<font size=6>為甚麼要學圖論?</font><br>
在我進入競賽圈的領域前，我對於圖論的認識僅止於二元樹、一筆畫問題等比較廣為人知的經典命題
進入競賽圈後，我發現了一塊新大陸，上面滿滿未知又有趣的知識等待我去學習
所以我想要跟各位分享這樣得到新知的喜悅感，於是我的專題主題就誕生了
## 甚麼是圖?
要了解圖論是甚麼，得要先有圖的概念，下面兩個是構成圖的要件
節點:圖最基本的物件
邊:連接兩個點的物件，有分有向邊與無向邊，差異只在與方向性是否受到限制
上面這個是非常標準的一個無向圖(表示全部的邊都沒有方向限制)
在圖裡面邊不是一個必要存在的要件 所以我們會說上面這張圖也算一種圖
## 圖論經典問題
### 一筆畫問題
相信大家都聽過歐拉這位偉大的數學家，他曾在一篇論文《柯尼斯堡的七橋》探討圖的一筆畫問題，也是第一次有正式論文探討圖論這個領域
我們可以用一點想像，把這張柯尼斯堡的地圖轉換成一張圖

題目就從"能不能不重複走到同一座橋並把所有的橋走完?"
變成"有沒有辦法不走到重覆的邊並把所有的邊走完?"
那我們能不能找到這樣的一個路徑?
.
.
.
.
答案是不我們做不到

但我們這是數學專題，我們必須給出嚴謹的證明，證明出為甚麼做不到
but how?
我們可以從一個觀點想 邊代表了甚麼意義?
邊不就代表我可以從這個點通出去也可以通進來嗎
我們先劃出堆點然後一筆畫隨意的亂走
走完後試著數每個點連上的邊數(也就是度數)

若某個點的度數是偶數，則有兩種可能
**1.作為起點或終點**
我們就想，出去的次數必定等於進來的次數，為甚麼?
原本有2k個跟該點連接且未被走過的邊，你出去以後會剩2k-1個 進來後剩2k-2 再出去後剩2k-3...
那我們又知道這個圖必定可以被一筆畫(畢竟是你剛剛自己亂畫出來的)
也就是這所有2k個邊都會被走過 所以最後出去與進來的次數必定相等
也就是說如果你畫的這個圖起點的度數是偶數 那起點必定等於終點
**2.作為中繼點(起終點以外的點)**
跟上面的推論類似，我們這2k個邊必定都會被走過，而他不是起點所以必定是從其他的某個點過來的
於是第一個被用掉的邊必定是走進這個點的 走進來剩2k-1個 出去後剩2k-2 再進來後剩2k-3...
而最後一個邊必定是被用來走出去的，也就是若這個點不是起點，那他必不是終點，正好與我們上面的推論相符

那考慮度數奇數的點呢?
**1.作為起點或終點**
我們假設這個點度數為2k+1且為起點，這2k+1個邊必定皆會被走過，則會出去k+1次，進來k次，也就是最後起點必定不等於終點
又若作為終點時，我們必定知道最後一個用掉的邊是進來，也就是進來k+1次，出去k次，也不與上一個結論衝突
**2.作為中繼點**
中繼點的定義也就是不為起點也不為終點，換言之就是進入次數等於出去次數
但可是我們不管怎麼分配 都沒有辦法找到一個分配方法使他的進去的次數等於出來的次數，所以度數為奇數的點不能做為中繼點

換言之只要一張圖
*度數為奇數的點數量=0或2*
則我們必定可以找到這張圖的一筆畫解$_{Q.E.D.}$
這也就可以解釋為甚麼柯尼斯堡的七橋不能一筆畫 因為太多"起終點了"

## 圖論經典演算法
### 戴克斯特拉演算法
最短路徑跟我們的生活息息相關，因為人性使然，驅使著我們尋找更短、更快的路徑

Dijkstra演算法的作法就是，我們先選一個起點，把它的距離設為0，其餘的點設為無窮大
把這個點放進一個叫做堆的資料結構當中

圖中這是最大堆，這個資料結構是利用二元樹來優化，做到$O(\log N)$插入、刪除(只能刪除最大(小)值)以及$O(1)$查詢當下最大(小)值

我們看上面的圖例，我們把1放進了堆然後又從堆裡面拿了出來，我們檢查與它相鄰的點，發現如果我用$dis_1+邊權_{1,2}$小於$dis_2$，於是我們更新$dis_2$為4，並把節點2的資料放進堆裡，其他的點也照做
下一輪拿出來的點是2，檢查一下相鄰的點，發現只有4，且沿著這條相鄰的邊走過去小於目前的$dis_4$，於是乎我們更新$dis_4$的值，並把(節點編號:4,與起點距離:5)的點放入堆中

但是堆沒有支援丟棄相同元素的資料，而且(4,5)與(4,6)這兩數對本來就不同，那我們若是不做點甚麼4這個節點的相鄰點勢必會被檢查到兩次，這樣會造成效率低下，要怎麼做才能挽救面臨`TLE`的風險?

我們只要跳過它就好
如果現在從堆裡拿出來的節點資料中它的後項，也就是與起點距離比$dis_i$還要大，表示我們必定已經檢查過他的周遭的點，所以我們把它從堆中拿掉後就不用去理它了

:::spoiler C++實現

#include<bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define endl "\n"
using namespace std;
const int N=2e5+5;
vector<pii>path[N];
vector<int>dis(N);
signed main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<m+1;i++)
    {
        int a,b,c;cin>>a>>b>>c;
        path[a].push_back(make_pair(b,c));
    }
    for(int i=1;i<=n;i++)dis[i]=1e18;
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    pq.push({0,1});
    dis[1]=0;
    while(pq.size())
    {
        int now=pq.top().S;
        int d=pq.top().F;
        pq.pop();
        if(dis[now]<d)continue;
        for(pii i:path[now])
        {
            int x=i.F,y=i.S;
            if(dis[now]+y<dis[x])
            {
                dis[x]=dis[now]+y;
                pq.push({dis[x],x});
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
    cout<<endl;
}

:::
複雜度$O(E\log V)$

### 克魯斯克爾演算法
最小生成樹可以拿來應用在建造陸地運輸網上，利用這個演算法可以找出一個所有點都連通且邊權和最小的一棵生成樹
Kruskal演算法的核心想法非常簡單，我們把邊利用其邊權由小到大排序好後，從邊權小的開始選入我們的生成樹裡，選到有n-1條邊時就表示我們已經找出這棵最小生成樹了
但有可能遇到一個狀況，也就是選到的邊所連通的兩點(設這兩點為$(x,y)$)已經互相連通了，這樣要怎麼處裡呢?
一樣非常簡單，只要跳過他不選就可以了，為甚麼呢?
利用反證法我們假設其中一個最小生成樹中存在該邊，要將這個邊放入生成樹中我們必須打斷方才選到該邊時$(x,y)$路徑中其中一條，又$(x,y)$路徑中任一條邊之權重必定$\le$該邊的權重，所以就算找到方法硬是選了這條邊然後繼續生成這棵樹，則最後的結果不會比原先的結果好

:::spoiler C++實現

#include<bits/stdc++.h>
#define endl "\n"
#define pb push_back
using namespace std;
const int N=2e5+5;
struct edge{int a,b,c;};
bool cmp(edge a,edge b){return a.c<b.c;}
vector<edge>E;
int p[N],num[N];
int fp(int now)
{
    if(now==p[now])return now;
    return p[now]=fp(p[now]);
}
void join(int x,int y)
{
    if(num[x]>=num[y])
    {
        num[x]+=num[y];
        p[y]=x;
    }
    else join(y,x);
}
signed main()
{
    int n,m;cin>>n>>m;
    for(int i=0;i<n+5;i++)p[i]=i,num[i]=1;
    for(int i=0;i<m;i++)
    {
        int a,b,c;cin>>a>>b>>c;
        E.pb({a,b,c});
    }
    sort(E.begin(),E.end(),cmp);
    int numedge=0;
    int ans=0;
    for(edge i:E)
    {
        if(numedge==n-1)break;
        int x=fp(i.a),y=fp(i.b);
        if(x!=y)
        {
            join(x,y);
            ans+=i.c;
            numedge++;
        }
    }
    cout<<ans<<endl;
}

:::
實現的時候運用了一個叫做並查集的資料結構，它可以讓我們快速查找($O(\alpha(N))$)任意一對(a,b)是否已經連通
總複雜度是$O(E\log E+E\alpha(V))$

## 特殊圖與其應用
### 樹
樹是一種很特別的圖，它有N個節點、N-1條邊且這N個點必定可以互相連通
最上面的那個節點我們稱之為根，在節點上一個節點叫父結點，最下面只有接到父結點的叫做葉子
而共同祖先則是兩個節點間的簡單路徑中離根結點最近的，也就是"最淺"的
#### 資料結構
##### 堆
我們來仔細看看堆這個資結
我們可以發現任意結點的權值大小必定大於它的所有子孫結點

加入一個節點的時候，我們直接把它加在深度最低的葉子下
這樣做完後我們往上"浮"，去跟它的父結點比較權值
如果底下的節點權值比較大，我們就把它跟它的父結點互換
並繼續往上比較直到它"浮到最高點"，或是直到它的權值比它的父結點小時，我們就停止更新

刪除最大值時，我們先把根給拔掉，再把最深的葉子放到根的位置
此時開始向下"沉"，我們讓它跟它的兩個子結點比較
若右結點比它大，則跟它互換，並繼續與它的子結點比較，一路比較到不需要再互換或已經換到葉子為止
反之亦然

我們可以看到它是一棵二元樹，且刪除與操作的行為特別使它最深的葉子深度不超過$\log N$
所以我們可以得到它的刪除與插入的複雜度為$O(深度)=O(\log N)$

C++的STL模板庫裡有寫好的現成堆，只要在標頭檔寫下

#include<queue>

就可以使用了
大致的使用方法如下

std::priority_queue<int,vector<int>,greater<int>>pq;
//宣告一個堆 注意第三個參數可以改成less<int> 而greater代表根會最小 less則相反
int a;cin>>a;
pq.push(a);//將變數a加入堆裡
cout<<pq.top()<<endl;//輸出堆裡面最小的值
pq.pop();//將根結點刪除

##### 線段樹
待完成...
### 二分圖
待完成...
#### 匹配問題
待完成...