# 圖論 (3) ## 6/14 社課 ---- ## Outline - 歐拉路徑 - 樹重心 - 樹直徑 --- ## 歐拉路徑 一筆畫問題 ---- - 歐拉路徑：圖上每條邊洽走過一次的路徑 - 歐拉迴路：起終點向同的歐拉路徑 ---- ### 歐拉路徑存在性 無向圖： 恰存在 $0$ 或 $2$ 個度數是奇數的點 若為 $0$ 個則存在歐拉迴路 有向圖： 除了起終點之外 每個點的入度 $=$ 出度 而起點的出度會多 $1$，終點入度會多 $1$ 若所有節點入度 $=$ 出度，存在歐拉迴路 ---- ### 構造歐拉路徑 （存在歐拉路徑的條件下） 對**邊** DFS 也就是對於每個點，看他所連接的每一條邊 沒有走過就走下去 當所有可以走的邊都走完了（也就是離開一條邊） 這個點就可以丟到答案裡 最後得到的答案因為是倒過來的 將他反轉就可以得到一條歐拉路徑 ---- 實際的實作中 可以存每個點的編號 然後再開一個陣列紀錄每條邊是否走過 在有向圖中 可以開直接拿 `vector` 中的最後一個 然後直接 pop 掉 ---- ### [一筆畫問題](https://tioj.ck.tp.edu.tw/problems/1084) 求字典序最小的歐拉路徑 ---- 只要 DFS 編號最小的點就好 每進到一個點就把他的邊排序 ---- **範例 Code** ```cpp= #include<bits/stdc++.h> using namespace std; using pii=pair<int, int>; int m; vector<vector<pii>> e; vector<bool> vis; vector<int> ans; void dfs(int now){ sort(e[now].begin(), e[now].end()); // 要字典序最小 for(pii i:e[now]){ int to=i.first, id=i.second; if(vis[id]) continue; vis[id]=1; dfs(to); } // 這個點已經找沒有連著未走過的邊，加入歐拉路徑尾端 ans.push_back(now); } int main(){ while(cin >> m, m){ e.assign(501, vector<pii>()); vis.assign(m, 0); ans.clear(); for(int i=0, u, v; i<m; i++){ cin >> u >> v; // 存下每個邊的編號 e[u].push_back({v, i}); e[v].push_back({u, i}); } bool ok=0; // 是否找到歐拉路徑 for(int i=1; i<=500; i++){ if(e[i].size()%2){ // 存在奇點，設為起點 dfs(i); ok=1; break; } } if(!ok){ // 不存在奇點，找編號最小的點當起點 for(int i=1; i<=500; i++){ if(!e[i].empty()){ dfs(i); break; } } } reverse(ans.begin(), ans.end()); // 將序列反轉得到答案 for(int i:ans) cout << i << '\n'; cout << '\n'; } } ``` --- ## 樹重心 一棵樹的重心（？ ---- 某個點 把它拿掉之後 剩下的連通塊點數都不超過 $\frac{N}{2}$ ---- 白話一點 一棵樹上拿掉一個點 可能會讓圖分成很多塊 這幾塊互相不連接 但每一塊的節點數量都不會大於原圖數量的一半 ---- 一棵樹上一定有重心 一棵樹最多兩個重心 ---- #### 一些酷酷的性質 - 在一棵樹上多加一個點，重心最多移動一條邊 - 將兩棵樹用一條邊連接，新的重心會在原兩棵樹重心間的路徑上 ---- ### [樹重心裸題](https://cses.fi/problemset/task/2079) 求任意樹重心 怎麼求樹重心？ ---- 先隨便定根 計算每個子樹的大小 在 DFS 過程中到的每個點 若以他為根，則他的所有子樹就會是 一開始 DFS 順序中得到的他的所有子樹 以及一棵除了他的子樹外剩下的點所構成的樹 ---- 也就是說 假設以他為根的子樹大小為 $sz(v)$ 那麼假設將他定為整棵樹的樹根 他就會多出一個子樹 大小為 $N-sz(v)$ 這個動作被稱為 "**換根**" ---- 利用這個想法 我們可以在 DFS 的過程中 得到以每個點為根的樹 他的子樹大小為何 等價於將他拔掉之後 剩下的連通塊節點數量為何 若剩下的大小都不超過 $\frac{N}{2}$，他就是重心 ---- **範例 Code** ```cpp= #include<bits/stdc++.h> #define fastio ios::sync_with_stdio(0); cin.tie(0); #define F first #define S second using namespace std; using pii=pair<int, int>; int n, sz[1000005]; vector<int> e[1000005], ans; void dfs(int now, int pre){ sz[now]=1; int mx=0; // 以他為根的最大子節點子樹 for(int i:e[now]){ if(i==pre) continue; dfs(i, now); sz[now]+=sz[i]; mx=max(mx, sz[i]); } mx=max(mx, n-sz[now]); if(mx<=n/2) ans.push_back(now); // 若最大子樹大小不超過一半，這個點就是重心 } int main(){ fastio cin >> n; for(int i=0, u, v; i<n-1; i++){ cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } dfs(1, 1); // 隨便定根 cout << ans[0] << '\n'; } ``` --- ## 樹直徑 最長的一條路 ---- ### 用 DP 找樹直徑 對於一個點 樹直徑一定是 - 通過他 - 在他的其中一個子樹內 其中一個 ---- 所以我們可以**分治**！ 對於以每個點 $u$ 為根的子樹 有他的直徑 $dis(u)$、最大深度 $h_u$ 則 $dis(u)=\max\{dis(v), h_w+h_x+1\}$ 其中 $v,w,x$ 都是 $u$ 的子節點 ---- [裸題](https://zerojudge.tw/ShowProblem?problemid=b967) ```cpp= #include<bits/stdc++.h> #define fastio ios::sync_with_stdio(0); cin.tie(0); using namespace std; int n, dis=-1; vector<int> e[100005]; int dfs(int now, int pre){ int mx=0, se=0; for(int i:e[now]){ if(i==pre) continue; int dep=dfs(i, now); if(mx<dep){ se=mx; mx=dep; } else if(se<dep) se=dep; } dis=max(dis, mx+se); // 更新最大值 return mx+1; // 回傳子樹深度 } int main(){ fastio while(cin >> n){ dis=-1; for(int i=0; i<n; i++) e[i].clear(); for(int i=0, u, v; i<n-1; i++){ cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } dfs(0, 0); cout << dis << '\n'; } } ``` ---- 樹直徑還有 $2$ 次 DFS 的做法 寫起來比較簡單 常數比 DP 作法大一點 有興趣的可以查查看