グラフ（離散数学）

6つの頂点と7つの辺を持つグラフ

離散数学、特にグラフ理論において、グラフとは、ある意味で「関連」しているオブジェクトの集合からなる構造である。オブジェクトは頂点（ノードまたはポイントとも呼ばれる）と呼ばれる抽象概念によって表され、関連する頂点のペアはそれぞれ辺（リンクまたはラインとも呼ばれる）と呼ばれる。^{[ 1 ]}グラフは典型的には、頂点を表す点または円の集合と、辺を表す直線または曲線で結ばれた図式 で表される。

辺は有向でも無向でも構いません。例えば、頂点がパーティーにいる人々を表し、2人の間に「握手」という辺がある場合、グラフは無向です。なぜなら、AがBと握手できるのは、 BがAとも握手する場合のみだからです。一方、AからBへの辺が「 AがBに借金をしている」という意味である場合、このグラフは有向です。なぜなら、借金は必ずしも相手に返されるわけではないからです。

グラフはグラフ理論が研究する基本的な主題です。「グラフ」という言葉が初めてこの意味で使用されたのは、 1878年にJJシルベスターによってで、数学と化学構造（彼はこれをケミコグラフィカル・イメージと呼びました）の間に直接的な関係があることを示していました。 ^{[ 2 ] [ 3 ]}

定義

グラフ理論における定義は多岐にわたります。以下は、グラフと関連する数学的構造を定義するための、より基本的な方法の一部です。

グラフ

3つの頂点と3つの辺を持つグラフ

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

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

マルチグラフとは、複数の辺が同じ端点のペアを持つことを許す一般化である。文献によっては、マルチグラフは単にグラフと呼ばれることもある。^{[ 6 ] [ 7 ]}

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

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

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

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

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

有向グラフ

3つの頂点と4つの有向辺を持つ有向グラフ。二重矢印は反対方向の2つの有向辺を表す。

有向グラフまたはダイグラフは、エッジに方向があるグラフです。

限定的だが非常に一般的な意味では、^{[ 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 つの定義で定義されている有向グラフは、ループを持つことができません。これは、頂点をそれ自身に接続するループが辺 (有向単純グラフの場合) であるか、 に含まれないに接続する (有向多重グラフの場合) ためです。したがって、ループを許可するには、定義を拡張する必要があります。有向単純グラフの場合、 の定義は に変更する必要があります。有向多重グラフの場合、 の定義はに変更する必要があります。曖昧さを避けるために、これらのタイプのオブジェクトは、それぞれループを許可する有向単純グラフとループを許可する有向多重グラフ(またはquiver )と呼ぶことができます。 ${\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と表記されます。

混合グラフ

3 つの頂点、2 つの有向辺、および 1 つの無向辺を持つ混合グラフ。

混合グラフとは、一部の辺が有向で、一部の辺が無向であるグラフです。混合単純グラフの場合は順序付き三項グラフG = ( V , E , A )、混合多重グラフの場合はG = ( V , E , A , ϕ _E , ϕ _A )となります。混合多重グラフの場合、 V、E（無向辺）、A（有向辺）、ϕ _E、ϕ _Aは上記で定義されています。有向グラフと無向グラフは特別なケースです。

重み付きグラフ

10個の頂点と12個の辺を持つ重み付きグラフ

重み付きグラフまたはネットワーク[ ^{9 ] [ 10 ]は}、各辺に数値（重み）が割り当てられたグラフです。^{[ 11 ]}このような重みは、問題に応じて、例えばコスト、長さ、容量などを表します。このようなグラフは、巡回セールスマン問題などの最短経路問題など、多くの文脈で現れます。

グラフの種類

有向グラフ

有向グラフの定義の一つは、 ( x , y )と( y , x )のうち最大でも一方のみがグラフの辺となり得る有向グラフである、というものです。つまり、無向（単純）グラフの 向きとして形成される有向グラフです。

「有向グラフ」を「有向グラフ」と同じ意味で用いる著者もいます。また、「有向グラフ」を、与えられた無向グラフまたは多重グラフの任意の方向を指すものとして用いる著者もいます。

正規グラフ

正則グラフとは、各頂点の近傍数が等しいグラフ、つまりすべての頂点の次数が等しいグラフです。次数kの頂点を持つ正則グラフは、 k正則グラフまたは次数kの正則グラフと呼ばれます。

完全グラフ

5つの頂点と10の辺を持つ完全グラフ。各頂点は他のすべての頂点と1つの辺を持ちます。

完全グラフとは、各頂点のペアが辺で結ばれているグラフです。完全グラフには、すべての可能な辺が含まれます。

有限グラフ

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

グラフ理論では、議論されるグラフは有限であると一般的に考えられています。グラフが無限である場合は、通常、その旨が明確に述べられます。

接続グラフ

無向グラフにおいて、頂点の順序のないペア{ 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）または循環グラフ（circular graph）とは、頂点がv ₁、v ₂、…、v _{n の}順序で並べられ、辺が{ v _i、v _{i +1} }（ただしi = 1、2、…、n − 1）と辺{ v _n、v ₁ }であるグラフである。サイクルグラフは、すべての頂点の次数が2である連結グラフとして特徴付けることができる。サイクルグラフが別のグラフのサブグラフとして現れる場合、それはそのグラフ内のサイクルまたは回路である。

木

ツリーは、任意の 2 つの頂点が1 つのパスで接続されている無向グラフ、または接続された非巡回無向グラフと同等です。

フォレストは、任意の 2 つの頂点が最大 1 つのパスで接続されている無向グラフ、または同等に非巡回無向グラフ、または同等にツリーの 非結合和集合です。

ポリツリー

ポリツリー(または有向ツリー、指向ツリー、単連結ネットワーク) は、基礎となる無向グラフがツリーである 有向非巡回グラフ(DAG) です。

ポリフォレスト(または有向フォレスト、指向フォレスト) は、基礎となる無向グラフがフォレストである有向非巡回グラフです。

上級クラス

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

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

グラフの特性

グラフ上の2つの頂点が共通の辺を共有する場合、それらの頂点は隣接していると呼ばれます。有向グラフ上の2つの頂点が、最初の頂点の先頭が2番目の頂点の末尾である場合、それらの頂点は連続していると呼ばれます。同様に、2つの頂点が共通の辺を共有する場合、それらの頂点は隣接していると呼ばれます（最初の頂点が末尾で、2番目の頂点が辺の先頭である場合、それらの頂点は連続していると呼ばれます）。この場合、共通の辺は2つの頂点を結んでいると言われます。辺とその辺上の頂点は、接続していると呼ばれます。

頂点が1つだけで辺を持たないグラフは、自明グラフと呼ばれます。頂点のみで辺を持たないグラフは、辺なしグラフと呼ばれます。頂点も辺もないグラフは、ヌルグラフまたは空グラフと呼ばれることもありますが、用語は一貫しておらず、すべての数学者がこの用語を認めているわけではありません。

通常、グラフの頂点は、集合の要素としての性質上、区別可能です。この種のグラフは、頂点ラベル付き と呼ばれることがあります。ただし、多くの問題では、頂点を区別できないものとして扱う方が適切です。(もちろん、頂点は、接続するエッジの数など、グラフ自体の特性によって区別できる場合もあります。) 同じことがエッジにも当てはまるため、ラベル付きエッジを持つグラフは、エッジラベル付きと呼ばれます。エッジまたは頂点にラベルが付いたグラフは、より一般的にはラベル付きと呼ばれます。したがって、頂点が区別できず、エッジも区別できないグラフはラベルなしと呼ばれます。(文献では、ラベル付き という用語は、異なる頂点またはエッジを区別するためだけに機能するラベル以外の種類のラベルにも適用される場合があります。)

ループを許容する有向多重グラフのカテゴリはコンマカテゴリ Set ↓ D です。ここで、D : Set → Set は、集合s をs × sに変換する関数です。

例

6つの頂点と7つの辺を持つグラフ

• この図は、頂点と辺を持つグラフの概略的な表現である。${\displaystyle V=\{1,2,3,4,5,6\}}$ ${\displaystyle E=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}。}$
• コンピュータサイエンスでは、有向グラフは知識 (概念グラフなど)、有限状態マシン、その他多くの離散構造を表すために使用されます。
• 集合X上の二項関係Rは有向グラフを定義します。Xの要素xが Xの要素y の直接の先行要素となるのは、 xRy のときのみです。
• 有向グラフは、Twitterのような、あるユーザーが他のユーザーをフォローしているような情報ネットワークをモデル化することができる。^{[ 12 ] [ 13 ]}
• 有向グラフの特に規則的な例としては、有限生成群のケーリーグラフやシュライア剰余類グラフが挙げられる。
• 圏論において、すべての小圏は、その頂点がその圏の対象、辺がその圏の矢印である有向多重グラフを基礎とします。圏論の言語では、小圏の圏から箙の圏への忘却関手が存在すると言われます。

グラフ操作

初期のグラフから新しいグラフを生成する操作はいくつかあり、次のカテゴリに分類できます。

• 単項演算は、次のような初期グラフから新しいグラフを作成します。
  • エッジ収縮、
  • 折れ線グラフ、
  • 双対グラフ、
  • 補グラフ、
  • グラフ書き換え;
• バイナリ演算では、次のような 2 つの初期グラフから新しいグラフが作成されます。
  • グラフの非結合和、
  • グラフの直積、
  • グラフのテンソル積、
  • グラフの強積、
  • グラフの辞書式積、
  • 直列-並列グラフ。

一般化

ハイパーグラフでは、エッジは任意の正の数の頂点を結合できます。

無向グラフは、 1次元単体（辺）と0次元単体（頂点）からなる単体複体として考えることができます。このように、複体は高次元単体を許容するため、グラフの一般化と言えます。

すべてのグラフはマトロイドを生成します。

モデル理論では、グラフは単なる構造です。しかし、その場合、辺の数に制限はありません。任意の基数を取ることができます（連続グラフを参照）。

計算生物学では、べき乗グラフ解析により、無向グラフの代替表現としてべき乗グラフが導入されます。

地理情報システムでは、ジオメトリ ネットワークはグラフをモデルにしており、道路ネットワークやユーティリティ グリッドの空間分析を実行するためにグラフ理論から多くの概念を借用しています。

参照

• 概念グラフ
• グラフ（抽象データ型）
• グラフデータベース
• グラフ描画
• グラフ理論のトピック一覧
• グラフ理論に関する出版物一覧
• ネットワーク理論

注記

1. Trudeau, Richard J. (1993).グラフ理論入門（訂正・増補再出版）. ニューヨーク: Dover Pub. p. 19. ISBN 978-0-486-67870-2. 2019年5月5日時点のオリジナルよりアーカイブ。2012年8月8日閲覧。グラフとは、頂点集合と辺集合と呼ばれる2つの集合からなるオブジェクトである。
2. 参照:
   • JJシルベスター（1878年2月7日）「化学と代数」、Wayback Machineに2023年2月4日アーカイブNature、17  : 284. doi : 10.1038/017284a0 。284ページより：「したがって、あらゆる不変量と共変量は、ケクレ図またはケミコグラフと全く同一のグラフで表現可能となる。」
   • JJ Sylvester (1878) 「二元量子論の不変量と共変量のグラフ表現への新原子理論の応用について、3つの付録付き」、Wayback Machineに2023年2月4日アーカイブ。American Journal of Mathematics, Pure and Applied、1 (1) : 64–90。doi : 10.2307/2369436。JSTOR 2369436。「グラフ」という用語は、本論文の65ページで初めて登場する。 
3. Gross, Jonathan L.; Yellen, Jay (2004).グラフ理論ハンドブック. CRC Press . p.  35. ISBN 978-1-58488-090-5. 2023年2月4日時点のオリジナルよりアーカイブ。2016年2月16日閲覧。
4. ベンダー＆ウィリアムソン 2010、148ページ。
5. 例えば、彌永と川田、 69 J、p. 4 を参照。 234 またはビッグス、p. 4.
6. ベンダー＆ウィリアムソン 2010、149ページ。
7. グラハムら、5ページ。
8. ベンダー＆ウィリアムソン 2010、p.161。
9. ストラング、ギルバート（2005年）、線形代数とその応用（第4版）、ブルックス・コール、ISBN 978-0-03-010567-8
10. Lewis, John (2013)、Javaソフトウェア構造（第4版）、ピアソン、p.405、ISBN 978-0-13-325012-1
11. フレッチャー, ピーター; ホイル, ヒューズ; パティ, C. ウェイン (1991). 『離散数学の基礎』（国際学生版）ボストン: PWS-KENT Pub. Co. p. 463. ISBN 978-0-53492-373-0重み付きグラフとは、各辺eに重みと呼ばれる数値w ( e )が割り当てられたグラフです。
12. Grandjean, Martin (2016). 「Twitterのソーシャルネットワーク分析：デジタル人文学コミュニティのマッピング」 . Cogent Arts & Humanities . 3 (1) 1171458. doi : 10.1080/23311983.2016.1171458 . 2021年3月2日時点のオリジナルよりアーカイブ。 2019年9月16日閲覧。
13. Pankaj Gupta、Ashish Goel、Jimmy Lin、Aneesh Sharma、Dong Wang、Reza Bosagh Zadeh WTF: Twitter の who-to-follow システムArchived 2019-07-12 at the Wayback Machine、 Proceedings of the 22nd international conference on World Wide Web . doi : 10.1145/2488388.2488433 .

参考文献

• Balakrishnan, VK (1997).グラフ理論（第1版）. McGraw-Hill. ISBN 978-0-07-005489-9。
• Bang-Jensen, J.; Gutin, G. (2000).有向グラフ：理論、アルゴリズム、応用. Springer.
• ベンダー、エドワード・A.；ウィリアムソン、S.ギル（2010年）『リスト、決定、グラフ。確率入門付き』
• ベルジェ、クロード (1958)。Théorie desgraphes et ses application (フランス語)。パリ：デュノー。
• ビッグス、ノーマン（1993年）『代数的グラフ理論』（第2版）ケンブリッジ大学出版局、ISBN 978-0-521-45897-9。
• ボロバス、ベラ (2002)。現代グラフ理論(第 1 版)。スプリンガー。ISBN 978-0-387-98488-9。
• ディーゼル、ラインハルト (2005)。グラフ理論(第 3 版)。ベルリン、ニューヨーク: Springer-Verlag。ISBN 978-3-540-26183-4。
• グラハム、RL。グレッチェル、M.ロヴァシュ、L. (1995)。組合せ論のハンドブック。 MITプレス。ISBN 978-0-262-07169-7。
• グロス、ジョナサン・L.、イエレン、ジェイ（1998年）『グラフ理論とその応用』CRCプレス、ISBN 978-0-8493-3982-0。
• グロス、ジョナサン・L.; イエレン、ジェイ (2003).グラフ理論ハンドブック. CRC. ISBN 978-1-58488-090-5。
• ハラリー、フランク (1995).グラフ理論. アディソン・ウェスリー出版社. ISBN 978-0-201-41033-4。
• 彌永章吉。川田幸義（1977）。数学百科事典。 MITプレス。ISBN 978-0-262-09016-2。
• ダニエル・ツヴィリンガー（2002年）『CRC標準数学表と公式』（第31版）チャップマン＆ホール／CRC. ISBN 978-1-58488-291-6。

さらに読む

• Trudeau, Richard J. (1993). 『グラフ理論入門』（訂正・増補再版）. ニューヨーク: Dover Publications . ISBN 978-0-486-67870-2. 2012年8月8日閲覧。

外部リンク

• ウィキメディア・コモンズのグラフ（離散数学）関連メディア
• ワイスタイン、エリック W. 「グラフ」。MathWorld 。