有向グラフ

有向グラフは、頂点集合Vと、始点から終点への向きを持つ有向辺の集合Eで非対称な関係を表すグラフです。辺$(u,v)$は$u\to v$を意味し、逆向き$v\to u$とは別の辺です。

■ 試験で押さえるポイント

• 頂点へ入る辺数を入次数、頂点から出る辺数を出次数とし、全頂点の入次数の和と出次数の和はいずれも|E|です。

• uから辺の向きに沿ってvへ到達できても、vからuへ到達できるとは限りません。互いに到達可能な最大集合を強連結成分と呼びます。

• 閉路を持たない有向グラフDAGは、依存関係や作業順序を表し、トポロジカルソートできます。閉路があると全頂点の線形な依存順序は作れません。

• 隣接行列Aでは$A_{ij}$が$i\to j$の辺を表し、一般に対称ではありません。Webリンク、一方通行、呼出し関係などに用います。

■ 選択肢での判断ポイント

辺の順序、入次数・出次数、到達方向、DAGとトポロジカル順序が重要です。片方向の辺を自動的に双方向として扱いません。

例: $A\to B$、$A\to C$、$C\to A$なら、Aの出次数2・入次数1、Bの入次数1・出次数0です。AからBへ行けてもBからAへは到達できません。