| 1 |
|
|
左の左は一筆描き閉路です。線幅は３ピクセルである。その右はその輪郭線である。
輪郭線は番号が付けられサイクルになっている。
この輪郭サイクルはどこも２重になっている。
もし元の描画閉路の幅が限りなく狭ければ、これらの２重のサイクルは重なると考えられる。
元々の閉路は線の交点をグラフの頂点とすると全ての頂点の辺の数は偶数であるので、
それはオイラーグラフであります。
したがって、２重のサイクルセットには２重のオイラーグラフがあると考えられます。
この２重のオイラーグラフは同じ頂点と辺により構成された二つのサイクルセットになります。
しかし、これからできるオイラーサーキットは道筋が違い別のオイラーサーキットになります。
一筆描き閉路に関して
サイクルで囲まれた領域を頂点、サイクルの隣接を辺とするグラフは２分グラフであるので、
２重サイクルのグラフはサイクルの隣接を基準にサイクルを分けることができると考えられます。
即ちそれは２分グラフのXとYのパーティションになる。
|
| 2 |
|
|
上記のパーティションがこの二つのサイクルセットです。
|
| 3 |
|
|
左は全ての隣接をチェックして、２分グラフを描いたものです。
右はサイクルを頂点とする領域とサイクルの隣接を辺とするグラフ（２分グラフ）描いたものです。
|
| 4 |
|
|
左の左は線幅１ピクセルで描いた閉路です 。
左の右はその輪郭線です。どこも２重になっていますが、ほとんどの場所で重なっているため、１重に見えます。
|
| 5 |
|
|
前記の３ピクセルの描画閉路の場合と同じように処理して、２分グラフに分けたものです。
両画像とも同じように見えます。
しかし、二つは違ったサイクルセットになっています。
左は５つのサイクルにより構成され、右は3つのサイクルにより構成されています。
ここで明らかなように、閉じた描画閉路の輪郭線は実質的に２重のオイラーサーキットであるといえます。
|
| 6 |
|
|
前記のサイクルセット（XもYも）をマージして一つのサイクルに変換し、
適当な位置でパスを切り、スタートとゴールとし、
ランダムな袋小路を追加、壁を細く道を太くすると迷路が完成する。
完成した迷路に正解のパスを追加すると図のようになる。
XパートもYパートも同じように見えるが道筋は違う。
|
| 7 |
詳しくは以下のの論文を参照ください。
Tomio Kurokawa, "Maze Construction by Using Characteristics of Eulerian Graphs,"
British Journal of Mathematics & Computer Science, Vol.9, Issue.6, pp.453-472, 2015.6,
SCIENCEDOMAIN international, UK, ISSN: 2231-0851, http://sciencedomain.org/issue/1147
論文のダウンロード-DOI:https://doi.org/10.9734/BJMCS/2015/18125
|
