読み方：グラフりろん

グラフ理論【graph theory】

概要

グラフ理論とは、点（ノード・頂点）と、点をつなぐ線（エッジ・辺）で構成される構造を数学的に研究する学問分野。ネットワークや関係性を持つあらゆる問題のモデル化と解析に用いられる。

グラフ理論の起源は1736年、スイスの数学者レオンハルト・オイラーが「ケーニヒスベルクの橋の問題」（一筆書き問題）を解いたことに遡る。当時のプロイセン、ケーニヒスベルク（現在はロシアの飛び地、カリーニングラード）には七つの橋があり、「すべての橋をちょうど一度ずつ渡って元の場所に戻れるか」という問いに対し、オイラーは島と橋の関係をノードとエッジで抽象化した「グラフ」の構造を分析して不可能であることを証明した。これがグラフ理論の出発点とされている。

グラフにはいくつかの基本的な種類がある。エッジに向き（方向）がない「無向グラフ」、エッジが方向を持つ「有向グラフ」、エッジに何らかの重み（距離やコストなど）を付与した「重み付きグラフ」などである。また、閉じた経路（サイクル）を持たない有向グラフは「有向非巡回グラフ」（DAG）と呼ばれ、タスクの依存関係や処理順序の管理に広く使われる。

グラフ理論は様々なアルゴリズムの基礎となっている。二点間の最短経路を求める「ダイクストラ法」や「ベルマン・フォード法」、グラフ全体を効率よく探索する「深さ優先探索」（DFS）と「幅優先探索」（BFS）、ネットワークの最大流量を求める最大フロー問題の様々な解法などがよく知られる。これらはカーナビゲーションシステムの経路案内、物流の最適化、通信ネットワーク設計、スケジューリングといった実問題に直接的に応用されている。

Webページ間のリンク構造、SNSのフォロー関係、タンパク質の相互作用ネットワークなど、現実世界の複雑な関係性はグラフとして自然に表現できる場合が多い。米グーグル（Google）社の検索順位付けに用いられるPageRankアルゴリズムもグラフ理論を応用したものであり、ノードとエッジという単純な概念が現代のITインフラを支える理論的な土台となっている。