テクノロジ
グラフ理論とは
読み方：グラフりろん
ひとことで言うと：頂点と辺で対象間の関係を表し、経路や接続性を扱う数学的理論。
意味をわかりやすく解説
グラフ理論では、対象を頂点、対象間の関係を辺として表します。辺に向きがある有向グラフ、向きがない無向グラフ、距離などの値を持つ重み付きグラフがあります。
経路、連結性、木、最短経路などを統一的に扱えるため、ネットワーク、路線、依存関係など多くの問題をモデル化できます。
具体例
駅を頂点、駅間の路線を辺、所要時間を辺の重みとして表せば、最短経路問題として扱えます。
似た用語との違い
木構造
木は閉路を持たない連結グラフの一種です。グラフは閉路や複数経路を持つ一般的な構造です。
ネットワーク
実際の通信網や道路網を、グラフ理論の頂点と辺で抽象化して分析できます。
覚え方
点＝頂点、線＝辺。向きと重みの有無をまず確認します。
基本情報技術者試験の試験ポイント
有向・無向、重み付き・重みなしの違いを判断し、DFS・BFS・最短経路算法につなげます。
CHECK QUESTION
道路を頂点と辺で表し、辺に所要時間を付けた場合、このグラフは何と呼べますか。
答えを見る
重み付きグラフです。辺に所要時間という重みが付いています。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。