ハイパーグラフ

同義語：hypergraph

概要

前提知識: グラフ, 集合族, 彩色

グラフの辺はちょうど 2 個の頂点を結ぶ。辺が 3 個以上の頂点を一度に含んでもよいとしたものがハイパーグラフである。有限幾何の点と直線、$\{1,\dots,N\}$ の中の等差数列、集合の族など、「どの部分集合を一組とみなすか」を記録したいときに自然に現れる。グラフの記事の例「反例：3 頂点を同時に結ぶ辺」が述べるとおり、そのような辺はグラフの辺ではない。
ハイパーグラフについての問いの多くは、グラフの彩色・マッチング・頂点被覆の問いを辺の大きさが一般の場合に広げたものである。2-彩色可能性については確率論的方法の記事が、辺の少ないハイパーグラフと、辺どうしの交わりの少ないハイパーグラフが 2-彩色可能であることを示している。この記事では、定義と例を述べたあと、彩色数の上界（prop-hg-two-section）、マッチング数・横断数・分数横断数のあいだの不等式（thm-hg-basic-inequalities）、貪欲法で選んだ横断の大きさの評価（thm-hg-greedy）を証明する。

定義

ハイパーグラフ

集合 $V$ と、$V$ の空でない部分集合からなる集合 $E$ の組 $\mathcal H=(V,E)$ を ハイパーグラフ（hypergraph）という。$V$ の元を $\mathcal H$ の頂点、$E$ の元を $\mathcal H$ の辺という。$V$ と $E$ がともに有限であるとき、$\mathcal H$ は有限であるという。

すべての辺の元の個数が $k$ であるとき、$\mathcal H$ は $k$-一様（$k$-uniform）であるという。
頂点 $v$ を含む辺の個数 $d(v)$ を $v$ の次数といい、その最大値を $\Delta(\mathcal H)$ と書く。すべての頂点の次数が $d$ であるとき、$\mathcal H$ は $d$-正則であるという。
辺の元の個数の最大値を $\mathcal H$ のランクといい、$r(\mathcal H)$ と書く。

この記事では、とくに断らない限りハイパーグラフは有限とする。2-一様なハイパーグラフは、グラフの記事の定義のグラフと同じものである。同じ部分集合を辺として何度も数えたいときは、辺を $V$ の部分集合で添字付けた族（集合族の記事の定義「添字付き集合族」）とし、多重ハイパーグラフとよぶ。Die25 §1.10（p. 27）も辺を「任意の濃度の空でない部分集合」としている。

接続行列と双対

$V=\{v_1,\dots,v_n\}$、$E=\{e_1,\dots,e_m\}$ とする。$v_i\in e_j$ なら $1$、そうでなければ $0$ を $(i,j)$ 成分とする $n\times m$ 行列 $B$ を $\mathcal H$ の接続行列という。$V$ と $E$ を 2 つの部とし、$v\in e$ のとき $v$ と $e$ を結んだ二部グラフを $\mathcal H$ の接続グラフという。
$\mathcal H$ のどの頂点も少なくとも 1 本の辺に含まれるとき、$E$ を頂点の集合とし、各 $v\in V$ について $v^{*}:=\{e\in E\mid v\in e\}$ を辺とする多重ハイパーグラフ $\mathcal H^{*}$ を $\mathcal H$ の双対という。その接続行列は $B$ の転置である。

接続行列 $B$ の行の和は頂点の次数、列の和は辺の大きさである。接続グラフは、頂点と辺の「含む・含まれる」の関係だけを記録したもので、$\mathcal H$ と同じ情報をもつ。双対をとることは、接続グラフの 2 つの部の役割を入れ替えることにあたる。

例

基本的なハイパーグラフ

完全 $k$-一様ハイパーグラフ $K_n^{(k)}$：$V=\{1,\dots,n\}$、$E$ を $V$ の $k$ 元部分集合の全体とする。各頂点の次数は $\binom{n-1}{k-1}$ で、$\binom{n-1}{k-1}$-正則である。$K_n^{(2)}$ は完全グラフ $K_n$ である。
Fano 平面：$V$ を体 $\mathbb F_2$ 上の 3 次元ベクトル空間 $\mathbb F_2^3$ の $0$ でない 7 個のベクトルとし、2 次元部分空間 $W$ ごとに $W\setminus\{0\}$（3 元）を辺とする。2 次元部分空間は 7 個あり、相異なる 2 点 $x,y$ はちょうど 1 本の辺 $\{x,y,x+y\}$ に乗る。相異なる 2 つの 2 次元部分空間の共通部分は、次元の公式から 1 次元なので、相異なる 2 辺はちょうど 1 点で交わる。3-一様、3-正則で、辺は 7 本である。
等差数列のハイパーグラフ：$V=\{1,\dots,N\}$ とし、$k$ 項の等差数列（公差 $1$ 以上）の項の集合を辺とする。2 色の彩色で単色の辺がないことは、どちらの色にも $k$ 項の等差数列がないことである。van der Waerdenの定理は、$N$ が十分大きければこのハイパーグラフが 2-彩色可能でないことを述べている。
グラフの三角形：グラフ $G$ の頂点を頂点とし、$G$ の三角形の頂点の集合を辺とすると、3-一様なハイパーグラフが得られる。

次数の和

有限なハイパーグラフ $\mathcal H=(V,E)$ について
$$ \sum_{v\in V}d(v)=\sum_{e\in E}\lvert e\rvert $$
である。とくに $\mathcal H$ が $k$-一様なら $\sum_v d(v)=k\lvert E\rvert$ であり、さらに $d$-正則なら $d\lvert V\rvert=k\lvert E\rvert$ である。

$v\in e$ となる組 $(v,e)$ の個数を 2 通りに数える。頂点 $v$ ごとに数えると $d(v)$ 個、辺 $e$ ごとに数えると $\lvert e\rvert$ 個である。言い換えると、両辺はどちらも接続行列の成分の和である。$\square$

2-一様の場合は握手補題である。Fano 平面では $3\cdot7=3\cdot7$、$K_n^{(k)}$ では $n\binom{n-1}{k-1}=k\binom nk$ となる。

彩色

彩色と彩色数

$q$ を正の整数とする。写像 $c\colon V\to\{1,\dots,q\}$ が $\mathcal H$ の $q$-彩色であるとは、元が 2 個以上のどの辺 $e$ も単色でない（$c$ が $e$ 上で定数でない）ことをいう。$q$-彩色が存在する最小の $q$ を $\mathcal H$ の彩色数といい、$\chi(\mathcal H)$ と書く。$\chi(\mathcal H)\le2$ のとき、$\mathcal H$ は 2-彩色可能であるという。

元が 1 個の辺は必ず単色になるので、定義から除いている。2-一様の場合、$q$-彩色は彩色の記事の定義「頂点彩色」の $q$ 色の頂点彩色と同じであり、$\chi(\mathcal H)$ は彩色数である。グラフの彩色では「隣り合う 2 頂点の色が違う」ことを求めるが、ハイパーグラフの彩色では「辺の中に色が 2 つ以上現れる」ことだけを求める。

2-切片による上界

$\mathcal H=(V,E)$ について、$V$ を頂点集合とし、相異なる 2 頂点が $\mathcal H$ のある辺に一緒に含まれるとき辺で結んだグラフを $\mathcal H$ の 2-切片 $G_2(\mathcal H)$ という。このとき $\chi(\mathcal H)\le\chi(G_2(\mathcal H))$ であり、$\mathcal H$ が 2-一様なら等号が成り立つ。

$c$ を $G_2(\mathcal H)$ の $q$ 色の頂点彩色とする。元が 2 個以上の辺 $e$ は相異なる 2 頂点 $u,w$ を含み、$u,w$ は $G_2(\mathcal H)$ で隣接するので $c(u)\ne c(w)$ であり、$e$ は単色でない。よって $c$ は $\mathcal H$ の $q$-彩色である。2-一様なら $G_2(\mathcal H)$ は $\mathcal H$ そのもので、両辺は等しい。$\square$

完全一様ハイパーグラフの彩色数

$k\ge2$ のとき $\chi(K_n^{(k)})=\lceil n/(k-1)\rceil$ である。写像 $c$ が $K_n^{(k)}$ の彩色であることは、どの $k$ 元部分集合も単色でないこと、すなわち各色の頂点が $k-1$ 個以下であることと同値だからである。$q$ 色で $n$ 個の頂点を塗り各色 $k-1$ 個以下にできるのは、$q(k-1)\ge n$ のときちょうどである。
$G_2(K_n^{(k)})$ は $K_n$ で彩色数は $n$ なので、$k\ge3$ では prop-hg-two-section の不等式は一般に等号にならない。たとえば $\chi(K_5^{(3)})=3$ だが $\chi(K_5)=5$ である。

$k$-一様で 2-彩色可能でないハイパーグラフの辺の本数の最小値を $m(k)$ と書く。三角形 $K_3$ は 2 色で塗れず、辺が 2 本以下のグラフは閉路を含まない森(グラフ理論)で二部グラフなので、$m(2)=3$ である。確率論的方法の記事の命題「辺の少ないハイパーグラフの 2-彩色」は $m(k)\ge2^{k-1}$ を示し、同じ記事の例「反例の確かめ」は Fano 平面が 2-彩色可能でないことを示している。よって $4\le m(3)\le7$ である。

マッチングと横断

マッチング・横断・分数横断

$\mathcal H=(V,E)$ を有限なハイパーグラフとする。

どの 2 本も交わらない辺の集合 $M\subset E$ をマッチングといい、その元の個数の最大値を $\nu(\mathcal H)$ と書く。
すべての辺と交わる頂点の集合 $T\subset V$ を横断（transversal）といい、その元の個数の最小値を横断数 $\tau(\mathcal H)$ という。
写像 $w\colon V\to[0,\infty)$ で、すべての辺 $e$ について $\sum_{v\in e}w(v)\ge1$ を満たすものを分数横断といい、$\sum_{v\in V}w(v)$ の下限を分数横断数 $\tau^{*}(\mathcal H)$ という。

$E=\emptyset$ なら $\nu=\tau=\tau^{*}=0$ である。横断 $T$ の指示関数（$T$ の上で $1$、外で $0$）は分数横断である。2-一様の場合、$\nu$ はグラフのマッチング数（マッチング(グラフ理論)）、横断は頂点被覆である。二部グラフでは両者が等しいことが König の定理として知られている（独立集合(グラフ) の記事を参照）。

マッチング数と横断数の不等式

$\mathcal H$ を辺が 1 本以上ある有限なハイパーグラフ、$r=r(\mathcal H)$ をそのランクとする。このとき
$$ \nu(\mathcal H)\le\tau^{*}(\mathcal H)\le\tau(\mathcal H)\le r\,\nu(\mathcal H) $$
である。

1 つ目．$M$ をマッチング、$w$ を分数横断とする。$M$ の辺は互いに交わらないので、各頂点は $M$ の高々 1 本の辺にしか含まれない。$w\ge0$ だから
$$ \lvert M\rvert\le\sum_{e\in M}\sum_{v\in e}w(v)\le\sum_{v\in V}w(v) $$
である。$w$ についての下限をとれば $\lvert M\rvert\le\tau^{*}$ となり、$M$ を最大のマッチングにとれば $\nu\le\tau^{*}$ である。
2 つ目．最小の横断の指示関数は分数横断で、その値の和は $\tau$ である。
3 つ目．最大のマッチング $M$ をとり、$M$ の辺の和集合を $U$ とする。$\lvert U\rvert\le r\lvert M\rvert=r\nu$ である。$U$ と交わらない辺 $e$ があったとする。$e$ は空でないので $M$ の辺ではなく（$M$ の辺は $U$ に含まれる）、$M\cup\{e\}$ は $M$ より大きいマッチングになり、$M$ の最大性に反する。よって $U$ は横断で、$\tau\le\lvert U\rvert\le r\nu$ である。$\square$

等号と真の不等号

$k\ge2$、$n=2k-1$ とし、$K_{2k-1}^{(k)}$ を考える。$k$ 元部分集合の 2 つは、合わせて $2k>n$ 個の元をもつことはできないので交わり、$\nu=1$ である。$k-1$ 個以下の頂点の集合 $T$ の補集合は $k$ 個以上の元をもち、$T$ と交わらない辺を含むので、$T$ は横断でない。$k$ 個の頂点の集合の補集合は $k-1$ 個の元しかもたず辺を含まないので、横断である。よって $\tau=k=r\nu$ であり、thm-hg-basic-inequalities の最後の不等式は等号になりうる。
$n\ge k$ とし、$K_n^{(k)}$ で、どの頂点にも $1/k$ をおくと分数横断になるので $\tau^{*}\le n/k$ である。逆に分数横断 $w$ について、すべての辺にわたって $\sum_{v\in e}w(v)\ge1$ を足すと、各頂点は $\binom{n-1}{k-1}$ 本の辺に含まれるので $\binom{n-1}{k-1}\sum_vw(v)\ge\binom nk$、すなわち $\sum_vw(v)\ge n/k$ である。よって $\tau^{*}(K_n^{(k)})=n/k$ で、$n=2k-1$ のとき $1< \frac{2k-1}{k}< k$ となり、最初の 2 つの不等式はどちらも真の不等号になりうる。
Fano 平面では、相異なる 2 辺は必ず交わるので $\nu=1$ である。1 本の辺はほかのすべての辺と交わるので横断で、$\tau\le3$ である。相異なる 2 点 $x,y$ について、$x$ を含む辺と $y$ を含む辺は 3 本ずつで、辺 $\{x,y,x+y\}$ を共有するので、$\{x,y\}$ と交わる辺は 5 本で、7 本すべてとは交わらない。よって $\tau=3=r\nu$ である。

貪欲法による横断

最小の横断を求めるには、すべての頂点の部分集合を調べる必要があり、頂点が多いと現実的でない。次の手順は、まだ横断していない辺を最も多く含む頂点を 1 つずつ選んでいく。
貪欲法．$T_0:=\emptyset$ とする。$T_{i-1}$ と交わらない辺が残っている間、$T_{i-1}$ と交わらない辺を最も多く含む頂点 $v_i$ を 1 つ選び（同数なら任意）、$T_i:=T_{i-1}\cup\{v_i\}$ とする。残る辺がなくなった時点の $T_t$ を出力する。
各段で $T_{i-1}$ と交わらない辺 $e$ の頂点はその辺を含むので、選んだ $v_i$ は少なくとも 1 本の新しい辺と交わる。辺は有限個なので手順は $\lvert E\rvert$ 段以内で止まり、出力 $T_t$ は横断である。正の整数 $m$ について、$h_m:=1+\frac12+\cdots+\frac1m$ とおく（Eulerの定数の記事の調和数）。

貪欲法による横断の評価

$\mathcal H$ を辺が 1 本以上ある有限なハイパーグラフ、$\Delta=\Delta(\mathcal H)$ とする。貪欲法の出力 $T_t$ は
$$ \lvert T_t\rvert\le h_\Delta\,\tau^{*}(\mathcal H) $$
を満たす。とくに $\tau(\mathcal H)\le h_\Delta\,\tau^{*}(\mathcal H)\le(1+\log\Delta)\,\tau^{*}(\mathcal H)$ である。

新しく横断した辺に代価を割り振る

代価．第 $i$ 段で選んだ $v_i$ が新しく交わる辺（$v_i$ を含み $T_{i-1}$ と交わらない辺）の本数を $a_i$ とする。$a_i\ge1$ である。各辺 $e$ はちょうど 1 つの段で初めて横断されるので、その段を $i$ として $e$ の代価を $p(e):=1/a_i$ と定める。第 $i$ 段で初めて横断される辺の代価の和は $a_i\cdot\frac1{a_i}=1$ なので
$$ \sum_{e\in E}p(e)=t $$
である。
1 つの頂点のまわりの代価．頂点 $v$ を固定し、$v$ を含み $T_i$ と交わらない辺の本数を $s_i$ とする（$s_0=d(v)$、$s_t=0$）。第 $i$ 段で初めて横断される $v$ を含む辺は $s_{i-1}-s_i$ 本ある。$s_{i-1}\ge1$ のとき、$v$ 自身が第 $i$ 段で $T_{i-1}$ と交わらない辺を $s_{i-1}$ 本含む候補なので、$v_i$ の選び方から $a_i\ge s_{i-1}$ であり、これらの辺の代価は $1/s_{i-1}$ 以下である。$s_{i-1}=0$ の段ではそのような辺はない。$s_i< j\le s_{i-1}$ の各 $j$ について $\frac1j\ge\frac1{s_{i-1}}$ なので
$$ \sum_{e\ni v}p(e)\le\sum_{i:\,s_{i-1}\ge1}\frac{s_{i-1}-s_i}{s_{i-1}}\le\sum_{i=1}^{t}\ \sum_{j=s_i+1}^{s_{i-1}}\frac1j=h_{d(v)}\le h_\Delta $$
である（$d(v)=0$ なら左辺は $0$）。真ん中の和は $j=1,\dots,s_0$ をちょうど 1 回ずつ数える。
分数横断との比較．$w$ を分数横断とする。各辺で $\sum_{v\in e}w(v)\ge1$、$p\ge0$ なので
$$ t=\sum_{e}p(e)\le\sum_{e}p(e)\sum_{v\in e}w(v)=\sum_{v}w(v)\sum_{e\ni v}p(e)\le h_\Delta\sum_{v}w(v) $$
である。$w$ について下限をとれば $t\le h_\Delta\tau^{*}$ となる。最後に、$j\ge2$ について $\frac1j\le\int_{j-1}^{j}\frac{dx}x$ なので $h_\Delta\le1+\int_1^\Delta\frac{dx}x=1+\log\Delta$ である。$\square$

正則な一様ハイパーグラフの横断数

$k,d\ge1$ とし、$\mathcal H$ を $n$ 頂点の $k$-一様 $d$-正則なハイパーグラフとする。このとき $\tau^{*}(\mathcal H)=n/k$ であり、
$$ \frac nk\le\tau(\mathcal H)\le\frac nk\,h_d $$
である。

どの頂点にも $1/k$ をおくと、各辺で和はちょうど $1$ なので分数横断で、$\tau^{*}\le n/k$ である。分数横断 $w$ について、すべての辺にわたって $\sum_{v\in e}w(v)\ge1$ を足すと、左辺は各頂点を $d$ 回数えて $d\sum_vw(v)$、右辺は $\lvert E\rvert=dn/k$（prop-hg-handshake）なので $\sum_vw(v)\ge n/k$ である。よって $\tau^{*}=n/k$ で、thm-hg-basic-inequalities と thm-hg-greedy（$\Delta=d$）から残りが従う。$\square$

Fano 平面（$n=7$、$k=d=3$）では $\tau^{*}=7/3$ なので、$\tau$ は $7/3$ 以上の整数、すなわち $3$ 以上である。ex-hg-inequalities-sharp の 3 とは別の、数え上げによる下界の証明になっている。上界は $\frac73h_3=\frac{77}{18}$ である。

双対と集合被覆

thm-hg-greedy の証明は辺の重複を使っていないので、多重ハイパーグラフでもそのまま成り立つ。双対 $\mathcal H^{*}$ の横断は、$\mathcal H$ の辺の集合で、すべての頂点を覆うもの（各頂点がその中のどれかの辺に含まれるもの）にあたる。したがって、集合 $V$ を覆う部分集合の族 $e_1,\dots,e_m$ から、まだ覆っていない点を最も多く含む集合を順に選ぶと、選ぶ集合の個数は、分数的な被覆の最小値の $h_s$ 倍以下になる。ここで $s$ は $\lvert e_j\rvert$ の最大値で、$\mathcal H^{*}$ の最大次数にあたる。これは組合せ最適化の集合被覆問題の貪欲法の評価である。分数横断数は線形計画法の問題の最適値として計算できる。

条件を外したときの反例

外す条件	反例	成り立たなくなること
thm-hg-greedy で、各段に未横断の辺を最も多く含む頂点を選ぶこと	星：頂点 $c,a_1,\dots,a_m$（$m\ge2$）、辺 $\{c,a_i\}$。各段で $a_1,a_2,\dots$ を選ぶ	選んだ横断の大きさ $m$ が $h_\Delta\tau^{*}=h_m$ 以下
cor-hg-regular の正則性	同じ星（2-一様、$d(c)=m$、$d(a_i)=1$）	$\tau^{}=n/k$（$\tau^{}=1$、$n/k=(m+1)/2$）
prop-hg-two-section の等号での 2-一様性	$K_5^{(3)}$	$\chi(\mathcal H)=\chi(G_2(\mathcal H))$（$3\ne5$）
確率論的方法の命題「辺の少ないハイパーグラフの 2-彩色」の、辺が $2^{k-1}$ 本未満であること	Fano 平面（$k=3$、辺 $7\ge4$ 本）	2-彩色可能

反例の確かめ

1 行目．$\Delta=d(c)=m$ である。$c$ に $1$、ほかに $0$ をおくと分数横断なので $\tau^{*}\le1$、辺が 1 本以上あるので thm-hg-basic-inequalities から $\tau^{*}\ge\nu\ge1$、よって $\tau^{*}=1$ である。各段で $a_i$ を選ぶと新しく横断する辺は 1 本だけで、$m$ 段かかる。一方 $c$ は未横断の辺を $m\ge2$ 本含むので、貪欲法は最初に $c$ を選び 1 段で止まる。$m\ge2$ では $h_m< m$（$h_m\le1+\frac{m-1}2$）なので、評価が破れる。
2 行目．$n=m+1$、$k=2$ で、$\tau^{*}=1$ は 1 行目で示した。$m\ge2$ なら $(m+1)/2>1$ である。
3 行目．ex-hg-complete-chromatic による。
4 行目．確率論的方法の例「反例の確かめ」の 3 行目による。

補足

無限のハイパーグラフ：辺が無限集合であってもよいとすると、thm-hg-basic-inequalities の議論はそのままでは使えない。たとえば $V=\mathbb N$、辺を $\{j,j+1,j+2,\dots\}$（$j\in\mathbb N$）とすると、どの 2 辺も交わるので $\nu=1$ だが、有限集合 $T$ は $\max T$ より先から始まる辺と交わらないので、有限の横断はない。無限のグラフについては無限グラフを参照。
文献：ハイパーグラフの定義は Die25 §1.10（p. 27）にある。$r$-一様ハイパーグラフの定義は Zha23 の記法の章（p. xi）にある。