グラフ理論（ぐらふりろん）
最終更新：2026/4/19
グラフ理論は、点と線で表されるグラフを用いて、それらの関係性を数学的に研究する分野である。
別名・同義語 ネットワーク理論図論
ポイント
コンピュータ科学、情報科学、オペレーションズ・リサーチなど、様々な分野に応用される数学の一分野である。ネットワークの分析や最適化に役立つ。
概要
グラフ理論は、離散数学の一分野であり、グラフと呼ばれる数学的構造を扱う。グラフは、頂点（ノード）と辺（エッジ）から構成され、頂点間の関係性を表現する。この理論は、ネットワーク構造の分析、アルゴリズムの設計、最適化問題の解決など、幅広い分野で応用されている。
歴史
グラフ理論の起源は、18世紀に遡る。オイラーによるケーニヒスベルクの橋の問題の解決が、グラフ理論の始まりとされる。この問題は、都市の橋をすべて一度ずつ通って出発点に戻る経路が存在するかどうかを問うもので、グラフを用いて解決された。その後、19世紀後半から20世紀にかけて、ラームゼー理論、グラフ彩色、ネットワークフローなどの研究が進展した。
基本概念
- 頂点 (Vertex): グラフを構成する基本的な要素。オブジェクトやエンティティを表す。
- 辺 (Edge): 頂点間の関係を表す線分。有向グラフの場合は、方向性を持つ。
- グラフ (Graph): 頂点と辺の集合。
- 次数 (Degree): ある頂点に接続されている辺の数。
- パス (Path): 頂点と辺をたどる経路。
- サイクル (Cycle): 開始点と終了点が同じパス。