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