- まちがってたらごめんね。変なところあったら指摘してね。
木の直径とは
- 木における最大頂点間距離のこと
double-sweepで求める
アルゴリズム
- 木として$T=(V, E)$が与えられる
- ある頂点$u \in V$を選び、$u$を始点として最大距離となる終点$v \in V$を探し出す。
- 先ほど探し出した頂点$v$を始点として最大距離となる終点$w \in V$を探し出す。
- このとき、経路$v, w$の距離は木の直径となる。
証明
-
経路$v, w$が木での最長の経路となることを証明する。証明には背理法を使う。
-
経路$v, w$が木の最長経路とならないと仮定する。つまり、経路$v, w$より長い経路$a, b \in V$が存在すると仮定する。
-
木は頂点$a, b$の場所で大きく2通りに場合分けできる。
-
1つ目は$L = LCA(a, b)$が経路$u, v$上にあるときである。この場合を細かく(i), (ii)に分けて考える（図を参照）。
-
(i)について考える。以下の式より、$|ab|$以上となる$|vb|$が存在する。よって、この場合経路$a, b$は最長の経路ではない
|ab| = |aL| + |bL| \\
|aL| \leq |vL| \\
|ab| = |aL| + |bL| \leq |vL| + |bL| = |vb|
- (ii)について考える。(i)と同様に以下の式より、$|ab|$以上となる$|vb|$が存在する。よって、この場合経路$a, b$は最長の経路ではない
|ab| = |aL| + |bL| \\
|aL| \leq |vL| \\
|ab| = |aL| + |bL| \leq |vL| + |bL| = |vb|
- 2つ目は$L$が経路$u, v$上にないときである。これを細かくして(iii), (iiii)に分けて考える。
- (iii)について考える。$L_2=LCA(v, L)$とする。以下の式より、$ab$以上となる長さ$vb$が存在する。よって、この場合経路$a, b$は最長の経路ではない
|vL_2| \geq |aL_2| \\
|vL_2| > |aL| \\
|vL| > |aL| \\
|ab| = |aL| + |bL| < |vL| + |bL| = |vb|
- (iiii)について考える。以下の式より、以下の式より、$ab$以上となる長さ$vb$が存在する。よって、この場合経路$a, b$は最長の経路ではない
|uv| \geq |ua| \\
|uv| > |aL| \\
|vL| > |aL| \\
|ab| = |aL| + |bL| < |vL| + |bL| = |vb|
- はじめに経路$a, b$が最長の経路となると仮定した。しかし、(i)~(iiii)より、経路$a, b$が最長の経路ではないと証明した。経路$v, w$より長い経路$a, b$が存在するという仮定に矛盾が生じた。よって、木の直径は経路$v, w$の長さとなる。
コード
-
getTreeDiameter()を呼べば木の直径とその始点、終点が1通り求められる。
const int maxV = 111111;
vector<int> G[maxV]; // 頂点情報のみのグラフ
// treeDFS(親, 現在地, 根から現在地までの距離, 根からの最大の距離, 根から最大の距離となる頂点
void treeDFS(int from, int current, int dist, int &maxDist, int &maxVertex) {
// 距離と終点を更新
if (dist > maxDist) {
maxDist = dist;
maxVertex = current;
}
for (auto to : G[current]) {
// 逆流を防ぐ
if (to == from) continue;
treeDFS(current, to, dist + 1, maxDist, maxVertex);
}
}
void getTreeDiameter() {
int start = 0, end = 0, maxDist = 0;
treeDFS(-1, start, 0, maxDist, end);
start = end, end = 0, maxDist = 0;
treeDFS(-1, start, 0, maxDist, end);
printf("start: %d, end: %d, diameter: %d\n", start, end, maxDist);
}
直径を使って解く問題
メモ
- 直径は木DPでも求められるみたいなんだけど、木DPよくわからん。この辺の記事が良さげ。全方位木DPってやつらしい。
- double-sweepってアルゴリズム、ABC019のスライドに載ってたけどググっても出てこない。double-sweepは俗称みたいなもの？
- wからxへの最大の経路を$|wx|$とする。$|vw| \leq |wx|$だから$|vw|$が最大にならないのでは？と思ったけどそんなことはなかった。$a, b$は任意の頂点を表すので、$|ab|$が最大でないことを示せば$|vw|$が最大ということになった。
- 直径を使って解く問題、他にあったら教えてほしいです