グラフの基礎 グラフの連結性 オイラーグラフ 無向グラフ、オイラー小道が存在するための必要十分条件、連結、次数、格子、道路、除雪
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第7章(グラフの基礎)、7.2(グラフの連結性)、7.2.4(オイラーグラフ)、問7.10の解答を求めてみる。
グラフ。
次数が奇数である頂点は3個以上あるのでオイラー小道が存在しない。
よって、 各道路（路地）を一度だけ走行して、すべての道路を除雪することは不可能。
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第7章(グラフの基礎)、7.2(グラフの連結性)、7.2.4(オイラーグラフ)、問7.10の解答を求めてみる。
グラフ。
次数が奇数である頂点は3個以上あるのでオイラー小道が存在しない。
よって、 各道路（路地）を一度だけ走行して、すべての道路を除雪することは不可能。