グラフ理論

頂点（ノード）と辺（エッジ）からなるグラフ構造を扱う数学分野。無向グラフ、有向グラフ、重みつきグラフ、完全グラフなどの種類があり、ネットワーク設計、最短経路問題、スケジューリングなどに応用される。

頂点（ノード）と、頂点どうしを結ぶ辺（エッジ）からなるグラフの性質を研究する数学の分野。向きのある有向グラフ、向きのない無向グラフ、辺に重みを持つ重み付きグラフがあり、最短経路や最小全域木、ネットワークの経路制御、SNSの関係の分析などに応用される。

頂点（ノード）と、頂点どうしを結ぶ辺（エッジ）で、ものどうしのつながりを表すデータ構造。辺に向きのある有向グラフと向きのない無向グラフがあり、プログラムでは隣接行列や隣接リストで表現する。路線網の最短経路探索や、ネットワークの構造の表現に使う。

辺（エッジ）に方向がないグラフ。頂点（ノード）間の接続関係を表現し、辺は双方向の関係を示す。ネットワークのトポロジや社会的関係の表現に使われる。

辺（エッジ）に方向があるグラフ。頂点間の一方向の関係を表現する。Webページのリンク構造やワークフローの依存関係など、方向性のある関係の表現に適する。

重み付きグラフにおいて、始点から全ての頂点への最短経路を求めるアルゴリズム。辺の重みが非負の場合に使用でき、貪欲法に基づく。計算量はO(V²)だが、優先度付きキューを使うとO((V+E)log V)に改善できる。

グラフ上の2点間で、辺の重みの合計が最小になる経路を求める処理。カーナビの経路案内やネットワークのルーティングに使われる。代表的な解法にダイクストラ法やベルマンフォード法がある。

最短経路を求めるアルゴリズムの一つ。すべての辺について距離の更新を繰り返す。ダイクストラ法より遅いが、重みが負の辺を含むグラフでも扱え、負の閉路があることも検出できる。