グラフ (離散数学)

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

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

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

定義

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

グラフ

グラフ（有向グラフと区別して「無向グラフ」とか、多重グラフと区別して「単純グラフ」とも呼ばれたりもする）^[4][5]とは順序対 G = (V, E) である。ここで V は頂点 (vertex) と呼ばれる元の集合、E は頂点の対の集合でありその元は辺 (edge) と呼ばれる。

辺 {x, y} に含まれる頂点 xとy は、その辺の「端点」と呼ばれる。辺は頂点 x と y を「結び (join)」、x や y に「接続する (incident)」と言い表す。頂点がいかなる辺にも含まれないこともあり、その場合は他のどの頂点とも結ばれていない。

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

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

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

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

位数 n のグラフにおける、各頂点の最大次数は n − 1（ループが許される場合は n ）、辺の最大数は n(n − 1)/2（ループが許される場合は n(n + 1)/2）となる。

グラフの辺は「隣接関係」と呼ばれる頂点間の対称関係を定義する。具体的には、{x, y} が辺であれば、2つの頂点 x と y は「隣接している (adjacent)」という。

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

有向グラフ

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

限定的だが非常に一般的な意味において^[11]、有向グラフは以下の条件を満たす対${\displaystyle G=(V,E)}$として定義される。

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

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

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

多重辺を許す条件のより一般的な意味で^[11]、有向グラフは以下によって構成される順序三つ組 ${\displaystyle G=(V,E,\phi )}$として定義される。

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

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

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

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

混合グラフ

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

重み付きグラフ

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

グラフの種類

Oriented graph

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

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

正則グラフ

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

完全グラフ

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

有限グラフ

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

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

連結グラフ

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

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

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

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

k-頂点連結グラフやk-辺連結グラフは、取り除いた場合にグラフが非連結となる k−1 個の頂点（後者なら辺）集合が存在しないグラフ である。k-頂点連結グラフは単に「k-連結グラフ」と言うことも多い。

2部グラフ

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

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

パスグラフ

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

平面的グラフ

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

閉路グラフ

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

木

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

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

有向木

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

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

高度なグラフ

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

• ピーターセングラフとその一般化
• パーフェクトグラフ
• 補グラフ
• 弦グラフ
• 大きなグラフ自己同型群 (Graph automorphism) を持つその他のグラフ（頂点推移グラフ、弧推移グラフ、距離推移グラフ）
• 強正則グラフとその一般化である距離正則グラフ (distance-regular graph) 

グラフ属性

グラフの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)」と呼ぶ。

全てのグラフの圏はコンマ圏（${\displaystyle \mathbf {Set} \downarrow D}$）である。ここで ${\displaystyle D:\mathbf {Set} \rightarrow \mathbf {Set} }$は、集合 ${\displaystyle s}$ を ${\displaystyle s\times s}$ に対応付ける関手である。

用例

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

グラフ操作

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

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

一般化

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

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

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

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

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

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

関連項目

• グラフ理論
• グラフ (データ構造)
• 名称のあるグラフのギャラリー
• ネットワーク理論

脚注

出典

参考文献

• 陳慰・和田幸一『情報工学レクチャーシリーズ 離散数学』森北出版、2014年11月7日
• 加納幹雄『例題と演習で分かる離散数学』森北出版、2013年12月27日
• Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. https://books.google.com/books?id=vaXv_yhefG8C 
• Graham, R.L.; Grötschel, M.; Lovász, L. (1995). Handbook of Combinatorics. MIT Press. ISBN 978-0-262-07169-7 
• Iyanaga, Shôkichi; Kawada, Yukiyosi (1977). Encyclopedic Dictionary of Mathematics. MIT Press. ISBN 978-0-262-09016-2. https://archive.org/details/encyclopedicdict0000niho 
• 「グラフ理論用語 英和対訳表」-英語版wikiの翻訳時に参照した専門用語一覧

外部リンク

• Weisstein, Eric W. "Graph". mathworld.wolfram.com (英語).