グラフ（離散数学）

グラフ（有向グラフと区別するために無向グラフ、多重グラフと区別するために単純グラフと呼ばれることもある）^{[ 4 ] [ 5 ]}は、ペアG = ( V , E )であり、Vは要素が頂点（単数形：頂点）と呼ばれる集合であり、Eは順序付けされていないペアの集合である。${\displaystyle \{v_{1},v_{2}\}}$頂点の集合であり、その要素は辺（リンクまたは線とも呼ばれる）と呼ばれる。

空グラフとは、頂点の集合が空であるグラフ（したがって、辺の集合も空であるグラフ）のことです。グラフの次数は、頂点の数| V |であり、通常はnで表されます。グラフのサイズは、辺の数| E |であり、通常はmで表されます。ただし、アルゴリズムの計算複雑性を表す場合など、一部の文脈では、サイズという用語は| V | + | E |の量に使用されます（そうでない場合、空でないグラフのサイズは 0 になる可能性があります）。頂点の次数または価数は、その頂点に接続する辺の数です。ループのあるグラフでは、ループは 2 回カウントされます。

辺{ u , v }の頂点uとvは、辺の端点と呼ばれます。辺はuとvを結び、それらに接していると言われます。頂点はどの辺にも属さないことがあり、その場合は他のどの頂点にも接続されておらず、孤立していると呼ばれます。辺が${\displaystyle \{u,v\}}$頂点uとvが存在する場合、それらは隣接していると呼ばれます。

多重グラフは、複数のエッジが同じエンドポイントのペアを持つことを許容する一般化です。一部のテキストでは、多重グラフは単にグラフと呼ばれています。^{[ 6 ] [ 7 ]}

グラフによっては、頂点同士を結ぶ辺であるループが含まれる場合があります。ループを許容するためには、グラフE内の頂点のペアが同じノードを2回持つことが許されなければなりません。このような一般化されたグラフは、ループを含むグラフ、あるいは文脈からループが許容されていることが明らかな場合は単にグラフと呼ばれます。

一般的に、頂点集合Vは有限であるとみなされます（これは辺集合Eも有限であることを意味します）。無限グラフが考慮される場合もありますが、有限グラフに関するほとんどの結果は無限グラフには適用できないか、あるいは全く異なる証明が必要となるため、通常は特殊な二項関係として扱われます。

次数nのグラフでは、各頂点の最大次数はn − 1 (ループが許容される場合はn + 1、ループは次数に 2 を加えるため) であり、最大辺数はn ( n − 1)/2 (ループが許容される場合はn ( n + 1)/2 ) です。

グラフのエッジは、隣接関係と呼ばれる頂点間の対称的な関係を定義します。具体的には、{ x , y }がエッジである場合、2 つの頂点xとyは隣接しています。グラフは、 n × nの正方行列である隣接行列Aによって完全に決定され、 A _ijは頂点iから頂点jへの接続の数を指定します。単純グラ​​フの場合、A _ijは 0 で接続がないことを示すか、1 で接続があることを示します。さらに、単純グラフのエッジは同じ頂点から始まり同じ頂点で終わることはできないため、 A _ii = 0です。自己ループを持つグラフは、一部またはすべてのA _{ii が}正の整数に等しいことで特徴付けられ、多重グラフ (頂点間に複数のエッジがある) は、一部またはすべてのA _{ij が}正の整数に等しいことで特徴付けられます。無向グラフは、対称的な隣接行列 (つまり、A _ij = A _ji )を持ちます。

有向グラフ（ダイグラフ）とは、辺に方向が設定されているグラフのことである。

限定的ではあるが非常に一般的な意味では、^{[ 8 ]}有向グラフは、以下の要素からなるペアG = ( V , E )である。

• Vは頂点の集合（ノードまたはポイントとも呼ばれる）です。
• E は、異なる頂点の順序付きペアであるエッジの集合（有向エッジ、有向リンク、有向線、矢印、または弧とも呼ばれる）です。${\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}}$。

曖昧さを避けるために、この種のオブジェクトは正確には有向単純グラフと呼ばれるかもしれない。

xからyに向かう辺( x , y )において、頂点xとy は辺の端点、 x は辺の始点、yは辺の始点と呼ばれます。辺はxとyを結び、 xとyに接していると言われます。頂点はグラフ内に存在しても、辺に属していない場合があります。辺( y , x )は( x , y )の反転辺と呼ばれます。上記の定義では認められていない多重辺とは、始点と始点の両方が同じである 2 つ以上の辺のことです。

複数のエッジを許容する、より一般的な意味での有向グラフ^{[ 8 ]}は、次のような順序付き三つ組G = ( V , E , ϕ )として定義されることがある。

• Vは頂点の集合（ノードまたはポイントとも呼ばれる）です。
• Eは、エッジの集合（有向エッジ、有向リンク、有向線、矢印、または弧とも呼ばれる）です。
• ϕ は、すべての辺を頂点の順序付きペアにマッピングする接続関数です（つまり、辺は2つの異なる頂点に関連付けられます）。${\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}}$。

曖昧さを避けるために、この種のオブジェクトは正確には有向多重グラフと呼ばれるかもしれない。

ループとは、頂点とそれ自身を結ぶ辺のことです。上記の2つの定義で定義されている有向グラフにはループは存在しません。なぜなら、頂点とそれ自身を結ぶループは${\displaystyle x}$（有向単純グラフの場合）自身への辺であるか、（有向多重グラフの場合）に接続している。${\displaystyle (x,x)}$それは${\displaystyle \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}}$ループを許可するには、定義を拡張する必要があります。有向単純グラフの場合、定義は${\displaystyle E}$修正する必要がある${\displaystyle E\subseteq V^{2}}$有向多重グラフの場合、定義は${\displaystyle \phi }$修正する必要がある${\displaystyle \phi :E\to V^{2}}$曖昧さを避けるため、これらのタイプのオブジェクトは、それぞれループを許容する有向単純グラフ、およびループを許容する有向多重グラフ（またはクィバー）と正確に呼ばれることがあります。

ループを許容する有向単純グラフGの辺は、Gの頂点上の同次関係~であり、これはGの隣接関係と呼ばれます。具体的には、各辺( x , y )について、その端点xとy は互いに隣接していると言われ、これはx ~ yと表記されます。

混合グラフとは、有向辺と無向辺が混在するグラフのことです。混合単純グラフの場合は順序付き三つ組G = ( V , E , A )、混合多重グラフの場合はG = ( V , E , A , ϕ _E , ϕ _A )で表され、V、E (無向辺)、A (有向辺)、ϕ _Eおよびϕ _Aは上記のように定義されます。有向グラフと無向グラフは、混合グラフの特殊なケースです。

重み付きグラフまたはネットワーク[ ^{9 ] [ 10 ]は}、各エッジに数値（重み）が割り当てられたグラフです。^{[ 11 ]}重みは、対象となる問題に応じて、コスト、長さ、容量などを表す場合があります。このようなグラフは、巡回セールスマン問題などの最短経路問題など、多くの状況で発生します。

有向グラフの定義の一つは、 ( x , y )と( y , x )のうち、最大で一方のみが辺となり得る有向グラフである。つまり、無向（単純）グラフの向き付けによって形成できる有向グラフのことである。

著者によっては、「有向グラフ」を「有向グラフ」と同じ意味で用いる場合がある。また、著者によっては、「有向グラフ」を、与えられた無向グラフまたは多重グラフの任意の向きという意味で用いる場合がある。

正則グラフとは、各頂点が同じ数の隣接頂点を持つグラフ、すなわち、すべての頂点の次数が同じグラフのことです。頂点の次数がkである正則グラフは、 k正則グラフまたは次数kの正則グラフと呼ばれます。

完全グラフとは、すべての頂点のペアが辺で結ばれているグラフのことである。完全グラフには、考えられるすべての辺が含まれている。

有限グラフとは、頂点集合と辺集合が有限集合であるグラフのことである。そうでない場合は、無限グラフと呼ばれる。

グラフ理論においては、議論されるグラフは有限であることが暗黙のうちに前提とされているのが一般的である。グラフが無限である場合は、通常、その旨が明示的に述べられる。

無向グラフにおいて、頂点の順序付けされていないペア{ x , y }は、 xからyへの経路が存在する場合、連結していると呼ばれます。そうでない場合、その順序付けされていないペアは、非連結であると呼ばれます。

連結グラフとは、グラフ内のすべての頂点の順序付けされていないペアが連結している無向グラフのことである。そうでない場合は、非連結グラフと呼ばれる。

有向グラフにおいて、頂点の順序対( x , y )は、 xからyへ有向パスが存在する場合、強連結であると呼ばれます。そうでない場合、すべての有向辺を無向辺に置き換えた後に x から y へ無向パスが存在する場合、その順序対は弱連結であると呼ばれます。そうでない場合、その順序対は非連結であると呼ばれます。

強連結グラフとは、グラフ内のすべての頂点の順序対が強連結である有向グラフのことである。そうでない場合、グラフ内のすべての頂点の順序対が弱連結であれば弱連結グラフと呼ばれ、そうでない場合は非連結グラフと呼ばれる。

k頂点連結グラフまたはk辺連結グラフとは、 k -1個の頂点（または辺）の集合を取り除いてもグラフが分断されないグラフのことである。k頂点連結グラフは、単にk連結グラフと呼ばれることが多い。

二部グラフとは、頂点集合をWとXの2つの集合に分割できる単純グラフであり、 W内のどの2つの頂点も共通の辺を共有せず、 X内のどの2つの頂点も共通の辺を共有しないグラフである。言い換えれば、彩色数が2のグラフである。

完全二部グラフでは、頂点集合は互いに素な2つの集合WとXの和集合であり、 Wのすべての頂点はXのすべての頂点に隣接していますが、 WまたはX内には辺はありません。

次数n ≥ 2のパスグラフまたは線形グラフとは、頂点をv ₁ , v ₂ , …, v _nの順に並べることができ、辺が{ v _i , v _{i +1} } ( i = 1, 2, …, n − 1) であるグラフのことです。パスグラフは、2 つの頂点を除くすべての頂点の次数が 2 であり、残りの 2 つの頂点の次数が 1 である連結グラフとして特徴付けられます。パスグラフが別のグラフの部分グラフとして出現する場合、それはそのグラフにおけるパスです。

平面グラフとは、頂点と辺を平面上に描画することができ、かつどの2つの辺も交差しないグラフのことである。

次数n ≥ 3のサイクルグラフまたは円グラフとは、頂点をv ₁、v ₂、 …、v _nの順に並べることができ、辺が{ v _i、v _{i +1} } ( i = 1, 2, …, n − 1) と辺{ v _n、v ₁ }で構成されるグラフのことです。サイクルグラフは、すべての頂点の次数が 2 である連結グラフとして特徴付けられます。サイクルグラフが別のグラフの部分グラフとして現れる場合、それはそのグラフにおけるサイクルまたは回路です。

木とは、任意の2つの頂点がちょうど1つの経路で接続されている無向グラフ、または同等に連結された非巡回無向グラフのことである。

森とは、任意の2つの頂点が最大で1つの経路で接続されている無向グラフ、あるいは同等に非巡回無向グラフ、あるいは同等に木の非連結和集合である。

ポリツリー（または有向木、方向付き木、単連結ネットワーク）は、基となる無向グラフが木である有向非巡回グラフ（DAG）です。

ポリフォレスト（または有向フォレスト、方向付きフォレスト）とは、基となる無向グラフがフォレストである有向非巡回グラフのことである。

より高度なグラフの種類は以下のとおりです。

• ピーターセングラフとその一般化。
• 完璧なグラフ;
• 共グラフ;
• 弦グラフ;
• 大きな自己同型群を持つその他のグラフ：頂点推移グラフ、弧推移グラフ、距離推移グラフ。
• 強正則グラフとその一般化である距離正則グラフ。