完全2部グラフ

完全2部グラフについて

完全2部グラフ（Complete Bipartite Graph）は、グラフ理論における特定の形態の2部グラフです。このグラフは、2つの頂点集合があり、任意の一方の頂点が他方のすべての頂点と結ばれる特性を持っています。具体的には、グラフを表すとき、2つの頂点集合をそれぞれ V₁ と V₂、エッジを E とした場合に、次のように定義されます：

$$G := (V₁ + V₂, E)$$

ここで、任意の2つの頂点 v₁ ∈ V₁ と v₂ ∈ V₂ の間には、エッジが存在します。このような完璧な接続があるため、完全2部グラフはその名前が示す通り、特に重要なグラフの一種とされています。グラフの頂点集合のサイズを |V₁|=m および |V₂|=n とした場合、この完全2部グラフは Kₘ,ₙ と表記されます。

例と特性

完全2部グラフの具体例としては、任意の k に対して K₁,k という形を持つものがあり、これは「スター」と呼ばれます。スターは、木構造が完全2部グラフであることを示す良い例です。さらに、グラフ K₁,3 は「爪」と呼ばれ、K₃,3 は「ユーティリティグラフ」として知られており、これらは完全2部グラフの特性を示しています。

完全2部グラフは、いくつかの興味深い特性を持っています。例えば、2部グラフの辺の数は最大で m⋅n になりますが、完全2部部分グラフ Kₘ,ₙ を求める問題は NP完全問題に分類され、計算機科学において重要な役割を果たします。また、平面グラフは K₃,3 を含まないという性質があり、外平面グラフは K₃,2 を含まないため、これらは平面性や外平面性の必要条件として機能します。

さらに、完全2部グラフ Kₙ,ₙ は (n,4)-ケージとみなされ、または Turán グラフの特性も持っています。これに加えて、完全2部グラフの被覆数や独立集合の大きさ、隣接行列とラプラシアン行列の固有値も定義されています。特に、Kₘ,ₙ において、頂点被覆数は min{m, n} であり、辺被覆数は max{m, n} です。最大独立集合の大きさは max{m, n} であり、これらの特性はグラフ理論における重要な研究課題とされています。

最大マッチングと彩色

完全2部グラフ Kₘ,ₙ には、いくつかの特別な特徴があります。それは、最大マッチングのサイズが min{m, n} であることです。また、Kₙ,ₙ に対しては、ラテン方格に基づいた n色の辺彩色が存在します。これらの事実は、k-正則2部グラフにおける結婚定理を応用することで得られた結果として知られています。

関連用語

完全2部グラフに関連する用語として、閉路グラフ、完全グラフ、空グラフ、隣接行列などがあります。これらの用語は、グラフ理論全体の理解を深めるために重要です。特に、完全2部グラフは他の多くのグラフと比較され、研究される中で、その特性や応用範囲が広がっています。

もう一度検索