グラフ（離散数学）

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

エッジは有向でも無向でもかまいません。たとえば、頂点がパーティーの人々を表し、2 人の人々の間には握手するエッジがある場合、このグラフは無向です。なぜなら、人物A が人物Bと握手できるのは、 BもAと握手する場合のみだからです。対照的に、人物Aから人物Bへのエッジが、A がBにお金の借りがあることを意味している場合、このグラフは有向です。なぜなら、お金を借りることは必ずしも相互に借りがあるとは限らないからです。

グラフはグラフ理論が研究する基本的な主題である。「グラフ」という言葉は、数学と化学構造（彼はこれを化学図像と呼んだ）の直接的な関係から、1878年にJJシルベスターによってこの意味で初めて使用された。^{[2] [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 ) です。

グラフの辺は、隣接関係と呼ばれる頂点上の対称関係を定義します。具体的には、{ x , y }が辺である場合、 2 つの頂点xとy は隣接しています。グラフは、隣接行列Aによって完全に決定されます。隣接行列 Aはn × n の正方行列で、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]有向グラフは、以下の要素を含む順序付き3つ組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 \{(x,y)\mid (x,y)\in V^{2}\}}$${\displaystyle \phi }$${\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}\}}$

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

混合グラフは、一部の辺が有向で、一部の辺が無向であるグラフです。混合単純グラフの場合は順序付き 3 つ組G = ( V、E、A )、混合多重グラフの場合はG = ( V、E、A、ϕ _E、ϕ _A )で、V、E (無向辺)、A (有向辺)、ϕ _E、ϕ _{A は}上記のように定義されます。有向グラフと無向グラフは特別なケースです。

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

有向グラフの定義の 1 つは、 ( x , y )と( y , x )のうち最大でも 1 つがグラフのエッジになる有向グラフであるということです。つまり、無向 (単純) グラフの方向として形成できる有向グラフです。

一部の著者は、「有向グラフ」を「有向グラフ」と同じ意味で使用します。一部の著者は、「有向グラフ」を、特定の無向グラフまたはマルチグラフの任意の方向を意味するために使用します。

正則グラフは、各頂点に同じ数の隣接頂点があるグラフ、つまりすべての頂点の次数が等しいグラフです。次数kの頂点を持つ正則グラフは、k正則グラフまたは次数kの正則グラフと呼ばれます。

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

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

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

無向グラフでは、頂点の順序なしペア{ x , y }は、パスがxからyにつながる場合、接続されていると呼ばれます。それ以外の場合、順序なしペアは非接続と呼ばれます。

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

有向グラフでは、頂点の順序付きペア( x、y )は、有向パスがxから y につながる場合、強く接続されていると呼ばれます。それ以外の場合、すべての有向辺を無向辺に置き換えた後に無向パスが x から yにつながる場合、順序付きペアは弱く接続されていると呼ばれます。それ以外の場合、順序付きペアは切断されていると呼ばれます。

強く連結されたグラフは、グラフ内のすべての頂点の順序付きペアが強く連結されている有向グラフです。そうでない場合、グラフ内のすべての頂点の順序付きペアが弱く連結されているときは、弱連結グラフと呼ばれます。そうでない場合は、非連結グラフと呼ばれます。

k頂点連結グラフまたはk 辺連結グラフは、削除してもグラフが切断されるk − 1 個の頂点 (または辺) の集合が存在しないグラフです。k頂点連結グラフは、単にk 連結グラフと呼ばれることもあります。

二部グラフは、頂点集合を2 つの集合WとXに分割でき、 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) です。

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

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

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

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

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

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

すべてのグラフのカテゴリはコンマカテゴリ Set ↓ D です。ここで、D : Set → Set は、集合s をs × 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\}\}.}$
• コンピュータサイエンスでは、有向グラフは知識 (概念グラフなど)、有限状態マシン、その他多くの離散構造を表すために使用されます。
• 集合X上の二項関係 R は有向グラフを定義します。X の要素xがXの要素y の直接の先行要素となるのは、 xRyの場合のみです。
• 有向グラフは、あるユーザーが他のユーザーをフォローしているTwitterなどの情報ネットワークをモデル化することができます。^{[12] [13]}
• 有向グラフの特に典型的な例としては、有限生成群のケーリーグラフやシュライア剰余類グラフが挙げられる。
• 圏論では、すべての小圏は、頂点が圏の対象、辺が圏の矢印である有向多重グラフを基礎に持ちます。圏論の言語では、小圏の圏から箙の圏への忘却関手が存在すると言われます。

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

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

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

無向グラフは、 1単体(辺) と 0 単体 (頂点) で構成される単体複体として考えることができます。複体は、より高次元の単体を許容するため、グラフの一般化です。

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

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

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

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

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

• Balakrishnan, VK (1997).グラフ理論(第 1 版). McGraw-Hill. ISBN 978-0-07-005489-9。
• Bang-Jensen, J.; Gutin, G. (2000)。有向グラフ：理論、アルゴリズム、アプリケーション。Springer。
• Bender, Edward A.; Williamson, S. Gill (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日閲覧。

• ウィキメディア・コモンズのグラフ（離散数学）に関連するメディア
• Weisstein、Eric W.「グラフ」。MathWorld。