グラフ (離散数学)のソースを表示

{{翻訳直後|1=[[:en:Graph (discrete mathematics)]]14:39, 26 March 2021 |date=2021年3月}}
{{about|[[グラフ理論]]の主題である辺で連結された頂点集合|[[関数 (数学)|関数]]を視覚化するグラフ|グラフ (関数)}}
[[画像:6n-graf.svg|thumb|頂点6つと辺7つから成るグラフの例]]
[[数学]]の[[グラフ理論]]における'''グラフ'''（英: graph）とは[[数学的構造]]の一つ。[[数学的対象|対象]]の[[集合]]で、対象の一部が相互に何らかの脈絡で「関係している」ようなものをいう。ここで対象とは[[頂点 (グラフ理論)|頂点]]（節点やノードとも）と呼ばれる抽象物であり、互いに関係のある頂点の対は辺（枝やエッジとも）と呼ばれる<ref name=":0">{{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=19|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|accessdate=8 August 2012|quote=A graph is an object consisting of two sets called its ''vertex set'' and its ''edge set''.}}</ref>。一般的に、グラフは点または丸で表した頂点の集合に直線または曲線で辺を描き加えた[[ダイアグラム]]で表現される。グラフは[[離散数学]]の研究対象の一つである。

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

グラフはグラフ理論における基本的な研究対象である。「グラフ」という言葉は、1878年に[[ジェームズ・ジョセフ・シルベスター]]によってこの意味で最初に使用された<ref>See:
* J. J. Sylvester (February 7, 1878) [https://books.google.com/books?id=KcoKAAAAYAAJ&vq=Sylvester&pg=PA284#v=onepage&q&f=false "Chemistry and algebra,"] ''Nature'', ''17'' : 284. {{doi|10.1038/017284a0}}. 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) [https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64#v=onepage&q&f=false "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|10.2307/2369436}}. {{JSTOR|2369436}}. The term "graph" first appears in this paper on page 65.</ref><ref>{{Cite book
 | title = Handbook of graph theory
 | first1 = Jonathan L.
 | last1 = Gross
 | first2 = Jay
 | last2 = Yellen
 | publisher = [[CRC Press]]
 | year = 2004
 | page = [https://books.google.com/books?id=mKkIGIea_BkC&pg=PA35&lpg=PA35 35]
 | isbn = 978-1-58488-090-5
 | url = https://books.google.com/books?id=mKkIGIea_BkC
 }}</ref>。

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

=== グラフ===
[[File:Undirected.svg|thumb|頂点3つと辺3つから成るグラフ（無向グラフ）]]
'''グラフ'''（[[有向グラフ]]と区別して「無向グラフ」とか、[[多重グラフ]]と区別して「単純グラフ」とも呼ばれたりもする）{{sfn|Bender|Williamson|2010|p=148}}<ref>See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.</ref>とは[[順序対]] {{math|1=''G'' = (''V'', ''E'')}} である。ここで {{mvar|V}} は頂点 (vertex) と呼ばれる[[元 (数学)|元]]の集合、{{mvar|E}} は頂点の対の集合でありその元は辺 (edge) と呼ばれる。

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

[[File:Multi-pseudograph.svg|thumb|right|多重グラフの例。赤が多重辺で、青がループ]]

頂点をそれ自身と結ぶ辺である「[[ループ (グラフ理論)|ループ]]（自己ループとも）」を許すグラフもある<ref>陳・和田,2014年,p.116</ref>。このように一般化されたグラフは「ループ付きグラフ (graphs with loops)」と呼ばれる。文脈からループを許すことが自明な場合は単にグラフと呼んだりもする。

「[[多重グラフ]]{{enlink|multigraph}}」とは、2つの頂点間に複数の辺がある「多重辺」を許すように一般化したグラフである<ref>陳・和田,2014年,pp115-116</ref>。一部のテキストでは、多重グラフのことを単にグラフと呼んでいたりもする{{sfn|Bender|Williamson|2010|p=149}}<ref>Graham et al., p. 5.</ref>。多重辺を許すにあたり、上述の辺に関する定義を頂点対の（通常の）集合ではなく、頂点対の[[多重集合]]に変更する必要がある。

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

[[空グラフ]]とは、頂点の集合が[[空集合|空]]である（したがって辺の集合も空である）グラフをいう。頂点の数 {{math|{{abs|''V''}}}}をグラフの「[[位数]]」といい、辺の数 {{math|{{abs|''E''}}}}をグラフの「サイズ」という<ref>加納,2013年,pp.72-73</ref>。ただし、アルゴリズムの[[計算複雑性理論|計算複雑性]]を表現するなど一部の文脈では、サイズが {{math|{{abs|''V''}} + {{abs|''E''}}}}である（こうしないと、空ではないグラフのサイズが0となりえてしまう）。頂点の[[次数 (グラフ理論) |次数]]とは頂点に接続する辺の数のことで、ループ付きグラフの場合ループは2回カウントされる<ref name=":0" />。

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

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

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

=== 有向グラフ ===
{{main|有向グラフ|:en:Directed graph}}
[[File:Directed.svg|thumb|頂点3つと有向辺4つから成る有向グラフ（二重矢印は双方向の有向辺2つを表す）]]
'''有向グラフ''' (directed graph, digraph) は、辺に向きがあるグラフである。

限定的だが非常に一般的な意味において{{sfn|Bender|Williamson|2010|p=161}}、有向グラフは以下の条件を満たす対<math>G=(V,E)</math>として定義される。
* <math>V</math> は、頂点の集合
* <math>E \subseteq \{(x,y) \mid (x,y) \in V^2 \;\textrm{ and }\; x \neq y \}</math> は辺の集合で、辺（有向辺とも言う）は頂点の[[順序対]]である。つまり1辺が異なる2頂点と関連している。

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

辺 <math>(x,y)</math> は <math>x</math> から <math>y</math> の向きを表し、頂点 <math>x</math> と<math>y</math> はその辺の「端点」であるが、<math>x</math> は辺の「始点 (tail)」そして <math>y</math> は辺の「終点 (head)」という<ref>陳・和田,2014年,pp116-117</ref>。辺は <math>x</math> と <math>y</math> を「結び」、<math>x</math> と <math>y</math> に「接続する」と表現される。頂点は、グラフ内にあっても辺を持たない場合もある。辺 <math>(y,x)</math> は <math>(x,y)</math> の「逆向辺 (inverted edge)」と呼ばれる。「多重辺」は、上述の定義だと許されないが、同じ始点と終点を持つ辺が複数あるものを言う。

多重辺を許す条件のより一般的な意味で{{sfn|Bender|Williamson|2010|p=161}}、有向グラフは以下によって構成される順序三つ組 <math>G=(V,E,\phi)</math>として定義される。
* <math>V</math> は、頂点の集合
* <math>E</math> は、辺（有向辺とも言う）の集合
* <math>\phi : E \to \{(x,y) \mid (x,y) \in V^2 \;\textrm{ and }\; x \neq y \}</math> は全ての辺を頂点の順序対に写す写像「接続関数 (incidence function)」である。

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

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

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

=== 混合グラフ===
[[File:Example of simple mixed graph.jpg|thumb|upright|140px|混合グラフの例（頂点３つ。有向辺２つ。無向辺１つ。]]
{{main|混合グラフ|:en:Mixed graph}}
「混合グラフ (mixed graph) 」とは、一部の辺が有向、一部の辺が無向であるグラフ。混合単純グラフは順序三つ組 {{nowrap|1=''G'' = (''V'', ''E'', ''A'')}} である。混合複合グラフは {{nowrap|1=''G'' = (''V'', ''E'', ''A'', ''ϕ''<sub>''E''</sub>, ''ϕ''<sub>''A''</sub>)}} の五つ組で、''V'', ''E'' (無向辺), ''A'' (有向辺), ''ϕ''<sub>''E''</sub> ,''ϕ''<sub>''A''</sub> は上述にて定義したものである。有向グラフと無向グラフは混合グラフの特殊なケースである。

[[File:Weighted_network.png|thumb|10の頂点と12の辺からなる重み付きグラフの例。辺に付された数字が重み（距離、所要時間など）を表す。]]

=== 重み付きグラフ===
「重み付きグラフ (weighed graph)」もしくは「ネットワーク (network)」<ref>{{Citation | last=Strang | first=Gilbert | title=Linear Algebra and Its Applications | publisher=Brooks Cole | edition=4th | year=2005 | isbn=978-0-03-010567-8 | url=https://books.google.com/books?vid=ISBN0030105676 }}</ref><ref>{{Citation | last=Lewis | first=John | title=Java Software Structures | publisher=Pearson | edition=4th | year=2013 | isbn=978-0133250121 | page=405 }}</ref>とは、各辺に数値（重み）が割り当てられているグラフ<ref>{{cite book|last1=Fletcher|first1=Peter|last2=Hoyle|first2=Hughes|last3=Patty|first3=C. Wayne|title=Foundations of Discrete Mathematics|year=1991|publisher=PWS-KENT Pub. Co.| location=Boston| isbn=978-0-53492-373-0| pages=463 | edition=International student|quote=A ''weighted graph'' is a graph in which a number ''w(e)'', called its ''weight'', is assigned to each edge ''e''.}}</ref> 。この重みとは、扱う問題次第で例えば料金や距離や所要時間だったりする。こうしたグラフは、例えば[[巡回セールスマン問題]]のような[[最短経路問題]]など、多くの文脈で作成される。

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

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

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

[[File:Complete graph K5.svg|thumb|180px|5つの頂点と10の辺からなる完全グラフの例。各頂点が他全ての頂点に対して辺を有する]]
=== 完全グラフ===
{{main|完全グラフ}}
「完全グラフ (complete graph)」は、どの2頂点間にも1本の辺があるグラフ。完全グラフにはありうる全ての辺が含まれている。

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

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

=== 連結グラフ ===
{{main|連結グラフ}}
無向グラフでは、頂点 {{mvar|x}} から {{mvar|y}} まで[[道 (グラフ理論)|道]]がたどれる場合、非順序対 <math>\{x, y\}</math> が「連結している (connected)」と言う。道が存在しない場合、その非順序対は「非連結」と呼ばれる。

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

有向グラフでは、{{mvar|x}} から {{mvar|y}} まで有向道がたどれる場合に、頂点の順序対<math>(x, y)</math> が「強連結」であると言う。有向道は存在しないが、有向辺を全て無向辺に置き換えた後なら {{mvar|x}} から {{mvar|y}} までの無向道がたどれる場合は「弱連結」であると言う<ref>陳・和田,2014年,p.118</ref>。それ以外の場合、その順序対は非連結と呼ばれる。

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

[[k-頂点連結グラフ| {{mvar|k}}-頂点連結グラフ]]や[[k-辺連結グラフ|{{mvar|k}}-辺連結グラフ]]は、取り除いた場合にグラフが非連結となる {{math|''k''&minus;1}} 個の頂点（後者なら辺）集合が存在しないグラフ
<!--which no set of k-1 vertices (respectively, edges) exists that, when removed, disconnects the graphの直訳だが、「k - 1個の頂点（後者なら辺）を取り除いても連結が保たれるグラフ」くらいに意訳すべきかも？-->
である。{{mvar|k}}-頂点連結グラフは単に「{{mvar|k}}-連結グラフ」と言うことも多い。

[[ファイル:Simple-bipartite-graph.svg|thumb|180px|2部グラフの例]]
=== 2部グラフ ===
{{main|2部グラフ}}
<!--図例に合わせて、''U''と''V''（英語版はWとX）で説明。-->

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

[[完全2部グラフ]]において、頂点集合は2つの[[素集合]] <math>U</math> と<math>V</math> の合併 (union) であり、<math>U</math> 内にある全ての頂点が <math>V</math> 内にある全ての頂点と隣接しているのだが<ref>加納,2013年,p.74</ref>、素集合の <math>U</math> 内や <math>V</math> 内で完結する辺がないものをいう。

=== パスグラフ ===
{{main|:en:Path graph|道 (グラフ理論)}}

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

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

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

[[File:Tree graph.svg|thumb|180px|6つの頂点と5つの辺からなる「木」の例。これと交わりを持たない木が複数あると「森」になる]]
=== 木 ===
{{main|木 (数学)}}
「木 (tree)」とは、あらゆる頂点の対が厳密に1つの道で連結されている無向グラフ。あるいは連結で閉路のない無向グラフとも言える。

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

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

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

=== 高度なグラフ ===
より高度なグラフの種類を幾つか挙げると、以下のものがある。
*[[ピーターセングラフ]]とその一般化
*[[パーフェクトグラフ]]
*[[補グラフ]]
*[[弦グラフ]]
*大きな[[グラフ自己同型|グラフ自己同型群]]{{enlink|Graph automorphism}}を持つその他のグラフ（[[頂点推移グラフ]]、[[対称グラフ|弧推移グラフ]]、[[距離推移グラフ]]）
*[[強正則グラフ]]とその一般化である[[距離正則グラフ]]{{enlink|distance-regular graph}}
{{also|名称のあるグラフのギャラリー}}

== グラフ属性 ==
{{see also|:en:Glossary of graph theory|:en:Graph property}}

グラフの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)」と呼ぶ<!--続く(In the literature, the term labeled may apply to other kinds of labeling, besides that which serves only to distinguish different vertices or edges）は蛇足説明なので割愛-->。

全てのグラフの[[圏 (数学)|圏]]は[[コンマ圏]]（<math> \mathbf{Set} \downarrow D</math>）<!--左の式は原文通りだが正しくないかもしれない-->である。ここで <math>D: \mathbf{Set} \rightarrow \mathbf{Set}</math>は、集合 <math>s</math> を <math>s \times s</math> に対応付ける[[関手]]である。

== 用例 ==
[[File:6n-graf.svg|thumb|6つの頂点と7つの辺からなるグラフ]]
*右のダイアグラムは次のグラフを模式的に表現したものである。
**頂点 <math>V = \{1, 2, 3, 4, 5, 6\}</math> 
**辺 <math>E = \{\{1, 2\}, \{1, 5\}, \{2, 3\}, \{2, 5\}, \{3, 4\}, \{4, 5\}, \{4, 6\}\}</math>
*[[コンピュータサイエンス]]では、有向グラフが知識（[[概念グラフ]]など）や有限状態機械（[[状態遷移図]]）<ref>加納,2013年,pp.104-108</ref>ほか多くの離散構造を表すのに使われている。
*集合 <math>X</math> 上の[[二項関係]] <math>R</math> は有向グラフを定義する。<math>X</math> の元 <math>x</math> は、<math>xRy</math> である場合にのみ <math>X</math> の元 <math>y</math> の直前元 (direct predecessor) となる必要十分条件を満たす。
*有向グラフは、あるユーザーが別の人をフォローする[[Twitter]]等の情報ネットワークを図に表すことができる<ref name="snatwitter">{{Cite journal | volume = 3| issue = 1| last = Grandjean| first = Martin| title = A social network analysis of Twitter: Mapping the digital humanities community| journal =Cogent Arts & Humanities| date = 2016| pages = 1171458| doi=10.1080/23311983.2016.1171458| url = https://serval.unil.ch/resource/serval:BIB_81C2C68B1DF5.P001/REF| doi-access = free}}</ref><ref name="twitterwtf">Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh [http://dl.acm.org/citation.cfm?id=2488433 WTF: The who-to-follow system at Twitter], ''Proceedings of the 22nd international conference on World Wide Web''. {{doi|10.1145/2488388.2488433}}.</ref>。
*とりわけ正則的な有向グラフの例としては、[[群の生成系#有限生成群|有限生成群]]の[[ケイリーグラフ]]や[[シュライアーコセットグラフ]]などが挙げられる。 
*[[圏論]]では、全ての小さい圏が台有向多重グラフ (underlying directed multigraph) を持っており、そこでの頂点は元の圏の対象、辺は元の圏の[[射 (圏論)|矢印]]である。圏論の言葉では、それを[[小さい圏の圏]]から[[箙 (数学)|箙の圏]]への[[忘却関手]]{{enlink|forgetful functor}}がある、と表現する。

== グラフ操作 ==
{{main|:en:Graph operations}}
[[Image:Edge contraction with multiple edges.svg|200px|thumb|right|辺の縮約の例。左側グラフの辺 <math>\{u, v\}</math> を縮めて頂点 <math>W</math> にしたものが右のグラフ]]

初期のグラフから新しいグラフを生成する数学的操作が幾つかあり、次のように分類される場合がある。
* 「[[単項演算]] (unary operation)」では、1つの初期グラフから以下のような新たグラフを生み出す。
** 辺の縮約{{enlink|edge contraction}}-ある1辺を縮めて両端点を1頂点にする操作
** [[ライングラフ]]<ref>白井朋之「[http://www.kurims.kyoto-u.ac.jp/~ito/MPHP/confs/rims01/proc/shirai.pdf The spectrum of the infinitely extended Sierpinski lattice]」[[京都大学]]数理解析研究所、2-3頁</ref>
** [[双対グラフ]]
** [[補グラフ]]-頂点集合はそのままで隣接関係を逆にする操作<ref>加納,2013年,p.75</ref>
** [[グラフ書換え]]{{enlink|graph rewriting}}
* 「[[二項演算]] (binary operation)」では、2つの初期グラフから以下のような新たグラフを生み出す。
** グラフ同士の[[非交和|交わりを持たない和]]
** グラフ同士の[[デカルト積]]{{enlink|cartesian product of graphs}}
** グラフ同士の[[テンソル積]]{{enlink|tensor product of graphs}}
** グラフ同士の強い積{{enlink|strong product of graphs}}
** グラフ同士の[[辞書式順序|辞書]]積{{enlink|lexicographic product of graphs}}
** [[直並列グラフ]]{{enlink|series-parallel graph}}

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

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

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

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

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

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

== 関連項目 ==
*[[グラフ理論]]
*[[グラフ (データ構造)]]
*[[名称のあるグラフのギャラリー]]
*[[ネットワーク理論]]

== 脚注 ==
=== 出典===
{{Reflist|2}}
=== 参考文献 ===
<!--出典で「著者,年,ページ」表記のもの-->
*陳慰・和田幸一『[https://www.morikita.co.jp/data/mkj/081081mkj.pdf 情報工学レクチャーシリーズ 離散数学]』森北出版、2014年11月7日
*加納幹雄『[https://www.morikita.co.jp/data/mkj/006151mkj.pdf　例題と演習で分かる離散数学]』森北出版、2013年12月27日
* {{cite book |last1=Bender |first1=Edward A. |last2=Williamson |first2=S. Gill |date=2010 |title=Lists, Decisions and Graphs. With an Introduction to Probability |url=https://books.google.com/books?id=vaXv_yhefG8C }}
* {{cite book |last1=Graham |first1=R.L. |last2=Grötschel |first2=M. |last3=Lovász |first3=L. |date=1995 |title=Handbook of Combinatorics |publisher=MIT Press |isbn=978-0-262-07169-7 }}
* {{cite book |last1=Iyanaga |first1=Shôkichi |last2=Kawada |first2=Yukiyosi |date=1977 |title=Encyclopedic Dictionary of Mathematics |url=https://archive.org/details/encyclopedicdict0000niho |publisher=MIT Press |isbn=978-0-262-09016-2 |url-access=registration }}
*「[http://x-n.io/doc/graph-theory-terms グラフ理論用語 英和対訳表]」-英語版wikiの翻訳時に参照した専門用語一覧

== 外部リンク==
* {{MathWorld | urlname=Graph | title = Graph}}

{{Graph Theory-footer}}

{{DEFAULTSORT:くらふ (りさんすうかく)}}
[[Category:グラフ理論のグラフ|*]]
[[Category:グラフ理論]]
[[Category:数学に関する記事]]