グラフ理論とは？ぐらふりろん
グラフ理論とは、点（節点・ノード）と、それらを結ぶ線（辺・エッジ）でものごとの関係を表して分析する数学分野。向きの有無で有向グラフ・無向グラフに分かれ、コンピュータ上では隣接行列（節点どうしのつながりを0と1の表にしたもの）や隣接リスト（節点ごとにつながる相手を並べた一覧）で表現する。ネットワーク経路や作業の順序関係の分析に応用される。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →具体例
節点数nのグラフを隣接行列で表すとn×nの表になり、節点iからjへ辺があるとき要素を1にする。無向グラフでは対角線を軸に対称な行列になる。辺が少ない疎なグラフでは隣接リストのほうが記憶容量を節約できる。
試験での引っ掛け
隣接行列の記憶量は辺の数に関係なくn²で決まる。「辺が少ないから行列も小さい」は誤り。また無向グラフの辺の総数と次数（1つの節点につながっている辺の数）の関係（次数の合計＝辺の数の2倍）を問う出題にも注意。
関連用語
出典・参考
公式シラバスの1 基礎理論 ＞ 2. 応用数学 ＞ (5) グラフ理論に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。