二部グラフ
概要
二部グラフ（bipartite graph）とは、頂点集合を二つの部集合に分割し、すべての辺が異なる部集合に属する頂点どうしを結ぶようにできるグラフである。これは頂点を 2 色で塗り分けて隣接する頂点が同色にならないようにできることと同値であり、さらに閉路の長さがすべて偶数であることとも同値である（König による特徴付け）。頂点集合を $r$ 個のクラスに分ける $r$-部グラフ、異なる部集合の頂点をすべて結んだ完全二部グラフ $K_{m,n}$ や完全 $r$-部グラフ $K(n_1,\dots,n_r)$ はその自然な拡張である。二部グラフは、二部グラフの部分グラフが再び二部グラフであること、連結な場合に二部分割が一意であること、辺数が $\lfloor n^2/4\rfloor$ 以下であることなどの基本性質を持ち、マッチング理論や組合せ最適化の基本的な舞台となる。
前提知識: グラフ, 単純グラフ, 道, 閉路, 連結グラフ
定義
本記事では、特に断らない限り、ループも平行辺も持たない無向の単純グラフ $G=(V,E)$ を扱う。頂点の集合を $V=V(G)$、辺の集合を $E=E(G)$ と書き、辺 $\{u,v\}\in E$ を $uv$ とも書く。
グラフ $G=(V,E)$ が二部グラフ（bipartite graph）であるとは、$V$ の分割 $V=A\cup B$、$A\cap B=\emptyset$ であって、$G$ のすべての辺が一方の端点を $A$ に、他方の端点を $B$ に持つものが存在することをいう。すなわち、$A$ の頂点どうし、および $B$ の頂点どうしを結ぶ辺が存在しない。このような分割の組 $\{A,B\}$ を $G$ の二部分割（bipartition）といい、$A$、$B$ を部集合（part）という。二部分割を明示するとき $G=(A,B;E)$ とも書く。
定義において $A$ や $B$ が空集合であることも許す。したがって辺を持たないグラフ（空グラフ）はすべて二部グラフであり、特に 1 頂点のグラフも二部グラフである。同じ部集合に属する 2 頂点は隣接しないので、誘導部分グラフ $G[A]$ と $G[B]$ はいずれも辺を持たない。
二部分割 $\{A,B\}$ を持つ二部グラフ $G$ が完全二部グラフ（complete bipartite graph）であるとは、$A$ の各頂点と $B$ の各頂点がすべて隣接すること、すなわち
$$E=\{\{a,b\}\mid a\in A,\ b\in B\}$$
となることをいう。$|A|=m$、$|B|=n$ の完全二部グラフは同型（グラフ同型）を除いて一つに定まり、これを $K_{m,n}$ と書く。$K_{1,n}$ を星グラフ（star）ともいう。
正の整数 $r$ に対し、グラフ $G=(V,E)$ が $r$-部グラフ（$r$-partite graph）であるとは、$V$ の分割 $V=A_1\cup\cdots\cup A_r$（$i\neq j$ のとき $A_i\cap A_j=\emptyset$）であって、各 $i$ について $A_i$ の頂点どうしを結ぶ辺が存在しないものが存在することをいう。このとき各 $A_i$ を頂点のクラス（class）または部集合という。$2$-部グラフは二部グラフにほかならない。
$r$-部グラフ $G$ が、クラス $A_1,\dots,A_r$ に関して完全 $r$-部グラフ（complete $r$-partite graph）であるとは、異なるクラスに属する頂点がすべて隣接すること、すなわち
$$E=\{\{v,w\}\mid v\in A_i,\ w\in A_j,\ 1\le i< j\le r\}$$
となることをいう。$|A_i|=n_i$（$i=1,\dots,r$）の完全 $r$-部グラフは同型を除いて一つに定まり、これを $K(n_1,\dots,n_r)$ と書く。完全二部グラフ $K(p,q)$ は上の $K_{p,q}$ であり、$K(t,\dots,t)$（クラスが $r$ 個）を $K_r(t)$ とも書く。
文献によっては、二部分割の両方の部集合が空でないことを要求する流儀がある（Die17 §1.6 では分割の各クラスを空でないとしている）。その流儀では 1 頂点のグラフは二部グラフでない。本記事のように空の部集合を許す流儀は Wes01 §1.1 による。また、マッチング理論（マッチング）やネットワークフローのように、二部分割を順序対 $(A,B)$ として固定して扱う文脈では、同じグラフでも分割のデータを込めて考える。本記事の定義は分割の存在だけを要求する。有向グラフや多重グラフについても、向きや平行辺を無視して得られるグラフが二部グラフであるとき二部グラフという。ループを持つグラフは、ループの両端が同じ部集合に入るので二部グラフではない。
直感
二部グラフとは、頂点を白と黒の 2 色で塗り分けて、すべての辺が白と黒の間だけを走るようにできるグラフである。人と仕事、学生と講義、生産者と消費者のように、頂点が二種類のものに分かれ、辺が異なる種類のものだけを結ぶ状況を抽象化したものといえる。二部グラフは「分割が存在する」という外在的な条件で定義されるが、「閉路の長さがすべて偶数である」という内在的な条件で完全に特徴付けられる（thm-bipartite-even-cycle）。このため、与えられたグラフが二部グラフかどうかは分割を探さなくても判定でき、幅優先探索によって効率よく判定できる。
例と反例
$n\ge3$ とし、頂点 $v_0,v_1,\dots,v_{n-1}$ と辺 $v_0v_1,\ v_1v_2,\ \dots,\ v_{n-2}v_{n-1},\ v_{n-1}v_0$ からなる長さ $n$ の閉路グラフを $C_n$ と書く。$n$ が偶数のとき、$A:=\{v_i\mid i\text{ は偶数}\}$、$B:=\{v_i\mid i\text{ は奇数}\}$ とおくと、辺 $v_iv_{i+1}$（$0\le i\le n-2$）は添字の偶奇が異なる頂点を結び、辺 $v_{n-1}v_0$ も $n-1$ が奇数、$0$ が偶数なので $B$ と $A$ の頂点を結ぶ。よって $\{A,B\}$ は二部分割であり、$C_n$ は二部グラフである。$n$ が奇数のときは、$C_n$ 自身が長さ奇数の閉路なので、thm-bipartite-even-cycle により二部グラフではない。
木、より一般に閉路を持たないグラフ（森）は二部グラフである。閉路を全く持たないので、特に長さ奇数の閉路を持たず、thm-bipartite-even-cycle が適用できる。直接には、各連結成分(グラフ)で頂点 $r$ を一つ選び、$r$ からの距離(グラフ)が偶数の頂点全体と奇数の頂点全体に分ければ二部分割が得られる（thm-bipartite-even-cycle の証明を参照）。
$n$ 次元超立方体グラフ $Q_n$ とは、頂点集合を $\{0,1\}^n$ とし、ちょうど 1 個の成分だけが異なる二つのベクトルを辺で結んだグラフである。成分の総和が偶数の頂点全体を $A$、奇数の頂点全体を $B$ とすると、1 個の成分を変えると総和の偶奇が必ず反転するので、各辺は $A$ の頂点と $B$ の頂点を結ぶ。よって $\{A,B\}$ は二部分割であり、$Q_n$ は二部グラフである。
グラフの記事にならい、頂点集合が交わらない 2 つのグラフ $G$、$H$ に対し、$G\cup H$ を頂点集合 $V(G)\cup V(H)$、辺集合 $E(G)\cup E(H)$ のグラフ（非交和）とし、$G+H$ を $G\cup H$ に $V(G)$ の各頂点と $V(H)$ の各頂点を結ぶ辺をすべて加えたグラフ（結合、join）とする。また $n$ 頂点の空グラフ（辺を持たないグラフ）を $E_n$、$n$ 頂点の完全グラフを $K_n$ と書く。このとき
$$K(n_1,\dots,n_r)=E_{n_1}+E_{n_2}+\cdots+E_{n_r},\qquad K_{p,q}=E_p+E_q=\overline{K_p\cup K_q}$$
が成り立つ。実際、$E_{n_1}+\cdots+E_{n_r}$ の辺は異なる $E_{n_i}$ の頂点どうしを結ぶものの全体であり、これは各 $V(E_{n_i})$ をクラスとする完全 $r$-部グラフの辺集合そのものである。また $K_p\cup K_q$ の補グラフは、$K_p$ の内部と $K_q$ の内部の辺をすべて取り除き、$K_p$ と $K_q$ の間の辺をすべて加えたものだから $E_p+E_q$ に等しい。
完全 $r$-部グラフ $K(n_1,\dots,n_r)$ の辺数は $\sum_{1\le i< j\le r}n_in_j$ であり、クラス $A_i$ の頂点の次数(グラフ)は $n-n_i$（$n:=n_1+\cdots+n_r$）である。特に $K_{m,n}$ は $mn$ 本の辺を持ち、$A$ の頂点の次数は $n$、$B$ の頂点の次数は $m$ である。
三角形 $K_3=C_3$ は二部グラフではない。3 頂点をどのように二つの部集合に分けても、同じ部集合に 2 頂点が入り、$K_3$ ではその 2 頂点が隣接するからである。より一般に、$n$ が奇数の閉路グラフ $C_n$、および $n\ge3$ の完全グラフ $K_n$ は二部グラフではない。$K_n$ は $K_3$ を部分グラフとして含み、二部グラフの部分グラフは二部グラフである（prop-bipartite-hereditary）ことによる。
これらは次の意味で反例である。満たす性質：連結な単純グラフである。満たさない性質：二部グラフである。破る含意：「連結な単純グラフ ⇒ 二部グラフ」は成り立たない。また $C_5$ は、三角形を含まないが二部グラフでない例であり、「三角形を含まない ⇒ 二部グラフ」も成り立たないことを示す。二部性の判定は、描画が二列に並べられるかではなく、奇数長の閉路の有無で行う。
$r$-部グラフは、空のクラスを一つ加えれば $(r+1)$-部グラフでもある。逆は成り立たない。$K_3$ は 3 頂点をそれぞれ一つのクラスとする $3$-部グラフ（完全 $3$-部グラフ $K(1,1,1)$）であるが、上で見たように二部グラフではない。満たす性質：$3$-部グラフである。満たさない性質：$2$-部グラフである。破る含意：「$3$-部グラフ ⇒ $2$-部グラフ」は成り立たない。
性質
1 ⇒ 2：クラス $A_1,\dots,A_r$ をとり、$v\in A_i$ に対し $c(v):=i$ と定める。分割なので $c$ は $V$ 全体で定義された写像である。任意の辺 $uv$ について、$u$ と $v$ は同じクラスに属さないので $c(u)\neq c(v)$ である。
2 ⇒ 1：そのような $c$ をとり、$A_i:=c^{-1}(i)$（$i=1,\dots,r$）とおく。$A_1,\dots,A_r$ は互いに交わらず、合併は $V$ である。任意の辺 $uv$ について $c(u)\neq c(v)$ だから、$u$ と $v$ は異なる $A_i$ に属する。よって $A_1,\dots,A_r$ は $r$-部グラフの定義にいう分割である。$\square$
$\{A,B\}$ を $G$ の二部分割、$H$ を $G$ の部分グラフとし、$A':=A\cap V(H)$、$B':=B\cap V(H)$ とおく。$H$ の各辺は $G$ の辺だから端点を $A$ と $B$ に一つずつ持ち、両端点は $V(H)$ に属するので、$A'$ と $B'$ に一つずつ持つ。よって $\{A',B'\}$ は $H$ の二部分割である。
後半について、各連結成分は $G$ の部分グラフなので、$G$ が二部グラフなら前半により各成分も二部グラフである。逆に、連結成分 $G_1,\dots,G_k$ がそれぞれ二部分割 $\{A_i,B_i\}$ を持つとする。$A:=A_1\cup\cdots\cup A_k$、$B:=B_1\cup\cdots\cup B_k$ とおくと、成分の頂点集合は互いに交わらないので $\{A,B\}$ は $V(G)$ の分割であり、$G$ の各辺はある一つの成分 $G_i$ の辺なので端点を $A_i\subset A$ と $B_i\subset B$ に一つずつ持つ。よって $\{A,B\}$ は $G$ の二部分割である。$r$-部グラフの場合も、二部分割を $r$ 個のクラスに置き換えれば同じ議論が通用する。$\square$
次が本記事の主定理であり、二部性の内在的な特徴付けを与える。この特徴付けは König による（Die17 命題 1.6.1 および同章末尾の注記）。
グラフ $G$ について、次は同値である。
- $G$ は二部グラフである。
- $G$ のすべての閉路の長さは偶数である。すなわち、$G$ は長さが奇数の閉路を含まない。
1 ⇒ 2：$\{A,B\}$ を二部分割とし、$v_0,v_1,\dots,v_{k-1},v_k=v_0$ を $G$ の長さ $k$ の閉路とする。$v_0\in A$ としてよい。各辺は部集合をまたぐから、$i$ について帰納的に、$v_i$ は $i$ が偶数のとき $A$、奇数のとき $B$ に属する。$v_k=v_0\in A$ なので $k$ は偶数である。
2 ⇒ 1：prop-bipartite-hereditary により各連結成分について示せば十分なので、$G$ は連結グラフとしてよい。頂点 $r$ を一つ固定し、$v\in V$ に対し $d(v)$ で $r$ から $v$ への距離(グラフ)（$r$ と $v$ を結ぶ道の長さの最小値）を表す。連結性により $d(v)$ は有限である。
$$A:=\{v\in V\mid d(v)\text{ は偶数}\},\qquad B:=\{v\in V\mid d(v)\text{ は奇数}\}$$
とおく。$\{A,B\}$ が二部分割でないと仮定して矛盾を導く。仮定により、同じ部集合に属する 2 頂点を結ぶ辺 $uv$ が存在する。すなわち $d(u)$ と $d(v)$ の偶奇は等しい。
$P$ を $r$ から $u$ への最短の道、$Q$ を $r$ から $v$ への最短の道とする。最短の道 $r=x_0,x_1,\dots,x_m$ の上では $d(x_i)=i$ である。実際、$x_0,\dots,x_i$ は $r$ と $x_i$ を結ぶ長さ $i$ の道なので $d(x_i)\le i$ であり、もし $d(x_i)< i$ なら、$r$ から $x_i$ への長さ $d(x_i)$ の道に $x_i,\dots,x_m$ をつなぐと $r$ から $x_m$ への長さ $m-i+d(x_i)< m$ の歩道が得られ、歩道から頂点の繰り返しを取り除けばそれ以下の長さの道が得られるので（距離(グラフ)の記事の補題 lem-graph-distance-walk-to-path を参照）、$d(x_m)< m$ となって $P$ が最短であることに反する。したがって最短の道の上には、$r$ からの距離が等しい 2 頂点は存在しない。
$P$ と $Q$ の共通の頂点のうち $d$ の値が最大のものを $w$ とする（$r$ は共通の頂点なので $w$ は存在する）。$P$ の $w$ から $u$ までの部分を $P'$、$Q$ の $w$ から $v$ までの部分を $Q'$ とする。$P'$ は長さ $d(u)-d(w)$ の道、$Q'$ は長さ $d(v)-d(w)$ の道である。$P'$ と $Q'$ が $w$ 以外に共通の頂点 $z$ を持てば、$z$ は $P$ と $Q$ の共通の頂点で $d(z)\ge d(w)$ であり、$w$ の最大性から $d(z)=d(w)$ となるが、$P'$ 上に $r$ からの距離が等しい 2 頂点 $w,z$ はないので $z=w$ となり矛盾する。よって $P'$ と $Q'$ は $w$ だけを共有する。
したがって、$P'$ に沿って $w$ から $u$ へ進み、辺 $uv$ を渡り、$Q'$ を逆にたどって $v$ から $w$ へ戻る閉じた歩道は、$w$ 以外の頂点を繰り返さないので閉路であり、その長さは
$$\bigl(d(u)-d(w)\bigr)+\bigl(d(v)-d(w)\bigr)+1$$
である。$d(u)+d(v)$ は偶数だから、この長さは奇数である（$u\neq v$ なので長さは $1$ ではなく、したがって $3$ 以上である）。これは仮定 2 に反する。よって $\{A,B\}$ は二部分割であり、$G$ は二部グラフである。$\square$
$G$ を空でない連結な二部グラフとする。このとき $G$ の二部分割 $\{A,B\}$ は、$A$ と $B$ の順序を除いてただ一つである。
頂点 $r$ を固定し、$\{A,B\}$ を任意の二部分割とする。$r\in A$ としてよい。任意の頂点 $v$ に対し、連結性から $r$ から $v$ への道 $r=u_0,u_1,\dots,u_k=v$ が存在する。各辺は部集合をまたぐから、$u_i$ の属する部集合は一歩ごとに交代し、$u_i\in A$ であることと $i$ が偶数であることが同値である。特に $v\in A$ であることは、$r$ から $v$ へのこの道の長さ $k$ が偶数であることと同値である。ここで $r$ から $v$ へのどの道をとっても同じ結論が得られるので、$r$ から $v$ への道の長さの偶奇は道の取り方によらない。したがって
$$A=\{v\in V\mid r\text{ から }v\text{ への道の長さは偶数}\}$$
であり、右辺は二部分割の取り方によらず $G$ と $r$ だけから定まる。$B=V\setminus A$ も同様に定まるので、$r$ を含む側を $A$ とする限り二部分割は一意である。$\square$
連結でない場合は一意性が崩れる。たとえば辺を持たない 2 頂点のグラフでは、2 頂点を同じ部集合に入れても、別々の部集合に入れてもよい。
$G$ を頂点数 $n$ の二部グラフとすると
$$|E(G)|\le\left\lfloor\frac{n^2}{4}\right\rfloor$$
が成り立つ。等号が成り立つのは、$G$ が完全二部グラフ $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ と同型のとき、かつそのときに限る。
二部分割 $\{A,B\}$ をとり、$|A|=a$、$|B|=n-a$ とおく。すべての辺は $A$ の頂点と $B$ の頂点を結ぶから、辺の本数はそのような頂点の組の個数 $a(n-a)$ 以下である。ここで
$$a(n-a)=\frac{n^2}{4}-\Bigl(a-\frac{n}{2}\Bigr)^2$$
である。$n$ が偶数なら $(a-n/2)^2\ge0$ で、等号は $a=n/2$ のときに限る。$n$ が奇数なら $a-n/2$ は $1/2$ の奇数倍なので $(a-n/2)^2\ge1/4$ で、等号は $a=(n\pm1)/2$ のときに限る。いずれの場合も $a(n-a)\le\lfloor n^2/4\rfloor$ であり、等号は $a\in\{\lfloor n/2\rfloor,\lceil n/2\rceil\}$ のときに限る。よって $|E(G)|\le a(n-a)\le\lfloor n^2/4\rfloor$ である。
$|E(G)|=\lfloor n^2/4\rfloor$ ならば両方の不等号で等号が成り立つので、$\{|A|,|B|\}=\{\lfloor n/2\rfloor,\lceil n/2\rceil\}$ であり、$A$ の頂点と $B$ の頂点の組はすべて辺である。すなわち $G$ は $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ と同型である。逆に $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ の辺数は $\lfloor n/2\rfloor\lceil n/2\rceil=\lfloor n^2/4\rfloor$ である。$\square$
この上界は、三角形を含まない $n$ 頂点グラフ一般についても成り立つ（Mantelの定理、証明は部分グラフの記事にある）。二部グラフは三角形を含まないので、prop-bipartite-edge-bound はその特別な場合であり、等号を与える $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ は Mantel の定理の極値グラフ（極値グラフ理論）でもある。
補足
二部グラフはマッチング理論の中心的な舞台である。二部グラフにおいては、最大マッチングの大きさが最小頂点被覆の大きさに一致するというKönigの定理、および一方の部集合の頂点をすべて含むマッチングの存在条件を与えるHallの結婚定理が成り立つ（Die17 第 2 章、BM08 第 16 章）。組合せ最適化では割当問題や輸送問題が二部グラフ上のフローとして定式化される。
与えられた有限グラフが二部グラフかどうかは、thm-bipartite-even-cycle の証明にある構成をそのまま実行すれば判定できる。各連結成分で頂点 $r$ から幅優先探索を行って各頂点の距離を求め、距離の偶奇で頂点を 2 色に塗り分け、同色の 2 頂点を結ぶ辺があるかどうかを調べればよい。同色の辺があれば証明と同様に奇数長の閉路が存在し、なければ塗り分けが二部分割を与える。この判定は頂点数と辺数の和に比例する時間で実行できる（BM08 第 6 章）。
$r$-部グラフの概念は、prop-bipartite-coloring により頂点彩色の言葉で言い換えられる。グラフの彩色数が $r$ 以下であることと $r$-部グラフであることは同じであり、完全 $r$-部グラフ $K_r(t)$ は極値グラフ理論における Turán グラフ（Turánグラフ）の構成に現れる（Bol02 第 IV 章）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
