グラフ理論

グラフ理論(グラフりろん、 : graph theory)は、ノード節点 [英 1]頂点 [英 2])の集合とエッジ [英 3])の集合で構成されるグラフ [英 4]に関する数学の理論である。 グラフ (データ構造) などの応用がある。

概要

グラフによって、様々なものの関連を表すことができる。

6 つのノードと 7 つのエッジから成るグラフの一例

例えば、 鉄道路線 バス等の 路線図を考える際には、駅(ノード)がどのように路線(エッジ)で結ばれているかが問題となる。 線路が具体的にどのような曲線を描いているかは本質的な問題とならないことが多い。

したがって、 路線図では 間の距離や微妙な配置、路線の形状などがしばしば地理上の実際とは異なって描かれている。 路線図の利用者にとっては、駅と駅の「つながり方」が主に重要な情報なのである。

このように、「つながり方」に着目して抽象化された「点とそれらをむすぶ線」の 概念グラフであり [1]、 グラフがもつ様々な性質を探求するのがグラフ理論である。

つながり方だけではなく「どちらからどちらにつながっているか」をも問題にする場合、 エッジ矢印をつける。このようなグラフを有向グラフ [英 5]または、ダイグラフ [英 6]という。矢印のないグラフは、無向グラフ [英 7]という。

グラフを表現するのに、図ではなく、 隣接行列を用いることがある。無向グラフの隣接行列は、対称行列になる。例えば、上のグラフは、次の隣接行列で表現できる。

グラフの例

日常的な問題や工学的問題の多くをグラフとして考えることができる。

  • 路線図:前節のとおり。
  • 電気回路回路図を書く場合、実際の リード線どおりの形状に図を描いたりはしない。この場合も、「 接点がどうつながっているか」だけが問題であって、「つながり方」を保ちつつできるだけ見やすい形に絵を描く。回路図は一種のグラフである。
  • WWWの構造: WWWにおける ウェブページの、 ハイパーリンク・被リンク関係がなす構造は、有向グラフの一種である [2]
他の言語で
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
中文: 图论
粵語: 圖論