部分グラフ

同義語：subgraph

概要

定義

本記事では、特に断らない限り、ループも平行辺も持たない無向の単純グラフを扱う。グラフ $G=(V,E)$ は頂点の集合 $V=V(G)$ と辺の集合 $E=E(G)\subset[V]^2$ の組であり、$[V]^2$ は $V$ の相異なる 2 元からなる部分集合全体を表す。辺 $\{u,v\}$ を $uv$ とも書く。有向グラフ・多重グラフの場合は後述の注意で述べる。

部分グラフの定義

グラフ $H=(W,F)$ がグラフ $G=(V,E)$ の部分グラフ（subgraph）であるとは、
$$W\subset V,\qquad F\subset E$$
が成り立つことをいう。このとき $H\subset G$ と書き、$G$ を $H$ の超グラフ（supergraph）ともいう。$H\subset G$ かつ $H\neq G$ のとき、$H$ を $G$ の真部分グラフ（proper subgraph）という。

$H$ がグラフであることから $F\subset[W]^2$、すなわち $H$ の各辺の両端点は $W$ に属する。したがって部分グラフは、$G$ から頂点と辺を取り除いて得られるグラフであって、辺を残すならその両端点も残す、という条件を満たすものにほかならない。本記事の $\subset$ は等号を許す包含であり、$H\subset G$ は頂点集合・辺集合の文字どおりの包含を表す。

誘導部分グラフと全域部分グラフ

$G=(V,E)$ をグラフとする。

頂点集合 $W\subset V$ に対し、$W$ の頂点どうしを結ぶ $G$ の辺をすべて残した部分グラフ
$$G[W]:=\bigl(W,\ E\cap[W]^2\bigr)$$
を $W$ によって誘導される部分グラフ、または $W$ の誘導部分グラフ（induced subgraph）という。部分グラフ $H\subset G$ が誘導部分グラフであるとは、$H=G[V(H)]$ となることをいう。
$W=V$ である部分グラフ $(V,F)$ を $G$ の全域部分グラフ（spanning subgraph）という。

誘導部分グラフは「残す頂点」だけで決まり、全域部分グラフは「残す辺」だけで決まる。一般の部分グラフは両方を独立に選べる。

頂点と辺の削除

$G=(V,E)$ をグラフとする。頂点の集合 $S\subset V$ に対し、$S$ の頂点とそれに接続する辺をすべて取り除いた誘導部分グラフを
$$G-S:=G[V\setminus S]$$
と書く。辺の集合 $F\subset E$ に対し、頂点はすべて残して $F$ の辺だけを取り除いた全域部分グラフを
$$G-F:=(V,\ E\setminus F)$$
と書く。1 個の頂点 $v$、1 本の辺 $e$ については $G-v:=G-\{v\}$、$G-e:=G-\{e\}$ と略記する。

以上の用語と記法は Die17 §1.1 および BM08 第 2 章に従う。

直感

部分グラフとは、もとのグラフの図から頂点と辺を消して作るグラフである。ただし、辺だけを残してその端点を消すことはできない。集合の部分集合と違い、グラフでは頂点集合と辺集合を独立には選べず、辺を残すならその両端点も残さなければならない。また、頂点を選んだときにその間の辺をすべて残すか一部だけ残すかで、誘導部分グラフと一般の部分グラフが分かれる。一本の道、一つの閉路、探索木、連結成分(グラフ)はいずれも、もとのグラフの内部にある部分グラフとして扱える。

例と反例

一本の辺

$uv\in E(G)$ なら、頂点集合 $\{u,v\}$ と辺集合 $\{uv\}$ からなるグラフは $G$ の部分グラフであり、$G[\{u,v\}]$ に等しい誘導部分グラフである。頂点集合 $\{u,v\}$ だけを取り、辺集合を空にしたグラフも $G$ の部分グラフだが、これは誘導部分グラフではない。

道と閉路の部分グラフ

$G$ の中の道 $v_0,v_1,\dots,v_k$ は、頂点 $v_0,\dots,v_k$ と辺 $v_{i-1}v_i$（$1\le i\le k$）からなる $G$ の部分グラフを定める。閉路も同様に部分グラフとして取り出せる。「$G$ が道や閉路を含む」とは、通常この意味、またはそれと同型（グラフ同型）な部分グラフを含むという意味である。

全域木の例

連結グラフ $G$ の全域木 $T$ とは、$G$ の全域部分グラフであって木であるものをいう。すなわち $V(T)=V(G)$、$E(T)\subset E(G)$ で、$T$ は連結かつ閉路を持たない。頂点はすべて残し、連結性を保つのに必要な辺だけを選んだ部分グラフである。

誘導部分グラフでない部分グラフ

三角形 $K_3$（頂点 $a,b,c$、辺 $ab,bc,ca$）の 3 頂点をすべて残し、辺 $ab,bc$ だけを残した長さ 2 の道 $P$ は $K_3$ の全域部分グラフである。しかし $P$ は辺 $ca$ を含まないので $P\neq K_3[\{a,b,c\}]=K_3$ であり、誘導部分グラフではない。

自分自身と空グラフ

任意のグラフ $G$ は $G\subset G$ を満たすので自分自身の部分グラフである。頂点集合が空のグラフを許す流儀では、それはすべてのグラフの部分グラフである。$G$ の任意の頂点集合 $W$ に対し、辺を持たないグラフ（空グラフ） $(W,\emptyset)$ も $G$ の部分グラフである。

反例：端点を欠く辺集合

$uv\in E(G)$ とする。頂点集合 $\{u\}$、辺集合 $\{uv\}$ という組は、辺 $uv$ の端点 $v$ が頂点集合に属さないのでグラフではなく、したがって $G$ の部分グラフでもない。満たす性質：頂点集合は $V(G)$ の部分集合、辺集合は $E(G)$ の部分集合である。満たさない定義条件：グラフである（各辺の両端点が頂点集合に属する）。破る含意：「頂点集合と辺集合がそれぞれ部分集合 ⇒ 部分グラフ」は成り立たない。

反例：準同型像

グラフ準同型 $f\colon G\to K$（隣接する頂点を隣接する頂点へ写す写像）が存在しても、$G$ が $K$ の部分グラフであるとは限らない。たとえば長さ 4 の閉路 $C_4$ から 1 本の辺 $K_2$ への準同型は存在する（頂点を交互に 2 つの端点へ写す）が、$C_4$ は $K_2$ の部分グラフではなく、$K_2$ と同型な部分グラフでもない（頂点数が多い）。満たす性質：$G$ から $K$ への準同型が存在する。満たさない性質：$G$ は $K$ の部分グラフ（または $K$ の部分グラフと同型）である。破る含意：「準同型が存在する ⇒ 部分グラフである」は成り立たない。準同型は頂点を同一視できるが、部分グラフは文字どおりの包含を要求する。

性質

部分グラフ関係の順序性

部分グラフ関係 $\subset$ は、グラフの間の関係として反射的・反対称的・推移的である。すなわち、任意のグラフ $G,H,K$ について、$G\subset G$ であり、$H\subset G$ かつ $G\subset H$ ならば $H=G$ であり、$K\subset H$ かつ $H\subset G$ ならば $K\subset G$ である。したがって、固定したグラフ $G$ の部分グラフ全体は $\subset$ に関して半順序集合をなす。

反射性：$G=(V,E)$ に対して $V\subset V$、$E\subset E$ だから $G\subset G$ である。
反対称性：$H=(W,F)\subset G=(V,E)$ かつ $G\subset H$ なら、$W\subset V$ かつ $V\subset W$ より $W=V$、同様に $F=E$ なので $H=G$ である。
推移性：$K=(U,D)\subset H=(W,F)$ かつ $H\subset G=(V,E)$ なら $U\subset W\subset V$、$D\subset F\subset E$ である。よって $K\subset G$ である。$\square$

「同型を除いて部分グラフである」という関係では、反対称性は文字どおりの等号ではなく同型までしか成り立たない。本記事の $H\subset G$ は頂点集合と辺集合を固定した包含である。

合併と共通部分

$H_1=(W_1,F_1)$、$H_2=(W_2,F_2)$ が $G$ の部分グラフなら、
$$H_1\cup H_2:=(W_1\cup W_2,\ F_1\cup F_2),\qquad H_1\cap H_2:=(W_1\cap W_2,\ F_1\cap F_2)$$
はいずれもグラフであり、$G$ の部分グラフである。さらに $H_1\cap H_2\subset H_i\subset H_1\cup H_2$（$i=1,2$）が成り立つ。

$W_1,W_2\subset V(G)$、$F_1,F_2\subset E(G)$ だから、それぞれの合併と共通部分も $V(G)$、$E(G)$ の部分集合である。グラフであることを確かめる。$e\in F_1\cup F_2$ なら $e$ は $F_1$ または $F_2$ に属し、その両端点はそれぞれ $W_1$ または $W_2$ に属するので $W_1\cup W_2$ に属する。$e\in F_1\cap F_2$ なら、その両端点は $W_1$ にも $W_2$ にも属するので $W_1\cap W_2$ に属する。よって $H_1\cup H_2$、$H_1\cap H_2$ はグラフであり、$G$ の部分グラフである。最後の包含は集合の包含 $W_1\cap W_2\subset W_i\subset W_1\cup W_2$、$F_1\cap F_2\subset F_i\subset F_1\cup F_2$ から従う。$\square$

合併は辺集合を合わせる操作であり、結果が連結とは限らない。共通の頂点を持つ 2 つの連結な部分グラフの合併は連結だが、互いに頂点を共有しなければ合併は非連結である。

道・閉路・二部性の保存

$H\subset G$ とする。

$H$ の任意の歩道・道・閉路は、$G$ でもそれぞれ歩道・道・閉路である。
$G$ が閉路を持たなければ（森であれば）、$H$ も閉路を持たない。
$G$ が二部グラフなら $H$ も二部グラフである（二部グラフの記事も参照）。

$H$ の歩道 $v_0,e_1,v_1,\dots,e_k,v_k$ が使う頂点 $v_i$ は $V(H)\subset V(G)$ に、辺 $e_i$ は $E(H)\subset E(G)$ に属し、$e_i$ が $v_{i-1}$ と $v_i$ を結ぶという条件は $G$ でも同じである。道・閉路であることは頂点の相異なりに関する条件であり、これも変わらない。
$H$ が閉路を持てば、(1) によりそれは $G$ の閉路である。対偶をとればよい。
$\{A,B\}$ を $G$ の二部分割とすると、$\{A\cap V(H),\ B\cap V(H)\}$ は $H$ の二部分割である。実際、$H$ の各辺は $G$ の辺なので端点を $A$ と $B$ に一つずつ持ち、両端点は $V(H)$ に属する。$\square$

逆向きは一般に成り立たない。$G$ が閉路を持っていても、その閉路の辺を 1 本取り除いた部分グラフ $G-e$ はその閉路を失う。連結性も部分グラフをとると失われうる一方、非連結なグラフが連結な部分グラフ（たとえば 1 本の辺）を持つことはある。
次数(グラフ)についても同様の単調性が成り立つ。$H\subset G$ かつ $v\in V(H)$ ならば、$v$ に接続する $H$ の辺はすべて $G$ の辺なので $d_H(v)\le d_G(v)$ である。等号は必ずしも成り立たず、$v$ を残して接続辺を取り除けば次数は下がる。誘導部分グラフ $G[W]$ では $W$ の内部の辺はすべて残るので、$d_{G[W]}(v)$ は $v$ の隣接頂点のうち $W$ に属するものの個数である。
次は、指定したグラフを部分グラフとして含まないという条件が辺数を制限することを示す最初の例であり、Mantel の定理として知られる（Wes01 定理 1.3.23、Bol02 第 IV 章）。

三角形を含まないグラフの辺数の上界

$G$ を $n$ 頂点の有限グラフとする。$G$ が三角形 $K_3$ と同型な部分グラフを持たなければ
$$|E(G)|\le\left\lfloor\frac{n^2}{4}\right\rfloor$$
である。言い換えれば、$|E(G)|>\lfloor n^2/4\rfloor$ ならば $G$ は三角形を部分グラフとして含む。上界は最良であり、完全二部グラフ $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ は三角形を含まず、ちょうど $\lfloor n^2/4\rfloor$ 本の辺を持つ。

$G=(V,E)$ が三角形を含まないとし、頂点 $x$ の次数を $d(x)$ と書く。辺 $xy\in E$ に対し、$x$ と $y$ の両方に隣接する頂点 $z$ が存在すれば $x,y,z$ が三角形をなすので、$x$ の隣接頂点の集合と $y$ の隣接頂点の集合は交わらない。よって
$$d(x)+d(y)\le n\qquad(xy\in E)$$
である。これをすべての辺について加えると
$$\sum_{xy\in E}\bigl(d(x)+d(y)\bigr)\le n|E|$$
となる。左辺において、頂点 $x$ の項 $d(x)$ は $x$ に接続する辺の個数、すなわち $d(x)$ 回現れるので、左辺は $\sum_{x\in V}d(x)^2$ に等しい。したがって
$$\sum_{x\in V}d(x)^2\le n|E|$$
である。一方、握手補題（次数(グラフ)の記事を参照）により $\sum_{x\in V}d(x)=2|E|$ であるから、Cauchy-Schwarzの不等式により
$$(2|E|)^2=\Bigl(\sum_{x\in V}d(x)\Bigr)^2\le n\sum_{x\in V}d(x)^2\le n^2|E|$$
が成り立つ。$|E|>0$ なら両辺を $4|E|$ で割って $|E|\le n^2/4$ を得る（$|E|=0$ なら不等式は明らか）。$|E|$ は整数だから $|E|\le\lfloor n^2/4\rfloor$ である。
最後に、$K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ は二部グラフなので閉路の長さがすべて偶数であり（二部グラフの記事を参照）、特に三角形を含まない。その辺数は $\lfloor n/2\rfloor\lceil n/2\rceil$ であり、$n$ が偶数なら $n^2/4$、奇数なら $(n^2-1)/4$、いずれも $\lfloor n^2/4\rfloor$ に等しい。$\square$

「含む」と同型

thm-subgraph-mantel のように「$G$ が $K_3$ を部分グラフとして含む」というとき、頂点の名前まで一致する包含 $K_3\subset G$ ではなく、$G$ のある部分グラフが $K_3$ とグラフ同型であることを意味するのが普通である。ラベル付きの包含 $H\subset G$ と、同型を除いた包含「$H\cong H'\subset G$ となる $H'$ が存在する」を区別しておくと、禁止部分グラフの議論が明確になる。

有向グラフと多重グラフの場合

有向グラフでは、残す辺の向き（始点と終点）を保ったまま頂点と辺を選ぶ。多重グラフでは、同じ端点の組を持つ複数の辺を個別に区別し、その一部だけを残すことができる。いずれの場合も部分グラフは「頂点と辺の部分集合を選び、辺に端点を対応させる写像をそれに制限したもの」として定義され、上で述べた順序性・合併と共通部分・道と閉路の保存はそのまま成り立つ。

補足

あるグラフ $F$（またはそれと同型なグラフ）を部分グラフや誘導部分グラフなどの部分構造として持たないという条件を禁止部分構造（forbidden substructure）という。特に、$F$ と同型なグラフを部分グラフとして持たない $n$ 頂点グラフの辺数の最大値を求める問題を禁止部分グラフ問題（forbidden subgraph problem）といい、thm-subgraph-mantel は $F=K_3$ の場合である。$F$ が完全グラフ $K_{r+1}$ の場合の答えを与えるのが Turánの定理で、極値グラフは完全 $r$-部グラフである（Bol02 第 IV 章、Die17 第 7 章）。一般に、ある部分構造を持つ、または持たないという条件のもとでグラフの辺数・最小次数・最大次数などを調べる分野を極値グラフ理論（extremal graph theory）という。
部分グラフの概念は、誘導部分グラフ、全域木、連結成分(グラフ)、マッチングのようにグラフ内部の構造を記述する基礎であり、切断点・橋・連結度の定義には頂点削除 $G-v$ と辺削除 $G-e$ が繰り返し現れる。また、部分グラフの辺を縮約することを許したグラフマイナーは、部分グラフ関係より粗い順序を与える。