گراف همیلتنی

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 17 خرداد 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 24 مرتبه

تعریف گراف همیلتنی

در یک گراف، مسیری که شامل همه راس‌های گراف باشد، مسیر همیلتنی نام دارد.

در یک گراف، به دوری که شامل همه راس‌های گراف باشد، دور همیلتنی می‌گویند.

گرافی که شامل دور همیلتنی باشد، گراف همیلتنی نامیده می‌شود.

بنابراین:

اگر G یک گراف از مرتبه p3 باشد و دارای دوری به طول p باشد، یعنی دارای دوری باشد که هر راس را درست یک بار شامل شود آن را گراف همیلتنی گوییم.

به‌عنوان نمونه، گراف‌های زیر همیلتنی هستند:

گراف همیلتنی - پیمان گردلو

دریافت مثال

تمرین

گراف زیر را در نظر بگیرید:

گراف همیلتنی - پیمان گردلو

آیا گراف فوق همیلتونی است؟

گراف فوق همیلتنی است زیرا از مرتبه 6 بوده و دارای دوری به طول 6 به‌صورت زیر باشد:

a,b,c,d,e,f,a

قضایا گراف همیلتنی

قضیه

هر گراف کامل kp با شرط p3 همیلتنی است.

اثبات

یادآوری می‌کنیم که:

گراف ساده G=(V,E) را کامل گویند، اگر هر راس آن با تمام راس‌های دیگر متصل باشد، در واقع هر دو راس این گراف با یک یال به‌هم متصل می‌باشد.

گراف کامل با p راس را به‌صورت kp نمایش می‌دهند.

در گراف kn که n3 و چون همه راس‌ها توسط یالی به‌هم متصل‌اند، پس دنباله زیر یک دور به طول p در گراف kp است، پس گراف kp با شرط p3 همیلتنی است.     

a1a2....ap1apa1

توجه شود که گراف‌های کامل k2,k1,k0 دور ندارند، بنابراین همیلتنی نیستند.

دریافت مثال

قضیه

گراف کامل kp به‌طوری‌که p عددی فرد و از مرتبه p3 باشد، دارای دور همیلتنی مختلف به تعداد زیر است: 

12(p1)!

اثبات

دور هامیلتونی دارای p یال می‌باشد، پس به تعداد زیر دور هامیلتونی داریم که یال مشترکی ندارند:

1pp2=p12

در ضمن برای تعداد دورهای هامیلتونی متفاوت، که ممکن است یال مشترکی هم داشته باشند، در اولین انتخاب p حالت در دومین انتخاب p-1 حالت و همین طور الی آخر، پس از آنجا که هر دور هامیلتونی دارای یال است، داریم:

12p!p=12(p1)!

دریافت مثال

قضیه

هر گراف همیلتنی، همبند است.

اثبات

یادآوری می‌کنیم که:

گراف همبند گرافی است که بین هر دو راس آن لااقل یک مسیر وجود داشته باشد، در غیر این‌صورت گراف ناهمبند است.

می‌دانیم گراف همیلتنی شامل یک دور همیلتنی می‌باشد، یعنی دوری که از همه راس‌های گراف می‌گذرد پس درجه هر راس نمی‌تواند برابر صفر باشد و هر راس با راس‌های دیگر در ارتباط است (به‌عبارت دیگر از هر راس دیگر مسیری وجود دارد) لذا گراف همیلتنی، همبند است.

دریافت مثال

قضیه

در یک گراف همیلتنی درجه تمام راس‌ها بزرگ‌تر یا مساوی 2 است.

اثبات

فرض کنید در یک گراف همیلتنی درجه راسی کوچک‌تر از 2 باشد، در این‌صورت درجه آن صفر یا یک است.

صفر نمی‌تواند باشد زیرا هر گراف همیلتنی، همبند است و راس از درجه صفر در دور وارد نمی‌شود.

اگر درجه این راس یک باشد، زمانی که در دور همیلتنی به آن می‌رسیم به‌علت این‌که راس مجاور دیگری ندارد، از آن نمی‌توان عبور کرد و چون گراف همیلتنی است، چنین فرضی امکان ندارد، لذا درجه تمام راس‌ها در یک گراف همیلتنی بزرگ‌تر یا مساوی 2 است.

دریافت مثال

قضیه

اگر G یک گراف ساده از مرتبه p با مینیمم درجه δ باشد، درصورتی‌که p3 و δp2 آن‌گاه گراف G همیلتنی است. 

دریافت مثال

قضیه

اگر G یک گراف ساده با p3 راس باشد و برای هر دو راس غیرمجاور u و w (رئوسی که به‌هم متصل نیستند) از G داشته باشیم:     

deg(u)+deg(w)p

آن‌گاه G همیلتنی است.

اگر G یک گراف ساده با p راس باشد و به‌ازای هر دو راس غیرمجاور u و w از آن:   

deg(u)+deg(w)p-1

آن‌گاه G دارای یک مسیر همیلتنی است.

نکته

1- یک دور اویلری از هر یال دقیقا یک‌بار استفاده می‌کند، اما ممکن است راس‌های تکراری داشته باشد به همین خاطر می‌تواند یک دور همیلتنی نباشد.

یک دور همیلتنی از هر راس دقیقا یک بار استفاده می‌کند و لازم نیست که شامل همه یال‌های G باشد در نتیجه می‌تواند یک دور اویلری نباشد.

گراف همیلتنی - پیمان گردلو


2- درجه هر راس kp برابر p-1 است و هر kp با شرط k3  همیلتنی است و گرافی همبند.  

3- برای گراف همیلتنی مرتبه p:

qman=p(p-1)2=p2qmin=p


4- با وجود شباهت ظاهری در تعاریف دور اویلری و همیلتنی، ریاضیات مربوط به آنها با هم خیلی تفاوت دارد. 

اگر گراف G یک دور همیلتنی داشته باشد، آن‌گاه G یک زیر گراف H با خواص زیر است:

H شامل هر راس G است.     

H همبند است.

تعداد یال‌های H برابر تعداد راس‌های آن است.

هر راس H از درجه 2 است. 


5- دور همیلتنی ممکن است از بعضی از یال‌ها عبور نکند.

مثلا دور a,b,c,d,a در گراف زیر از یال ac عبور نکرده است.

گراف همیلتنی - پیمان گردلو


6- اگر گراف G همیلتنی باشد باید با حذف هر یالی کماکان همبند باقی بماند زیرا هر گراف همیلتنی، همبند است. 

7- اگر گرافی با برداشتن یک یال ناهمبند شود، همیلتنی نمی‌باشد.

مثال‌ها و جواب‌ها

گراف همیلتنی

5,000تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید