グラフ理論とは？
グラフ理論とは、対象を頂点、そのつながりを辺として抽象化して扱う数学。辺に向きのある有向グラフ、重みを持つ重み付きグラフなどがあり、通信経路、作業の順序関係、状態遷移の表現に使う。実装上は隣接行列か隣接リストで表し、辺が少ない場合は後者が有利。
ぐらふりろん
グラフ理論の意味
対象を頂点、そのつながりを辺として抽象化して扱う数学。辺に向きのある有向グラフ、重みを持つ重み付きグラフなどがあり、通信経路、作業の順序関係、状態遷移の表現に使う。実装上は隣接行列か隣接リストで表し、辺が少ない場合は後者が有利。
グラフ理論の具体例
通信網を重み付きグラフとみなし、最短経路や最小全域木を求めて回線設計に生かす。作業の先行関係を有向で閉路の無いグラフとして表せばアローダイアグラムになり、閉路があれば順序に矛盾があると機械的に分かる。
グラフ理論は試験でどう引っ掛けられる？
頂点数nの無向グラフの辺数の上限はn(n−1)/2、有向ではn(n−1)とちょうど2倍になる。隣接行列は辺の数によらず頂点数の2乗のメモリを使うため、疎なグラフでは無駄が大きいという比較が出る。
グラフ理論と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。