一筆書きで書けるか判定したい

一筆書きである線の経路をなぞれるかどうかを判定したいときに使える方法について紹介します.一筆書きできる経路のことをオイラー路といい、辺をたどったら始点に戻るものを特にオイラー閉路と言う.

この章を学ぶ前に必要な知識

条件

効果

ポイント

一筆書きで書けるか判定する方法についてまとめます. といっても判定方法自体は、とてもシンプルです. 一筆書きができる経路のことをオイラー路と言って、始めりの頂点と終わりの頂点が同じものをオイラー閉路といいます.	一筆書きで書けるか判定したい
一筆書きが可能かどうか判定する基準を以下に書きました. どちらかが満たされていれば一筆書き可能です. ・全ての頂点につながっている辺(エッジ)の数が偶数. ・二つの頂点だけが奇数本の辺がつながっていてになっていて、他は全て偶数.	一筆書きか判定する
	頂点と辺からなるグラフ.それぞれの数字はつながっている辺の数上のルールに従えば、図の絵は奇数が２点だけで、それ以外は偶数となっているので一筆書き可能. 実際に簡単に見つけられると思う.
奇数本の頂点がある場合は必ずそれらの頂点の片方から初めて、終わるときももう片方の頂点にたどり着く必要がある. 一筆書きができるということは、全ての点は通過することになります. 通過するためには常にその頂点に入る道と出る道の二つがなくてはなりません.そのため偶数の辺を持つことが必要になります.	判定方法補足

この章を学んで新たに学べる

Comments