لینک دانلود و خرید پایین توضیحات
فرمت فایل 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:
مقاله درباره چرخه های همیلتون