組合せとグラフの理論(塩田)第4回 (1) グラフの中の道いろいろ
定義
まず、いろいろな種類の道を定義して、そのあとで例を示します。 ※ なお、教科書によって微妙に用語が違うことがありますので、読んでいておかしいときはその本の定義を見直してください。例
これは (1) の記号で $v \rightarrow y \rightarrow x \rightarrow v \rightarrow w$ と書ける歩道です。 同じ辺は通っていませんので小道ですが、中間で $v$ を二度通っているので道ではありません。 | |||
これは道です。 | |||
これは閉じた小道ですが、閉路ではありません。 中間点 $v$ を2度通っています。 | |||
これらは閉路です。 |