二部グラフの魔法 ― なぜ二部グラフではすべてが上手くいくのか

奇数閉路がないだけで，マッチング・彩色・被覆がすべて効率的に解ける ― 二部グラフの驚くべき性質を解説します．König の定理の直感と，競技プログラミングでの帰着パターンも紹介します．

2026年2月27日

グラフ理論には「二部グラフではすべてが上手くいく」という経験則があります．一般のグラフでは NP 完全になる問題が，二部グラフに制限すると多項式時間で解けてしまうことが驚くほど多いのです．この記事では，なぜ二部グラフがそんなに特別なのかを探ります．

1 二部グラフとは

定義 1 (二部グラフ).

グラフ

G = (V, E)

の頂点集合を

V = L \cup R

（

L \cap R = \emptyset

）に分割して，すべての辺が

L

の頂点と

R

の頂点を結ぶようにできるとき，

G

を二部グラフと呼びます．

学生と企業のマッチング，タスクとマシンの割り当て，問題と解法の対応 ― 二部グラフは「2種類のものの間の関係」を表す自然なモデルです．

2 奇数閉路がない ― たったこれだけ

二部グラフの特徴づけは驚くほどシンプルです．

定理 2.

グラフ

G

が二部グラフであるための必要十分条件は，

G

が奇数長の閉路をもたないことです．

注意 3 (なぜ奇数閉路がないと二部になるのか).

G

が連結であるとして，ある頂点

v

を選び BFS で距離を計算します．距離が偶数の頂点を

L

，奇数の頂点を

R

に入れます．

もし辺

{u, w}

で

u, w

が同じ側にあったとすると，

v

から

u

への路，辺

{u, w}

，

w

から

v

への路をつなぐと奇数長の閉路ができます．

逆に奇数閉路がなければ，同じ側の頂点を結ぶ辺は存在せず，

L, R

の分割は二部グラフの分割になります．

この「BFS で2色塗りできる」という特徴づけは，二部グラフの判定が $O (∣ V ∣ + ∣ E ∣)$ でできることも意味しています．

3 マッチング ― 二部グラフの華

定義 4 (マッチング).

辺集合

M \subseteq E

で，

M

のどの2辺も端点を共有しないものをマッチングと呼びます．

∣ M ∣

が最大のものを最大マッチングと呼びます．

一般のグラフでも最大マッチングは多項式時間で求められます（Edmondsのアルゴリズム）．しかし二部グラフではもっと簡単です ― 最大フローに帰着できるからです．

注意 5.

二部グラフ

(L, R, E)

のマッチング問題は，前回紹介した最大フロー問題に直結しています．ソース

s

から

L

の各頂点に容量1の辺を，

R

の各頂点からシンク

t

に容量1の辺を引けば，最大フロー = 最大マッチングのサイズです．

4 König の定理 ― マッチングと被覆の双対性

二部グラフで最も美しい定理のひとつが König の定理です．

定義 6 (頂点被覆).

頂点集合

C \subseteq V

が頂点被覆であるとは，すべての辺

{u, v} \in E

に対して

u \in C

または

v \in C

（またはその両方）が成り立つことです．

∣ C ∣

が最小のものを最小頂点被覆と呼びます．

定理 7 (König の定理).

二部グラフにおいて，最大マッチングのサイズ = 最小頂点被覆のサイズ．

ν (G) = τ (G)

注意 8 (König の定理の直感).

一般のグラフでは

ν (G) \leq τ (G)

しか言えません（弱双対性）．各マッチング辺をカバーするのに少なくとも1頂点必要なので

ν \leq τ

は自明です．

二部グラフでは等号が成り立ちます．これは最大フロー最小カット定理の帰結です：マッチングをフローとして，被覆をカットとして見ると，Max-Flow = Min-Cut から

ν = τ

が従います．

一般のグラフでは等号が成り立ちません．たとえば三角形

K_{3}

では

ν = 1

（辺1本しかマッチできない）ですが

τ = 2

（どの1頂点を選んでも3辺すべてはカバーできない）です．

5 彩色 ― 一般グラフの NP 完全が二部では自明に

定義 9 (グラフ彩色).

グラフ

G

の $k$ -彩色とは，関数

f : V \to {1, 2, \dots, k}

で，隣接する頂点が異なる色を持つものです．最小の

k

を彩色数

χ (G)

と呼びます．

一般のグラフで $χ (G) \leq 3$ かどうかを判定するのは NP 完全です．しかし二部グラフでは：

定理 10.

辺をもつ二部グラフの彩色数は

χ (G) = 2

です．

これは定義から明らかです ― 二部グラフの定義が「2色で塗れる」ということそのものだからです．

6 独立集合 ― König と補集合の関係

定義 11 (独立集合).

頂点集合

I \subseteq V

で，

I

のどの2頂点も隣接しないものを独立集合と呼びます．

一般のグラフでの最大独立集合問題は NP 完全ですが，二部グラフでは：

定理 12.

二部グラフにおいて，最大独立集合のサイズ

= ∣ V ∣ - 最大マッチングのサイズ

．

α (G) = ∣ V ∣ - ν (G)

注意 13.

これは

C

が頂点被覆

⟺

V ∖ C

が独立集合という補集合の関係と，König の定理を組み合わせたものです：

α (G) = ∣ V ∣ - τ (G) = ∣ V ∣ - ν (G)

7 Hall の定理 ― 完全マッチングの条件

定理 14 (Hall の結婚定理).

二部グラフ

(L, R, E)

が

L

の完全マッチング（

L

のすべての頂点がマッチされる）をもつための必要十分条件は，任意の

S \subseteq L

に対して

∣ N (S) ∣ \geq ∣ S ∣

が成り立つことです．ここで

N (S)

は

S

の隣接頂点の集合です．

注意 15 (Hall の条件の直感).

「どのグループの学生を見ても，その学生たちが応募可能な企業の数が学生数以上ある」ということです．もしある学生グループが応募できる企業数が学生数より少なければ，明らかに全員をマッチできません．驚くべきことに，この「明らかな」必要条件が十分条件でもあるのです．

8 競プロでの帰着パターン

注意 16 (AtCoder での二部グラフ).

競技プログラミングでは，問題を二部グラフに帰着するパターンが頻出します：

二部マッチング：「最大いくつのペアを作れるか」→ 最大マッチング
最小頂点被覆：「最小いくつの点で全辺をカバーするか」→ König の定理で最大マッチングに帰着
最大独立集合：「互いに矛盾しない最大集合」→ $∣ V ∣ - ν (G)$
辺彩色：二部グラフの辺彩色数 = 最大次数（König の辺彩色定理）

これらはすべて多項式時間で解けるというのが，二部グラフの魔法です．

9 まとめ ― なぜ二部グラフは特別なのか

二部グラフ $⟺$ 奇数閉路がない $⟺$ 2色で塗れる
König の定理により，最大マッチング = 最小頂点被覆
その帰結として，最大独立集合もマッチングから求められる
彩色数は自明に2
一般グラフで NP 完全な問題の多くが，二部グラフでは多項式時間で解ける

奇数閉路がないというたったひとつの構造的性質が，これほど多くの恩恵をもたらす ― これが二部グラフの魔法の正体です．

次の記事では，グラフの「かたち」そのものに注目します．平面グラフの驚くべき性質と四色定理について考えます．

グラフ理論離散数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

二部グラフの魔法 ― なぜ二部グラフではすべてが上手くいくのか

1 二部グラフとは

2 奇数閉路がない ― たったこれだけ

3 マッチング ― 二部グラフの華

4 König の定理 ― マッチングと被覆の双対性

5 彩色 ― 一般グラフの NP 完全が二部では自明に

6 独立集合 ― König と補集合の関係

7 Hall の定理 ― 完全マッチングの条件

8 競プロでの帰着パターン

9 まとめ ― なぜ二部グラフは特別なのか

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ