二部グラフ

二部グラフは、いくつかの異なる方法で特徴づけることができます。

• 無向グラフは、奇数サイクルを含まない場合に限り二部グラフである。^{[ 13 ] [ 14 ]}
• グラフが二部グラフであるのは、それが2彩色可能である場合（つまり、彩色数が2以下である場合）に限る。^{[ 3 ]}
• グラフが二部グラフであるのは、すべての辺が奇数個の結合（削除するとグラフのコンポーネント数が増加する最小の辺のサブセット）に属している場合に限る。^{[ 15 ]}
• グラフが二部グラフであるのは、そのグラフのスペクトルが対称である場合に限る。 ^{[ 16 ]}

二部グラフでは、最小頂点被覆のサイズは最大マッチングのサイズに等しくなります。これはケーニッヒの定理です。^{[ 17 ] [ 18 ]}この定理の別の同等の形式は、最大独立集合のサイズと最大マッチングのサイズの合計が頂点の数に等しいということです。孤立頂点のない任意のグラフでは、最小辺被覆のサイズと最大マッチングのサイズの合計が頂点の数に等しくなります。^{[ 19 ]}この等式をケーニッヒの定理と組み合わせると、二部グラフでは、最小辺被覆のサイズが最大独立集合のサイズに等しく、最小辺被覆のサイズと最小頂点被覆のサイズの合計が頂点の数に等しいという事実が得られます。

関連する結果のもう 1 つのクラスは完全グラフに関するものです。すべての二部グラフ、すべての二部グラフの補グラフ、すべての二部グラフの線グラフ、およびすべての二部グラフの線グラフの補グラフはすべて完全です。二部グラフの完全性は容易にわかります (彩色数は 2 であり、最大クリークサイズも 2 です) が、二部グラフの補グラフの完全性はそれほど自明ではなく、ケーニッヒの定理の別の言い換えです。これは、完全グラフの最初の定義を促した結果の 1 つです。^{[ 20 ]}完全グラフの線グラフの補グラフの完全性は、ケーニッヒの定理のさらに別の言い換えであり、線グラフ自体の完全性は、すべての二部グラフは最大次数に等しい数の色を使用してエッジ彩色を行うという、ケーニッヒの以前の定理の言い換えです。

強完全グラフ定理によれば、完全グラフは二部グラフに似た禁止グラフ特性を持ちます。グラフが二部グラフであるのは、その部分グラフに奇数サイクルが存在しない場合に限ります。また、グラフが完全グラフであるのは、その部分グラフに奇数サイクルまたはその補グラフが誘導部分グラフとして存在しない場合に限ります。二部グラフ、二部グラフの線グラフ、およびそれらの補グラフは、強完全グラフ定理の証明で使用される完全グラフの 5 つの基本クラスのうち 4 つを構成します。^{[ 21 ]}したがって、二部グラフの任意の部分グラフは奇数サイクルを獲得できないため、二部グラフでもあります。^{[ 22 ]}

頂点について、隣接する頂点の数をその頂点の次数と呼び、次のように表されます。${\displaystyle \deg v}$二部グラフの次数和公式は^{[ 23 ]}と述べている。

${\displaystyle \sum _{v\in V}\deg v=\sum _{u\in U}\deg u=|E|\,.}$

二部グラフの次数列は、2つの部分の次数をそれぞれ含むリストのペアである。${\displaystyle U}$そして${\displaystyle V}$例えば、完全二部グラフK _{3,5 の}次数列は${\displaystyle (5,5,5),(3,3,3,3,3)}$同型な二部グラフは同じ次数列を持ちます。しかし、一般に次数列は二部グラフを一意に識別するものではありません。場合によっては、同型でない二部グラフでも同じ次数列を持つことがあります。

二部グラフ実現問題とは、次数列が与えられた2つの自然数のリストであるような単純な二部グラフを見つける問題である。（末尾のゼロは、有向グラフに適切な数の孤立頂点を追加することで容易に実現できるため、無視してもよい。）

二部グラフの隣接行列${\displaystyle (U,V,E)}$サイズが(0,1) の行列です${\displaystyle |U|\times |V|}$隣接する頂点のペアごとに 1、隣接しない頂点には 0 が割り当てられます。^{[ 24 ]}二部グラフ、ハイパーグラフ、および有向グラフ間の等価性を記述するために、二部隣接行列が使用される場合があります。

ハイパーグラフは、無向グラフと同様に頂点と辺を持つ組み合わせ構造ですが、辺は必ずしも2つの端点を持つ必要はなく、任意の頂点の集合であることができます。二部グラフ${\displaystyle (U,V,E)}$Uはハイパーグラフの頂点の集合、Vはハイパーエッジの集合であり、Eはハイパーグラフの頂点vからハイパーグラフのエッジeへのエッジを、 v がeの端点のいずれかである場合に限り含むハイパーグラフをモデル化するために使用できます。この対応関係の下では、二部グラフの双方向隣接行列は、対応するハイパーグラフの隣接行列と完全に一致します。二部グラフとハイパーグラフの間のこの対応関係の特殊なケースとして、任意の多重グラフ(同じ 2 つの頂点間に 2 つ以上のエッジが存在する可能性があるグラフ) は、いくつかのハイパーエッジが等しい端点の集合を持ち、多重隣接がなく、二分割の一方の側の頂点がすべて次数2 である二部グラフによって表現されるハイパーグラフとして解釈できます。^{[ 25 ]}

隣接行列の同様の再解釈を用いることで、有向グラフ（ラベル付き頂点の数が与えられ、自己ループを許容する）と、二部グラフの両側に同じ数の頂点を持つバランスのとれた二部グラフとの間に一対一の対応関係があることを示すことができる。なぜなら、 n個の頂点を持つ有向グラフの隣接行列は、任意の(0,1)行列でサイズは${\displaystyle n\times n}$これは、二部グラフの両側にn個の頂点を持つ二部グラフの隣接行列として再解釈できます。 ^{[ 26 ]}この構成では、二部グラフは有向グラフの二部二重被覆です。

深さ優先探索(DFS)を使用すれば、グラフが二部グラフであるかどうかを判定し、二部グラフであれば 2 色彩、そうでなければ奇数サイクルを線形時間で返すことが可能です。主なアイデアは、深さ優先探索フォレストを先行順で走査し、各頂点に DFS フォレスト内の親の色とは異なる色を割り当てることです。これにより、頂点を親に接続するエッジで構成される全域フォレストの 2 色彩が必ず得られますが、フォレスト以外のエッジの一部は適切に色付けされない可能性があります。DFS フォレストでは、フォレスト以外のエッジの 2 つの端点のうちの 1 つがもう一方の端点の祖先であり、深さ優先探索がこのようなエッジを発見した場合は、これら 2 つの頂点が異なる色を持っていることを確認する必要があります。そうでない場合、祖先から子孫への森の中のパスと、色付けが間違っているエッジが奇数サイクルを形成し、アルゴリズムはグラフが二部グラフではないという結果とともにそれを返します。ただし、アルゴリズムがこの種の奇数サイクルを検出せずに終了した場合、すべてのエッジが正しく着色されている必要があり、アルゴリズムはグラフが二部グラフであるという結果とともに着色を返します。^{[ 27 ]}

あるいは、DFS の代わりに幅優先探索を使用して同様の手順を実行することもできます。ここでも、各ノードは、幅優先の順序で、探索フォレスト内の親ノードとは反対の色を与えられます。頂点が着色されたときに、以前に同じ色で着色された頂点に接続するエッジが存在する場合、このエッジと、幅優先探索フォレスト内でその 2 つの端点をそれらの最小共通祖先に接続するパスは、奇数サイクルを形成します。この方法で奇数サイクルが見つからずにアルゴリズムが終了した場合、適切な着色が見つかったはずであり、グラフが二部グラフであると安全に結論付けることができます。^{[ 28 ]}

交差グラフの場合${\displaystyle n}$ユークリッド平面上の線分やその他の単純な図形の場合、グラフが二部グラフであるかどうかをテストし、2色塗りまたは奇数サイクルを返すことができます。${\displaystyle O(n\log n)}$ビッグオー記法を使用すると、グラフ自体は最大で${\displaystyle O(n^{2})}$エッジ。^{[ 29 ]}

奇数サイクル横断は、グラフG = ( V , E ) と数kが与えられたとき、 Gから削除すると結果として得られるグラフが二部グラフになるk 個の頂点の集合が存在するかどうかを問うNP 完全なアルゴリズム問題です。 ^{[ 30 ]}この問題は固定パラメータ扱い可能であり、つまり、実行時間がグラフのサイズの多項式関数にkのより大きな関数を掛けたもので制限できるアルゴリズムが存在します。^{[ 31 ]}奇数サイクル横断という名前は、グラフが奇数サイクルを持たない場合に限り二部グラフであるという事実から来ています。したがって、二部グラフを得るためにグラフから頂点を削除するには、「すべての奇数サイクルをヒットする」か、いわゆる奇数サイクル横断セットを見つける必要があります。図では、グラフ内のすべての奇数サイクルに青色 (最下) の頂点が含まれているため、これらの頂点を削除するとすべての奇数サイクルが消滅し、二部グラフが残ります。 

エッジ二部分割問題は、グラフを二部グラフにするためにできるだけ少ないエッジを削除するアルゴリズム問題であり、グラフ修正アルゴリズムにおける重要な問題でもあります。この問題は固定パラメータ扱い可能であり、時間で解くことができます。${\textstyle O\left(2^{k}m^{2}\right)}$[ ^{32 ]}ここでkは削除するエッジの数、m^は入力グラフのエッジの数である。

グラフにおけるマッチングは、そのエッジのサブセットであり、どの 2 つのエッジも端点を共有しません。マッチングに関する多くのアルゴリズム問題、例えば最大マッチング(可能な限り多くのエッジを使用するマッチングを見つける)、最大重みマッチング、安定結婚などに対して、多項式時間アルゴリズムが知られています。^{[ 33 ]}多くの場合、マッチング問題は非二部グラフよりも二部グラフの方が簡単に解決できます。^{[ 34 ]}また、最大カーディナリティマッチングのためのHopcroft–Karp アルゴリズム^{[ 35 ]}など、多くのマッチングアルゴリズムは二部グラフの入力に対してのみ正しく動作します。

簡単な例として、集合が${\displaystyle P}$多くの人々が、あるセットの中から仕事を探している${\displaystyle J}$すべての人がすべての仕事に適しているわけではないが、仕事には様々な種類がある。この状況は二部グラフとしてモデル化できる。${\displaystyle (P,J,E)}$エッジが各求職者と各適切な仕事を結び付けている。^{[ 36 ]}完全マッチングは、すべての求職者を同時に満足させ、すべての仕事を埋める方法を表す。ホールの結婚定理は、完全マッチングを可能にする二部グラフの特徴付けを提供する。全米レジデントマッチングプログラムは、米国の医学生の求職者と病院のレジデンシーの仕事に関するこの問題を解決するためにグラフマッチング手法を適用している。^{[ 37 ]}

ダルマージ・メンデルソン分解は、最大マッチングを見つけるのに役立つ二部グラフの構造的分解である。^{[ 38 ]}