グラフ_(離散数学)

ウィキペディア

グラフ (離散数学)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/10/31 09:45 UTC 版)

この項目「グラフ (離散数学)」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en:Graph (discrete mathematics)14:39, 26 March 2021） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2021年3月）

この項目では、グラフ理論の主題である辺で連結された頂点集合について説明しています。関数を視覚化するグラフについては「グラフ (関数)」をご覧ください。

頂点6つと辺7つから成るグラフの例

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

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

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

定義

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

グラフ

頂点3つと辺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}$

頂点3つと有向辺4つから成る有向グラフ（二重矢印は双方向の有向辺2つを表す）

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

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

混合グラフの例（頂点３つ。有向辺２つ。無向辺１つ。

詳細は「混合グラフ」および「:en:Mixed graph」を参照

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

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

重み付きグラフ

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

グラフの種類

Oriented graph

「Oriented graph」の定義の1つは、${\displaystyle (x,y)}$

5つの頂点と10の辺からなる完全グラフの例。各頂点が他全ての頂点に対して辺を有する

完全グラフ

詳細は「完全グラフ」を参照

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

有限グラフ

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

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

連結グラフ

詳細は「連結グラフ」を参照

無向グラフでは、頂点 x から y まで道がたどれる場合、非順序対 ${\displaystyle \{x,y\}}$

2部グラフの例

2部グラフ

詳細は「2部グラフ」を参照

「2部グラフ (bipartite graph)」とは、頂点集合を ${\displaystyle U}$

6つの頂点と5つの辺からなる「木」の例。これと交わりを持たない木が複数あると「森」になる

木

詳細は「木 (数学)」を参照

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

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

有向木

詳細は「:en:Polytree」を参照

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

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

高度なグラフ

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

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

「名称のあるグラフのギャラリー」も参照

グラフ属性

「: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)」と呼ぶ。

全てのグラフの圏はコンマ圏（${\displaystyle \mathbf {Set} \downarrow D}$

6つの頂点と7つの辺からなるグラフ

• 右のダイアグラムは次のグラフを模式的に表現したものである。
  • 頂点 ${\displaystyle V=\{1,2,3,4,5,6\}}$
    辺の縮約の例。左側グラフの辺 ${\displaystyle \{u,v\}}$ カテゴリ / コモンズ