有向グラフ

有向グラフは、頂点と、向きのある辺で、一方向の関係を表すグラフです。A→Bの辺は、B→Aの辺とは別です。

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

• 頂点に入る辺の数を入次数、出る辺の数を出次数といいます。

• 閉路のない有向グラフ（DAG）は、作業の依存関係を表し、順番に並べられます。

• 隣接行列は、一般に対称になりません。

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

辺の向き、入次数と出次数、到達できる方向が重要です。AからBへ行けても、BからAへ行けるとは限りません。