ABC 318G Typical Path Problem

趣旨

AtCoder Beginner Contest 318 G Typical Path Problem を，(公式解説の方法でなく) block cut tree を使って解くこともできると思うのですが，根拠 (下の「命題」) が自分にとってあまり自明でなかったので，証明を書きます．

block cut tree や，関連する概念 (二重連結グラフなど) については，別の記事 を参照してください．

問題と解答方針

問題へのリンク

概略としては，連結単純無向グラフ $G$ と，その異なる3頂点 $A$, $B$, $C$ が与えられるので，
$B$ を経由して $A$ と $C$ を結ぶ単純パスが存在するかどうか判定せよ，というものです．
頂点数と辺の数は $2\times 10^5$ 以下．

block cut tree で解けそう，という感じはします．block cut tree 上で $A$ と $C$ を結ぶパスを考えておいて，$B$ がそこから大きく外れたら (間に関節点を入れなければならないような位置にあったら) ダメ．という感じです．ただ，base case (?) として，次の命題が成り立たないといけないわけですが，それがすぐに分かりませんでした (簡単なのでしょうか?)．

命題1

二重連結グラフ上に異なる3点 $A$, $B$, $C$ があるとき，$A$, $C$ を両端とする単純パスで $B$ を通るものが存在する．

これを認めれば，問題は，次のように解けます:

もとのグラフ上の頂点 $X$ に対し，block cut tree 上の頂点 $p(X)$ を，$X$ が関節点の時には，その関節点に対応する頂点として，そうでないときには $X$ が属するブロックに対応する頂点として定義する．

• $A$ と $C$ が同一ブロックに属するとき
  • $B$ もそのブロックに属するときには，命題 1 より Yes と判定する．
  • そうでない時には，$A$ から $B$ までのパスと $C$ から $B$ までのパスは同一関節点を通るので，No と判定する．
• $A$ と $C$ が同一ブロックに属さないとき
  • link cut tree 上で，$p(A)$ と $p(C)$ を結ぶ単純パス $\tilde\pi$ 上に，$B$ が属するブロックが存在するときには，Yes と判定する．理由は次の通り．$A$ と $C$ を結ぶ任意の単純パス $\sigma$ をとる．
    • $p(B)$ が $\tilde\pi$ 上にあるときには，$\sigma$ 上に $B$ が存在する．
    • そうでないときには，$\tilde\pi$ 上の，$B$ が属するブロックの直前と直後の 関節点を $D$, $E$ とする．$D$, $E$ は $\sigma$ 上にある．$D$, $B$, $E$ に対して命題1を適用して得られるパスで，$\sigma$ の，$D$ から $E$ までの部分を差し替えれば，題意を満たすパスが得られる．
  • そうでない時には，$A$ から $B$ までのパスと $C$ から $B$ までのパスは同一関節点を通るので，No と判定する．

ということで，以下，命題1を証明します．

命題1の証明

補題を準備します．

補題2

(3点以上からなる単純) 二重連結グラフ $G = (V, R)$ は，サイクルから出発して，すでに構成された2点を結ぶ単純パスを追加することで構成される．正確には次の通り:
以下を満たす $V$ の部分集合 $V_0, V_1, \ldots, V_k$ ($k \geq 0$) が存在する．$V_i$ が導出するグラフを $G_i$ とするとき

• $V = \bigcup \{V_i \mid i = 0, 1, \ldots, k\}$
• $V_i \cap V_{i + 1}$ は，2点 $p_i$, $q_i$ からなる集合
• $|i - j| \geq 2$ のときは，$V_i \cap V_j = \varnothing$
• $G_0$ はサイクル
• $G_{i + 1}$ は，$p_i$ と $q_i$ を端点とする単純パス
• 各辺$pq$ について，$p, q \in V_i$ となる $i$ が存在する．

補題2の証明

まず，$V_0$ を作る．このために異なる3点，$x, y, z \in V$ をとる．$G$ は連結なので，一般性を失うことなく，$y$ と $x$ を結ぶ単純バスと $y$ と $z$ を結ぶ単純パスが取れる．これらのパスに共通に現れる点がある場合には，それを $y$ に取り直してパスを短くしていくことにより，$x$ と $z$ を結ぶ単純パスで，その上に $x$, $z$ のいずれとも等しくない点 $y$ があるものが取れる．$G$ は二重連結なので，$y$ を取り除いても $x$ と $z$ を結ぶパスがある．これらを用いて$x$, $y$, $z$ をその上に持つサイクル $C$ がとれる．$C$ 上の隣接しない2点 $p$, $q$ で，辺で結ばれているものがある場合には，それをショートカットしてサイクルを短くしていくことにより，そのような2点のないサイクルを作成することができる．これを $V_0$ とすれば，$G_0$ はサイクルになる．$V_0$ の大きさは3以上であることに注意する．

$V_m$ まで構成できたとして，$U_m := \bigcup \{V_i \mid i = 0, 1, \ldots, m\}$ とする．$V \setminus U_m \neq \varnothing$ であれば，$x \in V \setminus U_m $ をとる．$y \in U_m $ をとって，$y$ から $x$ に至る単純パスを取る．このパス上にあって$U_m$ に属する最後の点を改めて $y$ とし，$U_m$ 上にあって $y$ に隣接する点を $z$ とする．$G$ は二重連結なので，$z$ から $x$ に至る単純パスで，$y$ を通らないものがある．このパス上にあって $U_m$ に属する最後の点を $w$ とする．パス $y - x - w $ を，上でサイクルを作成したときと同じような方法で短くすることで，$V_{m + 1}$ を構成することができる．(終)

命題1の証明

補題2にいう構成に関する帰納法で，次の2つを証明する．$U_i := \bigcup \{V_i \mid i = 0, 1, \ldots, i\}$ とする．

• (あ) $U_i$ 上に異なる3点 $A$, $B$, $C$ をとると，$A$, $C$ を端点とする単純パスで，$B$ を通るものが存在する．
• (い) $U_i$ 上に異なる4点 $A$, $B$, $C$, $D$ をとると，$A$ と $C$，$B$ と $D$ を結ぶパスで共通部分を持たないものが存在するか，もしくは，$A$ と $D$，$B$ と $C$ を結ぶパスで，共通部分を持たないものが存在する．

$i = 0$ のときは，サイクルだから明らかである．$i + 1$ の場合は，丁寧に場合分けしてできる．文章で書くのは手間がかかるので，図で済ますことにする．