グラフ (離散数学)

数学のグラフ理論におけるグラフ（英: graph）とは数学的構造の一つ。対象の集合で、対象の一部が相互に何らかの脈絡で「関係している」ようなものをいう。ここで対象とは頂点（節点やノードとも）と呼ばれる抽象物であり、互いに関係のある頂点の対は辺（枝やエッジとも）と呼ばれる^[1]。一般的に、グラフは点または丸で表した頂点の集合に直線または曲線で辺を描き加えたダイアグラムで表現される。グラフは離散数学の研究対象の一つである。

辺には無向と有向の場合がある。例えば頂点をパーティ参加者として、2人が握手するとその間に辺が結ばれるとする場合、握手はお互い対等で行うものなので無向な辺といえる。対照的に、お金の貸し借り関係を辺とした場合、どちらか一方にのみ返済義務があるので有向な辺といえる。前者をグラフにしたものは無向グラフ (undirected graph) と呼ばれ、後者のグラフは有向グラフ (directed graph) と呼ばれる。

グラフはグラフ理論における基本的な研究対象である。「グラフ」という言葉は、1878年にジェームズ・ジョセフ・シルベスターによってこの意味で最初に使用された^[2]^[3]。

定義

グラフ理論における定義はさまざまである。以下、グラフや関連する数学的構造の定義で基本的なものを幾つか挙げる。

グラフ

グラフ（有向グラフと区別して「無向グラフ」とか、多重グラフと区別して「単純グラフ」とも呼ばれたりもする）テンプレート:Sfn^[4]とは順序対テンプレート:Math である。ここでテンプレート:Mvar は頂点 (vertex) と呼ばれる元の集合、テンプレート:Mvar は頂点の対の集合でありその元は辺 (edge) と呼ばれる。

辺テンプレート:Math} に含まれる頂点テンプレート:Mathとテンプレート:Math は、その辺の「端点」と呼ばれる。辺は頂点テンプレート:Math とテンプレート:Math を「結び (join)」、テンプレート:Math やテンプレート:Math に「接続する (incident)」と言い表す。頂点がいかなる辺にも含まれないこともあり、その場合は他のどの頂点とも結ばれていない。

頂点をそれ自身と結ぶ辺である「ループ（自己ループとも）」を許すグラフもある^[5]。このように一般化されたグラフは「ループ付きグラフ (graphs with loops)」と呼ばれる。文脈からループを許すことが自明な場合は単にグラフと呼んだりもする。

「多重グラフテンプレート:Enlink」とは、2つの頂点間に複数の辺がある「多重辺」を許すように一般化したグラフである^[6]。一部のテキストでは、多重グラフのことを単にグラフと呼んでいたりもするテンプレート:Sfn^[7]。多重辺を許すにあたり、上述の辺に関する定義を頂点対の（通常の）集合ではなく、頂点対の多重集合に変更する必要がある。

一般に、頂点テンプレート:Mvar の集合は有限集合と想定されており、これはまた辺の集合も有限集合だということも意味する。時には「無限グラフテンプレート:Enlink」が考慮されることもあるが、殆どの場合は特別な種類の二項関係だと見なされる、というのも有限グラフで得られた結果の大部分が無限のケースに拡張できなかったり、だいぶ異なる証明を必要とするためである。

空グラフとは、頂点の集合が空である（したがって辺の集合も空である）グラフをいう。頂点の数テンプレート:Mathをグラフの「位数」といい、辺の数テンプレート:Mathをグラフの「サイズ」という^[8]。ただし、アルゴリズムの計算複雑性を表現するなど一部の文脈では、サイズがテンプレート:Mathである（こうしないと、空ではないグラフのサイズが0となりえてしまう）。頂点の次数とは頂点に接続する辺の数のことで、ループ付きグラフの場合ループは2回カウントされる^[1]。

位数テンプレート:Math のグラフにおける、各頂点の最大次数はテンプレート:Math（ループが許される場合はテンプレート:Math ）、辺の最大数はテンプレート:Math（ループが許される場合はテンプレート:Math）となる。

グラフの辺は「隣接関係」と呼ばれる頂点間の対称関係を定義する。具体的には、テンプレート:Math が辺であれば、2つの頂点テンプレート:Math とテンプレート:Math は「隣接している (adjacent)」という。

一つのグラフは $n \times n$ の正方行列である隣接行列 $A$ によって完全に指定できる。 $A_{i j}$ は頂点テンプレート:Math と頂点テンプレート:Math をつなぐ接続の数を指定する。単純グラフの場合、 $A_{i j} \in {0, 1}$ であり、0と1が非接続と接続をそれぞれ表す。またこのとき $A_{i i} = 0$ である（つまりループを持たない）。ループ付きグラフは、一部または全ての $A_{i i}$ が正の整数になり、多重グラフ（頂点間に複数の辺がある）は一部または全ての $A_{i j}$ が正の整数になる。無向グラフの隣接行列は対称行列となる ( $A_{i j} = A_{j i}$ )。

有向グラフ

テンプレート:Main

有向グラフ (directed graph, digraph) は、辺に向きがあるグラフである。

限定的だが非常に一般的な意味においてテンプレート:Sfn、有向グラフは以下の条件を満たす対 $G = (V, E)$ として定義される。

$V$ は、頂点の集合
$E \subseteq {(x, y) ∣ (x, y) \in V^{2} and x \neq y}$ は辺の集合で、辺（有向辺とも言う）は頂点の順序対である。つまり1辺が異なる2頂点と関連している。

曖昧さを避けるため、この種類のグラフは厳密に「単純有向グラフ (directed simple graph)」と呼ぶ場合もある。

辺 $(x, y)$ は $x$ から $y$ の向きを表し、頂点 $x$ と $y$ はその辺の「端点」であるが、 $x$ は辺の「始点 (tail)」そして $y$ は辺の「終点 (head)」という^[9]。辺は $x$ と $y$ を「結び」、 $x$ と $y$ に「接続する」と表現される。頂点は、グラフ内にあっても辺を持たない場合もある。辺 $(y, x)$ は $(x, y)$ の「逆向辺 (inverted edge)」と呼ばれる。「多重辺」は、上述の定義だと許されないが、同じ始点と終点を持つ辺が複数あるものを言う。

多重辺を許す条件のより一般的な意味でテンプレート:Sfn、有向グラフは以下によって構成される順序三つ組 $G = (V, E, ϕ)$ として定義される。

$V$ は、頂点の集合
$E$ は、辺（有向辺とも言う）の集合
$ϕ : E \to {(x, y) ∣ (x, y) \in V^{2} and x \neq y}$ は全ての辺を頂点の順序対に写す写像「接続関数 (incidence function)」である。

曖昧さを避けるため、この種類のグラフは厳密に「多重有向グラフ(directed multigraph)」と呼ぶ場合もある。

「ループ」は始点と終点が同一な辺である。上述の2種類の定義においては有向グラフはループを持つことができない、なぜなら、辺 $(x, y)$ の定義に $x \neq y$ の条件があるので、頂点 $x$ と自分自身を結ぶループ（すなわち $(x, x)$ ）は辺の定義を満たさないためである。そのためループを許すには定義を拡張させる必要がある。有向単純グラフに対しては $E$ の定義を $E \subseteq {(x, y) ∣ (x, y) \in V^{2}}$ と修正し、有向多重グラフに対しては $ϕ$ の定義を $ϕ : E \to {(x, y) ∣ (x, y) \in V^{2}}$ と修正することになる。曖昧さを避けるため、これらの種類のグラフは厳密にそれぞれ「ループを許す単純有向グラフ (directed simple graph permitting loops)」そして「ループを許す多重有向グラフ（またはクイバー）」と呼ばれる場合もある。

ループを許す単純有向グラフ $G$ において、辺は $G$ の頂点に関する自己関係を成す。これを $\sim$ と表し、 $G$ の「隣接関係」と呼ぶ。具体的には、各辺 $(x, y)$ について、その端点 $x$ と $y$ は互いに「隣接する」と言い、 $x \sim y$ と表記される。

混合グラフ

テンプレート:Main 「混合グラフ (mixed graph) 」とは、一部の辺が有向、一部の辺が無向であるグラフ。混合単純グラフは順序三つ組テンプレート:Nowrap である。混合複合グラフはテンプレート:Nowrap の五つ組で、V, E (無向辺), A (有向辺), ϕ_E ,ϕ_A は上述にて定義したものである。有向グラフと無向グラフは混合グラフの特殊なケースである。

重み付きグラフ

「重み付きグラフ (weighed graph)」もしくは「ネットワーク (network)」^[10]^[11]とは、各辺に数値（重み）が割り当てられているグラフ^[12] 。この重みとは、扱う問題次第で例えば料金や距離や所要時間だったりする。こうしたグラフは、例えば巡回セールスマン問題のような最短経路問題など、多くの文脈で作成される。

グラフの種類

Oriented graph

「Oriented graph」の定義の1つは、 $(x, y)$ と $(y, x)$ のうち高々1つがグラフの辺となりうる有向グラフ。すなわち、単純無向グラフに向き付け (orientation) を行うことで形成されうる有向グラフである。

一部の著者は「有向グラフ」と同じ意味で「Oriented graph」を使っている。与えられた無向グラフや多重グラフへの任意の向き付けという意味で「Oriented graph」を使っている著者もいる。

正則グラフ

テンプレート:Main 「正則グラフ (regular graph)」は各頂点がいずれも同じ数の頂点と隣接しているグラフ。すなわち頂点の次数が全て等しいグラフ。次数がテンプレート:Mvar の正則グラフを「テンプレート:Mvar-正則グラフ」または「次数テンプレート:Mvar の正則グラフ」と呼ぶ。

完全グラフ

テンプレート:Main 「完全グラフ (complete graph)」は、どの2頂点間にも1本の辺があるグラフ。完全グラフにはありうる全ての辺が含まれている。

有限グラフ

「有限グラフ (finite graph)」は、頂点集合と辺集合が有限集合のグラフ。それ以外のものは「無限グラフ」と呼ばれる。

グラフ理論ではほとんど一般的に、議論されるグラフは有限グラフであることを暗に前提としている。グラフが無限の場合、通常はそれと明記されている。

連結グラフ

テンプレート:Main 無向グラフでは、頂点テンプレート:Mvar からテンプレート:Mvar まで道がたどれる場合、非順序対 ${x, y}$ が「連結している (connected)」と言う。道が存在しない場合、その非順序対は「非連結」と呼ばれる。

「連結グラフ」は、グラフにある任意の頂点の非順序対が連結している無向グラフである。それ以外の場合は非連結グラフと呼ばれる。

有向グラフでは、テンプレート:Mvar からテンプレート:Mvar まで有向道がたどれる場合に、頂点の順序対 $(x, y)$ が「強連結」であると言う。有向道は存在しないが、有向辺を全て無向辺に置き換えた後ならテンプレート:Mvar からテンプレート:Mvar までの無向道がたどれる場合は「弱連結」であると言う^[13]。それ以外の場合、その順序対は非連結と呼ばれる。

強連結グラフは、グラフにある任意の頂点の順序対が強連結している有向グラフである。それ以外で、グラフにある任意の頂点の順序対が弱連結している場合は、弱連結グラフという。それ以外のものは非連結グラフという。

[[k-頂点連結グラフ| テンプレート:Mvar-頂点連結グラフ]]や[[k-辺連結グラフ|テンプレート:Mvar-辺連結グラフ]]は、取り除いた場合にグラフが非連結となるテンプレート:Math 個の頂点（後者なら辺）集合が存在しないグラフである。テンプレート:Mvar-頂点連結グラフは単に「テンプレート:Mvar-連結グラフ」と言うことも多い。

2部グラフ

テンプレート:Main

「2部グラフ (bipartite graph)」とは、頂点集合を $U$ と $V$ の2集合に分割し、 $U$ 内で任意の2頂点が辺を共有することがなく、 $V$ 内でも任意の2頂点が辺を共有することがないようにできる単純グラフのこと。言い換えるなら、彩色数2となるグラフ。

完全2部グラフにおいて、頂点集合は2つの素集合 $U$ と $V$ の合併 (union) であり、 $U$ 内にある全ての頂点が $V$ 内にある全ての頂点と隣接しているのだが^[14]、素集合の $U$ 内や $V$ 内で完結する辺がないものをいう。

パスグラフ

テンプレート:Main

位数 $n \geq 2$ の「パスグラフ (path graph, linear graph)」とは、頂点の集合を $v_{1}, v_{2}, \dots, v_{n}$ のように順序付けすることで、辺の集合が ${v_{i}, v_{i + 1}}$ （ここで $i = 1, 2, \dots, n - 1$ ）のようになりうるグラフ。一本道のようなダイアグラムとなる。パスグラフは、2頂点を除き全ての頂点の次数が2、残る2頂点の次数が 1という特徴を持つ連結グラフとも言える。他のグラフの部分グラフとしてパスグラフを作った場合、それは元のグラフにおける道（パス）にあたる。

平面的グラフ

テンプレート:Main 「平面的グラフ (planar graph)」とは、辺同士が一切交差することなく平面上に頂点と辺を描くことができるグラフである。

閉路グラフ

テンプレート:Main 位数 $n \geq 3$ の「閉路グラフ (cycle graph)」とは、頂点の集合を $v_{1}, v_{2}, \dots, v_{n}$ のように順序付けすることで、辺の集合が ${v_{i}, v_{i + 1}}$ （ここで $i = 1, 2, \dots, n - 1$ ）に ${v_{n}, v_{1}}$ を付け加えたものとなりうるグラフ。ダイアグラムは閉路状になる。閉路グラフはあらゆる頂点の次数が2の連結グラフという特徴がある。他のグラフの部分グラフとして閉路グラフを作った場合、元のグラフにおける閉路（または回路）にあたる。

木

テンプレート:Main 「木 (tree)」とは、あらゆる頂点の対が厳密に1つの道で連結されている無向グラフ。あるいは連結で閉路のない無向グラフとも言える。

「森 (forest)」とは、あらゆる頂点の対が高々1つの道で連結されている無向グラフ。あるいは（同等の定義だが）閉路がない無向グラフ、または複数の木の交わりを持たない和 (disjoint union)でもある。

有向木

テンプレート:Main 「有向木 (polytree, directed tree, oriented tree, singly connected network)」とは、有向グラフの一種であって、その有向辺をすべて無向辺に置き換えたものが木グラフになるような有向非巡回グラフである。

同様に、「有向森」は、その有向辺をすべて無向辺に置き換えたものが森グラフになるような有向非巡回グラフである。

高度なグラフ

より高度なグラフの種類を幾つか挙げると、以下のものがある。

ピーターセングラフとその一般化
パーフェクトグラフ
補グラフ
弦グラフ
大きなグラフ自己同型群テンプレート:Enlinkを持つその他のグラフ（頂点推移グラフ、弧推移グラフ、距離推移グラフ）
強正則グラフとその一般化である距離正則グラフテンプレート:Enlink

テンプレート:Also

グラフ属性

テンプレート:See also

グラフの2辺が共通の頂点を共有する場合は、2辺が「隣接する (adjacent)」という。有向グラフの2辺は、1番目の終点が2番目の始点になっている場合に「連続する (consecutive)」という。同様に、2頂点が1辺を共有する場合は、2頂点が「隣接」する（有向グラフで、片方の頂点が始点、もう一方が終点ならば「連続」)といい、この場合に共通の1辺が2頂点を「結ぶ (join)」と言う。辺とその頂点とは「接続する (incident)」という。

頂点が1つだけで辺のないグラフは「自明なグラフ (trivial graph)」という。頂点だけからなるグラフは「辺のないグラフ (edgeless graph)」と呼ばれる。頂点も辺もないグラフは「空グラフ (null graph, empty graph)」と呼ばれたりもするが、この用語は一貫しておらず数学者全員がこの対象を容認しているわけではない。

通常、グラフの頂点は集合の元としての性質から互いに識別可能である。この種のグラフは「ラベル付き頂点を持つ (vertex-labeled)」と呼ぶ場合もある。ただし、多くの設問では頂点を識別不能として扱う方が都合が良い（もちろん、頂点はグラフ自体の属性によって、例えば接続辺の数などで、依然として識別できる場合もある）。同じことが辺にも適用されるため、ラベル付けされた辺を持つグラフは「ラベル付き辺を持つ」と呼ばれる。辺または頂点にラベルが与えられているグラフは「ラベル付き」と呼ばれるのが一般的である。したがって、頂点にも辺にも区別がないグラフを「ラベルなし (unlabeled)」と呼ぶ。

全てのグラフの圏はコンマ圏（ $𝐒 𝐞 𝐭 ↓ D$ ）である。ここで $D : 𝐒 𝐞 𝐭 \to 𝐒 𝐞 𝐭$ は、集合 $s$ を $s \times s$ に対応付ける関手である。

用例

右のダイアグラムは次のグラフを模式的に表現したものである。
- 頂点 $V = {1, 2, 3, 4, 5, 6}$
- 辺 $E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}}$
コンピュータサイエンスでは、有向グラフが知識（概念グラフなど）や有限状態機械（状態遷移図）^[15]ほか多くの離散構造を表すのに使われている。
集合 $X$ 上の二項関係 $R$ は有向グラフを定義する。 $X$ の元 $x$ は、 $x R y$ である場合にのみ $X$ の元 $y$ の直前元 (direct predecessor) となる必要十分条件を満たす。
有向グラフは、あるユーザーが別の人をフォローするTwitter等の情報ネットワークを図に表すことができる^[16]^[17]。
とりわけ正則的な有向グラフの例としては、有限生成群のケイリーグラフやシュライアーコセットグラフなどが挙げられる。
圏論では、全ての小さい圏が台有向多重グラフ (underlying directed multigraph) を持っており、そこでの頂点は元の圏の対象、辺は元の圏の矢印である。圏論の言葉では、それを小さい圏の圏から箙の圏への忘却関手テンプレート:Enlinkがある、と表現する。

グラフ操作

テンプレート:Main

初期のグラフから新しいグラフを生成する数学的操作が幾つかあり、次のように分類される場合がある。

「単項演算 (unary operation)」では、1つの初期グラフから以下のような新たグラフを生み出す。
- 辺の縮約テンプレート:Enlink-ある1辺を縮めて両端点を1頂点にする操作
- ライングラフ^[18]
- 双対グラフ
- 補グラフ-頂点集合はそのままで隣接関係を逆にする操作^[19]
- グラフ書換えテンプレート:Enlink
「二項演算 (binary operation)」では、2つの初期グラフから以下のような新たグラフを生み出す。
- グラフ同士の交わりを持たない和
- グラフ同士のデカルト積テンプレート:Enlink
- グラフ同士のテンソル積テンプレート:Enlink
- グラフ同士の強い積テンプレート:Enlink
- グラフ同士の辞書積テンプレート:Enlink
- 直並列グラフテンプレート:Enlink

一般化

ハイパーグラフでは、1つの辺が2つ以上の頂点と接合可能である。

無向グラフは、1次元単体（辺）と 0次元単体（頂点）からなる単体複体と見なすことも可能である。複体はより高次元の単体を容認しうるので、それ自体がグラフの一般化である。

全てのグラフはマトロイドを持ちうる。

モデル理論においてグラフは単なる構造である。しかしその場合、辺の数に制限はなく何らかの基数になりうる（詳細はen:Graphonを参照）。

計算生物学において、パワーグラフ分析は無向グラフの代替表現としてパワーグラフを導入している。

地理情報システム (GIS) では、地理的ネットワークがグラフを基に厳密にモデル構築され、グラフ理論から多くの概念を借用して道路網や電力系統の空間解析を行っている。

脚注

出典

テンプレート:Reflist

参考文献

陳慰・和田幸一『情報工学レクチャーシリーズ離散数学』森北出版、2014年11月7日
加納幹雄『例題と演習で分かる離散数学』森北出版、2013年12月27日
テンプレート:Cite book
テンプレート:Cite book
テンプレート:Cite book
「グラフ理論用語英和対訳表」-英語版wikiの翻訳時に参照した専門用語一覧

外部リンク

テンプレート:MathWorld

テンプレート:Graph Theory-footer

↑ ^1.0 ^1.1 テンプレート:Cite book
↑
See:
- J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Nature, 17 : 284. テンプレート:Doi. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."
- J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, - with three appendices," American Journal of Mathematics, Pure and Applied, 1 (1) : 64-90. テンプレート:Doi. テンプレート:JSTOR. The term "graph" first appears in this paper on page 65.
↑ テンプレート:Cite book
↑ See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
↑ 陳・和田,2014年,p.116
↑ 陳・和田,2014年,pp115-116
↑ Graham et al., p. 5.
↑ 加納,2013年,pp.72-73
↑ 陳・和田,2014年,pp116-117
↑ テンプレート:Citation
↑ テンプレート:Citation
↑ テンプレート:Cite book
↑ 陳・和田,2014年,p.118
↑ 加納,2013年,p.74
↑ 加納,2013年,pp.104-108
↑ テンプレート:Cite journal
↑ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web. テンプレート:Doi.
↑ 白井朋之「The spectrum of the infinitely extended Sierpinski lattice」京都大学数理解析研究所、2-3頁
↑ 加納,2013年,p.75

[:0-1] 1.0 ^1.1 テンプレート:Cite book

[2] See:
J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Nature, 17 : 284. テンプレート:Doi. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."

J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, - with three appendices," American Journal of Mathematics, Pure and Applied, 1 (1) : 64-90. テンプレート:Doi. テンプレート:JSTOR. The term "graph" first appears in this paper on page 65.

[3] J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Nature, 17 : 284. テンプレート:Doi. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."

[4] J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, - with three appendices," American Journal of Mathematics, Pure and Applied, 1 (1) : 64-90. テンプレート:Doi. テンプレート:JSTOR. The term "graph" first appears in this paper on page 65.

[3] テンプレート:Cite book

[4] See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.

[5] 陳・和田,2014年,p.116

[6] 陳・和田,2014年,pp115-116

[7] Graham et al., p. 5.

[8] 加納,2013年,pp.72-73

[9] 陳・和田,2014年,pp116-117

[10] テンプレート:Citation

[11] テンプレート:Citation

[12] テンプレート:Cite book

[13] 陳・和田,2014年,p.118

[14] 加納,2013年,p.74

[15] 加納,2013年,pp.104-108

[snatwitter-16] テンプレート:Cite journal

[twitterwtf-17] Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web. テンプレート:Doi.

[18] 白井朋之「The spectrum of the infinitely extended Sierpinski lattice」京都大学数理解析研究所、2-3頁

[19] 加納,2013年,p.75

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

グラフ (離散数学)

目次

定義