グラフ理論とは？ぐらふりろん
グラフ理論とは、頂点と辺という二つの要素だけで対象の関係構造を表す数学。辺に向きを持たせれば作業の先行関係や資源の待ち関係を、重みを持たせれば経路の距離や遅延を、同じ枠組みで扱える。計算機上では隣接行列と隣接リストのどちらで保持するかが、メモリ量と探索の速さのトレードオフになる。
最終更新：2026-10-06
エンベデッドSPを最短で暗記・合格する →背景
対象が違っても「何と何がつながっているか」だけが問題になる場面は多く、共通の形式へ落とせば同じアルゴリズムを使い回せる。最短経路・閉路検出・全域木といった道具が分野をまたいで効くのはこのためである。組込みでは状態遷移の設計もデッドロックの検出も同じ閉路の話に帰着するので、この抽象の効く場面が広い。
具体例
資源の割当てを、タスクを頂点・待ち関係を有向辺としたグラフで表すと、閉路の存在がそのままデッドロックの成立条件になる。作業の先行関係を閉路の無い有向グラフで表せばアローダイアグラムになる。頂点数nの隣接行列はn²のメモリを固定で使うので、RAMの限られた機器では隣接リストを選ぶ。
試験での引っ掛け
頂点数nの無向グラフの辺数の上限はn(n−1)/2、有向ではn(n−1)でちょうど2倍になる。隣接行列は辺の数によらず頂点数の2乗のメモリを使うため疎なグラフでは無駄が大きいが、辺の有無を定数時間で引ける利点があり、どちらが常に優れるわけではない。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。