مقاله درباره چرخه های همیلتون

لینک دانلود و خرید پایین توضیحات

فرمت فایل word  و قابل ویرایش و پرینت

تعداد صفحات: 7

چرخه های همیلتون

فرض کنید ، G یک گراف متصل با n رأس باشد . دور یا چرخه همیلتون که توسط ویلیام هامیلتون ارائه شد ، مسیری بر روی یال های گراف G است که از هر رأس فقط یکبار عبور می کند و دوباره به رأس شروع برمی گردد . به عبارت دیگر ، یک چرخه همیلتونی از رأسی مانند شروع شده و رئوس را به ترتیب مرور می کند ، با این شرط که یک یال است و همه ها بجزو که یکی هستند ، بقیه متمایزند .

گراف شکل زیر قسمت ( الف ) حاوی مدار هامیلتونی است ولی گراف شکل (ب) حاوی مدار هامیلتونی نیست . مسئله مدارهای هامیلتونی ، مدارهای هامیلتونی را در یک گراف متصل بدون جهت تعیین می کند .

درخت فضای حالت برای این مسئله به شرح زیر است . رأس آغازی در سطح صفر از درخت قرار داده می شود ، آن را رأس صفرم در مسیر می نامیم . در سطح 1 ، همه رئوس غیر از رأس آغازی را به عنوان نخستین رأس پس از رأس آغازی در نظر می گیریم . در سطح 2 ، هر یک از همین رئوس را به عنوان رأس دوم در نظر می گیریم و الی آخر ، سرانجام ، در سطح n-1 اُم هر یک از این رئوس را به عنوان رأس (n-1) اُم در نظر می گیریم.

با در نظر گرفتن ملاحظات زیر می توانیم در این درخت فضای حالت ، عقبگرد کنیم:

رأس i اُم از مسیر باید مجاور به رأس (n-1) اُم از مسیر باشد .

رأس (n-1) اُم باید مجاور رأس صفرم ( رأس آغازی ) باشد .

رأس i اُم نمی تواند یکی از (i-1) رأس باشد .

گراف ( الف ) حاوی مدار هامیلتونی است ؛ گراف (ب) فاقد مقدار هامیلتونی است .

الگوریتیمی که در ادامه خواهد آمد از همین ملاحظات برای عقبگرد استفاده می کند در این الگوریتم رأس به عنوان رإس آغازی در نظر گرفته می شود .

الگوریتم عقبگرد برای مسئله مدارهای هامیلتونی

مسئله : تعیین کلیه مدارهای هامیلتونی در یک گراف متصل و بدون جهت .

ورودی : عدد صحیح و مثبت n و گراف بدون جهت حاوی n رأس . این گراف توسط یک آرایه دو بعدی W نشان داده می شود که سطرها و ستون های آن از یک تا n اندیس گذاری شده اند و در آن در صورتی true است که بین رأس i اُم و رأس jاُم یالی وجود داشته باشد و در غیر اینصورت false است .

خروجی : همه مسیرهایی که از یک رأس مفروض آغاز شده اند ، کلیه رئوس موجود در گراف را دقیقاً یک بار بازدید می کنند و به رأس آغازی ختم می شوند . خروجی هر مسیر ، آرایه ای از اندیسهای vindex است که از صفر تا n-1 اندیس گذاری شده اند و در آن vindex[i] اندیس رأس i اُم روی مسیر است . اندیس رأس آغازی vindex [0] است .

void hamiltonian (index i )

{

index j:

if (promising(i)

if (I==n-1)

cout<< vindex[0] through vindex[n-1]:

else

for (j=2 j<=n:++){

vindex[i +1]=j :

Hamiltonian (i+1) :

}

}

bool promising (index i)

{

index j :

bool switch:

if (I==n-1 &&!W (vindex[n-1] [ vindex[0])

switch=false:

else if (i>0&&!W[vindex[i-1] [vindex [j])

switch=false:

else{

switch=true

j=1:

while(j<&& switch) {

if (vindex [i]==vindex[j]

switch=false: