マトロイドと貪欲法 ― グラフの奥にある構造

マトロイドの公理，グラフ的マトロイド，貪欲法の最適性定理，MSTの再解釈，マトロイド交差を証明付きで解説する．

2026年2月27日

1 マトロイドの定義

定義 1 (マトロイド).

有限集合

E

とその部分集合族

I \subseteq 2^{E}

の組

M = (E, I)

がマトロイド（matroid）であるとは，次の3条件を満たすことをいう：

(I1) 空集合： $\emptyset \in I$ ．
(I2) 遺伝性（hereditary property）： $I \in I$ かつ $J \subseteq I$ ならば $J \in I$ ．
(I3) 交換性質（augmentation property）： $I, J \in I$ かつ $∣ I ∣ < ∣ J ∣$ ならば，ある $e \in J ∖ I$ が存在して $I \cup {e} \in I$ ．

I

の元を独立集合（independent set）という．

注意 2.

交換性質 (I3) はベクトル空間における次の事実の抽象化である：

dim (span (I)) < dim (span (J))

ならば

J

の中に

I

に追加しても線形独立性を保つベクトルが存在する．

2 グラフ的マトロイド

定義 3 (グラフ的マトロイド).

グラフ

G = (V, E)

に対して，

M (G) = (E, I)

（ここで

I = {F \subseteq E ∣ (V, F) は閉路を持たない}

）を

G

のグラフ的マトロイド（graphic matroid）という．

定理 4.

M (G)

はマトロイドである．

証明.

(I1)：

(V, \emptyset)

は辺を持たないので閉路なし．

\emptyset \in I

．

(I2)：

F

が閉路を持たないならば

F^{'} \subseteq F

も閉路を持たない．遺伝性が成り立つ．

(I3)：

I, J \in I

，

∣ I ∣ < ∣ J ∣

とする．

(V, I)

は

∣ I ∣

本の辺を持つ森であり，連結成分の数は

∣ V ∣ - ∣ I ∣

である（木の辺数が頂点数

- 1

であることによる）．同様に

(V, J)

の連結成分数は

∣ V ∣ - ∣ J ∣ < ∣ V ∣ - ∣ I ∣

なので，

(V, J)

は

(V, I)

より少ない連結成分を持つ．

よって

(V, I)

のある連結成分

C

の2頂点を

(V, J)

内で結ぶ辺

e \in J ∖ I

が存在する．

e

を

I

に加えてもこの辺は

C

の2つの連結成分を結ぶのではなく新たな閉路は生じないが，実はより正確には，

J

の辺で

(V, I)

の異なる2つの連結成分を結ぶ辺

e

が存在する（鳩の巣原理による）．この

e

を

I

に加えても閉路は生じないので

I \cup {e} \in I

． □

定義 5 (ランク関数).

マトロイド

M = (E, I)

に対して，

S \subseteq E

のランクを

r (S) = max {∣ I ∣ ∣ I \subseteq S, I \in I}

で定める．

r (E)

を

M

のランクという．グラフ的マトロイドでは

r (E) = ∣ V ∣ - c

（

c

は連結成分数）．

3 貪欲法の最適性

定義 6 (重み付きマトロイドの最適化問題).

マトロイド

M = (E, I)

と重み関数

w : E \to R_{\geq 0}

が与えられたとき，

w (I) = \sum_{e \in I} w (e)

を最大にする（または最小にする）基を求める問題を考える．ここで基（basis）とは極大独立集合のことである．

定理 7 (貪欲法の最適性定理（Rado, 1957; Edmonds, 1971）).

M = (E, I)

をマトロイド，

w : E \to R_{\geq 0}

を重み関数とする．

E

の元を重みの降順

w (e_{1}) \geq w (e_{2}) \geq \dots \geq w (e_{m})

に並べ，貪欲法

I_{0} = \emptyset, I_{k} = {I_{k - 1} \cup {e_{k}} I_{k - 1} I_{k - 1} \cup {e_{k}} \in I のとき otherwise

で得られる

I_{m}

は

w (I_{m}) = max {w (I) ∣ I \in I}

を達成する．

証明.

I^{*} \in I

を最適な独立集合とし，

I_{m}

が最適でないと仮定する．貪欲法で選ばれた元を

a_{1}, a_{2}, \dots, a_{r}

（

w (a_{1}) \geq \dots \geq w (a_{r})

），

I^{*}

の元を重み降順に

b_{1}, b_{2}, \dots, b_{s}

とする．

j

を

w (a_{j}) < w (b_{j})

となる最初の添字とする（そのような

j

が存在しなければ

w (I_{m}) \geq w (I^{*})

）．

J = {b_{1}, \dots, b_{j}}

，

I = {a_{1}, \dots, a_{j - 1}}

とおくと

∣ I ∣ < ∣ J ∣

かつ

I, J \in I

．交換性質 (I3) より，ある

b_{k} \in J ∖ I

が存在して

I \cup {b_{k}} \in I

．

w (b_{k}) \geq w (b_{j}) > w (a_{j})

であり，

b_{k}

は

a_{1}, \dots, a_{j - 1}

の後で（重みの降順で）

e_{a_{j}}

より先に現れるはずだが，貪欲法がこれを選ばなかったことに矛盾する（

I \cup {b_{k}} \in I

なので選べたはず）． □

4 逆の成立

定理 8 (マトロイドの特徴づけ).

有限集合

E

と遺伝性を満たす部分集合族

I

（

\emptyset \in I

）について，「任意の重み関数

w : E \to R_{\geq 0}

に対して貪欲法が最適解を与える」ならば

(E, I)

はマトロイドである．

証明.

対偶を示す．

(E, I)

がマトロイドでない，すなわち交換性質 (I3) が破れるとする．

I, J \in I

，

∣ I ∣ < ∣ J ∣

で，任意の

e \in J ∖ I

に対して

I \cup {e} \in / I

となるものが存在する．

重みを

w (e) = 1 + ε

（

e \in I

のとき），

w (e) = 1

（

e \in J ∖ I

のとき），

w (e) = 0

（その他）と設定する（

ε > 0

は十分小さい）．貪欲法は

I

の元を先に選び，

J ∖ I

の元を追加できないので

w (I_{m}) \leq ∣ I ∣ (1 + ε)

．一方

w (J) = ∣ I \cap J ∣ (1 + ε) + ∣ J ∖ I ∣ \geq ∣ J ∣ > ∣ I ∣ (1 + ε)

（

ε

が十分小なら）．よって貪欲法は最適でない． □

5 Krustalアルゴリズムの再解釈

注意 9.

連結グラフ

G = (V, E)

に重み

w : E \to R_{> 0}

が与えられたとき，最小全域木（MST）を求める Kruskal のアルゴリズムは，辺を重みの昇順に並べ，閉路を作らない辺を貪欲に追加する手続きである．

これはグラフ的マトロイド

M (G)

上で重みを

w^{'} = - w

として最大重み基を求める貪欲法そのものである．貪欲法の最適性定理により，Krustal のアルゴリズムは MST を正しく求める．

graph TD
    A["マトロイド (E, I)"] --> B["グラフ的マトロイド"]
    A --> C["線形マトロイド"]
    A --> D["一様マトロイド"]
    B --> E["Kruskal = 貪欲法"]
    C --> F["線形独立性"]
    E --> G["MST"]

6 マトロイド交差

定義 10 (マトロイド交差).

2つのマトロイド

M_{1} = (E, I_{1})

，

M_{2} = (E, I_{2})

（同じ台集合

E

）が与えられたとき，

I_{1} \cap I_{2}

の中で最大の集合を求める問題をマトロイド交差問題（matroid intersection problem）という．

定理 11 (マトロイド交差定理（Edmonds, 1970年）).

max {∣ I ∣ ∣ I \in I_{1} \cap I_{2}} = S \subseteq E min (r_{1} (S) + r_{2} (E ∖ S))

ここで

r_{1}, r_{2}

はそれぞれ

M_{1}, M_{2}

のランク関数である．

注意 12.

マトロイド交差は二部マッチング（2つの分割マトロイドの交差）やアーボレセンスなど多くの組合せ最適化問題を統一的に扱える枠組みを提供する．ただし3つ以上のマトロイドの交差問題は一般に NP 困難であることが知られている．マトロイド交差は多項式時間アルゴリズムが存在し，組合せ最適化における「扱いやすさの境界」を特徴づける重要な概念である．

マトロイドと貪欲法 ― グラフの奥にある構造

1 マトロイドの定義

2 グラフ的マトロイド

3 貪欲法の最適性

4 逆の成立

5 Krustalアルゴリズムの再解釈

6 マトロイド交差

関連する「教科書の行間」記事

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

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

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

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

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