有向グラフ

教科書で学ぶグラフ理論の基礎

定義有向グラフ は、辺に 向き があり、辺を矢印で描くグラフである。

解説矢印は根元の頂点から先の頂点へ向かう関係を表し、逆向きの関係は別の矢印がない限り成り立たない。作業の前後関係、Web ページのリンク、一方通行の道路網などが有向グラフで表される。

たとえ一方通行の標識がある道路網のようなもの。標識の向きにしか進めず、戻るには別の道が要る。

記憶フック「有向」は文字どおり「向きが有る」。矢じりが付いているかどうかを見る。