最初にいくつかの定義:
定義 1
グラフ G = (V, E) は、隣接していない頂点 u と v の各ペアについて、d(u) + d(v)>=n (n = |V|) である場合、「密」と呼ばれます。d(*) は頂点の次数を表します *
定義 2
G 上の「ハミルトニアン サイクル」は、すべての l!=h に対して vil != vih であり、{ vil, vil} が G の辺であるような一連の頂点 ( vi1, vi2,....vin, vi1 ) です。 .
問題は次のとおりです: 密な無向グラフ G = (V; E) が入力として与えられたとき、G が G 上のハミルトニアン サイクルを許容するかどうかを判断し、存在する場合はそのサイクルを出力するか、「N」を出力するプログラムを作成します。ない場合。
私の解決策は、ソースから始まるすべての可能なパスを見つけ、このソースに戻るパスが存在するかどうかを確認することです。残念ながら、このソリューションは効率的ではありません。
助言がありますか？ありがとうございました。