二部グラフを具体例で理解する

この図では、左のグループを A と B、右のグループを 1、2、3 にします。A は 1 と 2、B は 2 と 3 につながります。すべての辺が左右の間を結び、同じグループの頂点同士には辺がありません。

このように、すべての辺の両端が異なるグループに属するように頂点を 2 つに分けられるグラフを、二部グラフと呼びます。グループの頂点数が等しい必要はありません。

A と B を人、1、2、3 を仕事と考えると、辺は担当できる組を表します。仕事 2 は両方の人とつながるので、どちらも担当できます。この図の辺だけで、実際の担当が決まったわけではありません。

左右に分けた配置は、関係の候補を比較するのに役立ちます。頂点のラベルと説明文で、左右がそれぞれ何を表すかを伝えてください。

Graph Editor ではこの入力を「辺の組リスト（ヘッダーなし）」として読み込み、「配置」の「二部」を選びます。頂点を移動しても、2 つのグループに分けられるという性質は変わりません。

三角形のような奇数本の辺で閉じる閉路があると、どのように分けても同じグループ内に辺が残ります。その場合は二部グラフにならず、二部の配置は選べません。