📂グラフ理論

グラフのファミリーとプロパティ

ビルドアップ

$n$個のラベリングされた頂点の集合$V = [n] = \left\{ 1 ,\cdots , n \right\}$を持つ単純グラフを考えてみよう。このグラフの辺は異なる二つの頂点を選ぶ場合の数だけ存在可能で、そのためその種類は正確に$\binom{n}{2}$だ。これを辺ごとではなく、グラフ全体として考えるなら、$n$個の頂点が固定された状況で$\binom{n}{2}$個の各辺が存在するか(1)しないか(0)のどちらかで区別できる。したがって、頂点が$n$個の全てのグラフの集合は次のように表せるだろう。 $$ 2^{\binom{n}{2}} $$ もちろん、私たちはこれら全てのグラフに興呀を持っているわけではないので、必要な性質を持つグラフだけを集めてみたい。例えば、頂点$n$個の平面グラフだけを集めた集合$P$やオイラーグラフだけを集めた集合$O$があるとするならば、これらは$2^{\binom{n}{2}}$の部分集合として定義されると同時に、グラフがその部分集合に属していればその性質を持つと言えるので、それ自体を性質と呼ぶに足りる。たとえば$G \in \left( P \cap O \right)$ならば、グラフ$G$は平面グラフであり、オイラーグラフだ。言い換えれば、グラフ$G$は平面である性質とオイラーグラフである性質を持っているのだ。

定義 ¹

1. $n$個のラベリングされた頂点を持つグラフのファミリーは冪集合表現を使って次のように表される。 $$ 2^{\binom{n}{2}} $$
2. グラフファミリー$2^{\binom{n}{2}}$の部分集合$\mathscr{P} \subset 2^{\binom{n}{2}}$をプロパティという。
3. $n$個のラベリングされた頂点と$m$個の辺を持つ単純グラフというプロパティ$\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$を次のように定義する。 $$ \mathscr{G}_{n,m} = \left\{ G \in 2^{\binom{n}{2}} : V(G) = [n] , \left| E(G) \right| = m \right\} $$
4. $G$に一つの辺$e \notin E(G)$が追加されても依然として保持されるプロパティを単調増加プロパティという。言い換えると、次を満たす$\mathscr{P}$を単調増加プロパティという。 $$ G \in \mathscr{P} \implies (G + e) \in \mathscr{P} $$ 逆に、一つの辺$e \in E(G)$がなくなっても次のように依然として保持されるプロパティを単調減少プロパティという。 $$ G \in \mathscr{P} \implies (G - e) \in \mathscr{P} $$ これらを総称してモノトーンプロパティという。