Ark's Blog

引っ越しました→ https://blog.arkark.dev/

ようこそ

線形空間𝔽₂^V上の問題に対する連結グラフから全域木への帰着

数学 アルゴリズム 競プロ

連結無向グラフが与えられたとき、それが線形空間 \mathbb{F}_2^V上の問題であれば、連結グラフから全域木に帰着できるかもしれないという話です。着想は

の解説から得ました。想定解の一部に「連結グラフの問題を全域木の問題に帰着」している箇所があります。この記事は、これを数学的に理解するためのものです。

想定読者

  • グラフや木の定義を知っている。
  • 学部１年程度の線形代数の知識がある。

問題を見ていなくてもわかる構成にしているつもりですが、一度問題を解いた上でこの記事を読むと、読みやすいと思います。

TL;DR

準備

定義

G=(V, E) を連結無向グラフとしたとき、各 e \in E に対して次を定義します：

\begin{align} \mathbf{f}_e := \left( \mathbb{1}_{\{v \in e\}} \right)_{v \in V} \in \mathbb{F}_2^{V} \end{align}

ここで、 \mathbb{1}_{\{\text{cond}\}} は指示関数です。

問題の定式化

この定義を用いると、与えられた問題は次のように形式化できます：

  • 入力：
    • G=(V, E)：連結無向グラフ
    • \mathbf{b} = (b_v)_{v \in V} \in \mathbb{F}_2^V
  • 出力：
    • 次を満たす A\subset Eが存在するか？ \begin{align} \mathbf{b} + \sum_{e\in A} \mathbf{f}_e = \mathbf{0} \end{align}
    • 存在するならばそのような Aを構成せよ。

目標

上で形式化した問題を次の問題に帰着することが今回の目標です。

  • 入力：
    • G=(V, E)：連結無向グラフ
    • \mathbf{b} = (b_v)_{v \in V} \in \mathbb{F}_2^V
  • 出力：
    • Gの任意の全域木 T=(V, D) をとる*1。
    • 次を満たす A\subset Dが存在するか？ \begin{align} \mathbf{b} + \sum_{e\in A} \mathbf{f}_e = \mathbf{0} \end{align}
    • 存在するならばそのような Aを構成せよ。

線形空間 \mathbb{F}_2^V への抽象化

\mathbb{F}_2^Vは、体 \mathbb{F}_2 上の線形空間とみなすことができます。

また、ベクトル集合 X \subset \mathbb{F}_2^V が張る空間を \langle X \rangle と表記します。

問題の形式化 revised

よって問題は、次のように言い換えられます：

  • 入力：
    • G=(V, E)：連結無向グラフ
    • \mathbf{b} = (b_v)_{v \in V} \in \mathbb{F}_2^V
  • 出力：
    • \mathbf{b} \in \langle\{\mathbf{f}_e \mid e \in E \} \rangle を満たすか？
    • 満たす場合、次を満たすような (c_e)_{e\in E} \in \mathbb{F}_2^E を構成せよ。 \begin{align} \sum_{e\in E} c_e \mathbf{f}_e = \mathbf{b} \end{align}

全域木への帰着

書き換えた問題を眺めると \langle\{\mathbf{f}_e \mid e \in E \} \rangle を張るベクトル集合（辺集合）についてのみ考えれば十分ということがわかります。

ところが、次の定理より全域木の辺集合は、それに該当します。

定理

G の任意の全域木 T=(V, D) に対して次が成り立ちます：

\begin{align} \langle\{\mathbf{f}_e \mid e \in E \} \rangle = \langle\{\mathbf{f}_e \mid e \in D \} \rangle \end{align}

証明

\langle\{\mathbf{f}_e \mid e \in E \} \rangle \supset \langle\{\mathbf{f}_e \mid e \in D \} \rangle は E \supset D より明らかなので、 \langle\{\mathbf{f}_e \mid e \in E \} \rangle \subset \langle\{\mathbf{f}_e \mid e \in D \} \rangle を示せば良い。

任意に \mathbf{x} \in \langle\{\mathbf{f}_e \mid e \in E \} \rangle をとる。このとき \begin{align} \sum_{e\in E} c_e \mathbf{f}_e = \mathbf{x} \end{align} を満たす (c_e)_{e\in E} \in \mathbb{F}_2^Eが存在する。また、 T=(V, D) は G=(V, E) の全域木なので、各 e = \{l, r\} \in E に対して T 上に lと rを端点にもつパスが存在し、そのパスの辺集合を P_e \subset D とおく。このとき、 \mathbb{F}_2 上の演算を考えると \begin{align} ^\forall e\in E,\, \mathbf{f}_e = \sum_{e' \in P_e} \mathbf{f}_{e'} \end{align} が成り立つ。よって \begin{align} \mathbf{x} &= \sum_{e\in E} c_e \mathbf{f}_e \\ &= \sum_{e\in E} \left( c_e \sum_{e' \in P_e} \mathbf{f}_{e'} \right) \\ &\in \langle\{\mathbf{f}_e \mid e \in D \} \rangle \end{align} が成り立つ。

以上より \langle\{\mathbf{f}_e \mid e \in E \} \rangle = \langle\{\mathbf{f}_e \mid e \in D \} \rangle が示された _\blacksquare

帰着

\langle\{\mathbf{f}_e \mid e \in E \} \rangle = \langle\{\mathbf{f}_e \mid e \in D \} \rangle が示されたので、元の問題は次のように書き換えられます。

  • 入力：
    • G=(V, E)：連結無向グラフ
    • \mathbf{b} = (b_v)_{v \in V} \in \mathbb{F}_2^V
  • 出力：
    • Gの任意の全域木 T=(V, D) をとる。
    • \mathbf{b} \in \langle\{\mathbf{f}_e \mid e \in D \} \rangle を満たすか？
    • 満たす場合、次を満たすような (c_e)_{e\in D} \in \mathbb{F}_2^D を構成せよ。 \begin{align} \sum_{e\in D} c_e \mathbf{f}_e = \mathbf{b} \end{align}

まとめ

まとめると、次のようなことがわかりました。

  • 線形空間 \mathbb{F}_2^V 上で議論ができる
  • 問題を \mathbb{F}_2^V 上の言葉で書き換えると、Eの張る部分空間を考えればよいことがわかる。
  • つまり、その空間を張るような辺（ベクトル）集合に制限しても問題ない。
    • 定理より、全域木の辺集合はそれに該当する。
  • よって元の問題は全域木に帰着された。

補足

もう少し議論を踏み込むと、さらにおもしろいことが見えてきます。

考察すると、全域木 T = (V, D) に対して \{\mathbf{f}_e \mid e \in D \} は線形独立なベクトルからなる集合であることがわかります。よって、この集合は \langle\{\mathbf{f}_e \mid e \in E \} \rangle の基底です。

厳密さに欠いた表現で言うと、全域木の辺集合は元のグラフの辺集合が張る空間の基底であるということです。全域木を取り出すことは、線形従属な辺を除去した操作に相当します。

また、このことから \langle\{\mathbf{f}_e \mid e \in E \} \rangle の次元は n-1 です。元の線形空間 \mathbb{F}_2^V の次元は n なので、すべての空間を張るには次元がひとつ足りません。

この足りない部分が「成分 1 の要素が奇数個のベクトル」です。つまり \mathbf{b} \in \langle\{\mathbf{f}_e \mid e \in E \} \rangle をみたすかどうかの判定は \mathbf{b} の成分が 1 である要素の個数の偶奇をみればよいです。解説 における印の個数の偶奇による判定は、これに相当しています。

さらに、次元がひとつ小さいことと |\mathbb{F}_2| = 2 であることから、 \mathbf{b} が一様乱数で与えられたときの構築可能だと判定される確率は \frac{1}{2} になることがわかります。これは、偶奇の比が１対１であることとも繋がります。

*1:元のグラフが連結なので全域木は少なくとも１つ存在します。