メッシュ構造において、よいサイクル検出方法がうかびません‥
メッシュから適当に複数辺を選択したとき、サイクルを形成するか調べるプログラムを書こうとしています。具体的には以下です。
メッシュ構造は、4×4や5×5程度を想定しています。
(↓........は無視して見てください。見にくくてすみません)
0---1---2---3
|.........|.........|.........|
4---5---6---7
|.........|.........|.........|
8---9---10--11
|.........|.........|.........|
12--13--14--15
現状では、上記のように点に番号をふり、
辺は(5,9)や(10,14)などで表しています。
(辺に番号を振ることも考えてはいます)
辺が24個ありますが、たとえば
ここから適当に12個の辺を選んだ時に、
それらがサイクル(0-1-5-4-0 や 1-2-3-7-6-5-1 など)を
形成しているか、していないか、判別するプログラムを書こうとしています。
が、うまい判別方法が思い浮かびません…。
あらかじめ、4×4、5×5ごとに全てのサイクルを求めておいて、
サイクル1つ1つについて、選んだ辺⊇サイクルの辺?
を確認するしかないでしょうか?
サイクル数が多そうなので、サイクルを求めるのもサイクルを含むかの確認も時間かかりそうで、やりたくないのですが…。(特に5×5では…)
何かもっと簡単な方法orよさそうな方法ありますでしょうか?
ご意見を、伺いたいです。よろしくおねがいします。
お礼
ありがとうございました。