📂グラフ理論

ツリーグラフ

定義 ¹

サイクルが存在しない連結グラフを木という。

説明

木は、コンピュータ科学のデータ構造などでよく見られる概念で、少しでもコンピュータを扱う理工学部の学生なら、ヒープソートという言葉を聞いたことがあるだろう。ここで言及されているそのヒープは、まさに木の一種である。木のユニオンは直感的にフォレストと呼ばれる。有向グラフの場合、入力次数が$0$のノードをルート、出力次数が$0$のノードをリーフとも呼ぶ。このように木は比較的応用が見つけやすく、言葉も親しみやすいが、残念ながら純粋数学ではその複雑な素顔をさらけ出す。

整理

次は、木グラフになる同値条件である。

$T$が$n$個の頂点を持つグラフだとしよう。以下は相互に同値である。

• (i): $T$は木である。
• (ii): $T$はサイクルを持たず、$n-1$個のエッジを持つ。
• (iii): $T$は連結グラフで、$n-1$個のエッジを持つ。
• (iv): $T$の全てのエッジはブリッジである。
• (v): $T$の任意の二つの頂点を結ぶパスは一つだけである。
• (vi): $T$はサイクルを持たないが、エッジを追加すると正確に一つのサイクルが生じる。

---

• エッジ$b \in G$が消去されることでグラフが断絶する場合、$b$をブリッジと呼ぶ。

証明

$(i) \implies (ii)$

$T$はサイクルが存在しないので、エッジを消去すると二つの木に分かれる。帰納的にこれを繰り返すと、各木ではエッジの数が頂点の数よりもちょうど一つ少ない。逆に考えると、木$T$は$n-1$個のエッジを持たなければならない。

---

$(ii) \implies (iii)$

$T$が連結グラフでないと仮定する。$T$の各コンポーネントはサイクルを持たず、それぞれ頂点より$1$少ない数のエッジを持つ。しかし、これはエッジが$n-1$個であるという前提に反するので、$T$は連結グラフでなければならない。

---

$(iii) \implies (iv)$

断絶グラフのエッジ: 単純グラフ$G$が$n$個の頂点を持っているとする。$G$が$k$個の頂点を持つなら、$G$のエッジの数$m$は次の条件を満たす。 $$n-k \le m \le (n-k)(n-k+1)/2$$

$T$のどのエッジでも取り除くと、頂点の数は$n$、エッジの数は$n-2$になるので$n-k \le n-2$となり、$2 \le k$というのはエッジを取り除くとコンポーネントの数が増えるという意味で、したがって$T$の全てのエッジはブリッジである。

---

$(iv) \implies (v)$

$T$は連結グラフであるため、どの頂点の組み合わせも少なくとも一つのパスに属する。ある頂点の組み合わせが二つのパスに属する場合、これはサイクルを形成し、全てのエッジがブリッジであるという前提に矛盾する。

---

$(v) \implies (vi)$

$T$が既にサイクルを含む場合、そのサイクルに属する任意の二つの頂点は少なくとも二つのパスに属することになり、前提に矛盾する。エッジ$e$が$T$に追加される場合、$e$に繋がる頂点は既に$T$と接続されているため、サイクルが形成される。したがって、$T$にエッジを追加すると正確に一つのサイクルが生まれる。

---

$(vi) \implies (i)$

$T$が連結グラフでない場合、各コンポーネントを結ぶようにエッジを追加してもサイクルは生じない。しかし、これは前提に矛盾するので、$T$は連結グラフでなければならず、前提でサイクルを持たないとされているので、$T$は木である。

■