Borna66
01-11-2011, 08:10 PM
در تئوری گراف ها یک مسیر همیلتونی در یک گراف بدون جهت یک مسیر است که از هر راس (http://fa.wikipedia.org/w/index.php?title=%D8%B1%D8%A7%D8%B3&action=edit&redlink=1) فقط یک بار گذشته باشد.و یک دور همیلتونی در یک گراف ساده بدون جهت یک دور است که از هر راس فقط یک بار عبور می‌کند و به راس اول باز می‌گردد و محاسبه این که یک گراف دارای مسیر یا دور همیلتونی است از مسائل NP-complete است.مسیر و دور همیلتونی بعد از William Rowan Hamilton کسی که بازی Icosiam را اختراع کرد نامگذاری شد و البته امروزه با نام پازل همیلتون هم شناخته می‌شود و شامل پیدا کردن یک دور همیلتونی در یک دوازده وجهی بود که همیلتون این مسئله را حل کرد ولی متاسفانه روش او برای تمام گراف ها تعمیم نمی‌یابد. http://pnu-club.com/imported/2011/01/13.png (http://fa.wikipedia.org/wiki/%D9%BE%D8%B1%D9%88%D9%86%D8%AF%D9%87:Hamiltonian_p ath.svg) http://pnu-club.com/imported/2011/01/12.gif (http://fa.wikipedia.org/wiki/%D9%BE%D8%B1%D9%88%D9%86%D8%AF%D9%87:Hamilton_path .gif)
تعریف
یک مسیر همیلتونی یا یک مسیر قابل ردیابی یک مسیر است که از هر راس فقط یک بار عبور می‌کند و گرافی که شامل یک مسیر همیلتونی است را یک گراف همیلتونی یا گراف قابل ردیابی می نامیم و اگر برای هر دو جفت راس یک مسیر همیلتونی بین آن دو راس وجود داشته باشد آن را یک گراف همیلتونی پیوسته می نامیم.
و یک دور همیلتونی یک دور است که از هر راس فقط یک بار عبور می‌کند به جز راسی که در ابتدا و انتها است که دوبار پیموده شده است و گرافی که شامل یک دور همیلتونی است را گراف همیلتونی می نامیم و همین نامگذاری را می‌توان برای گراف های جهت دار تعمیم داد با توجه به این که هر یال ار یک مسیر یا دور در یک جهت خاص قرار دارد.
قضیهٔ Bondy chvatal
بهترین خاصیت گراف های همیلتونی در سال ۱۹۷۲ توسط Bondy chavatal بیان شد که تعمیم قضیهٔ Dirac و Ore بود که به نحوی بیان می‌کند یک گراف همیلتونی است اگر به اندازهٔ کافی یال داشته باشد که در زیر بیش تر توضیح داده می‌شود.
ابتدا خاتمهٔ یک گراف را به این شکل تعریف می کنیم که یک گراف G با n راس داریم(cal(G را خاتمهٔ G را می نامیم که از G ساخته می‌شد و با وصل کردن هر دو راس غیر همجوار v و U که مجموع درجات آن ها برابر یا بزرگتر از n است.
و قضیهٔBondy chvatal در سال ۱۹۷۲ بیان می‌کند که یک گراف همیلتونی است اگر و فقط اگر خاتمهٔ آن همیلتونی باشد. و اکنون به بیان قضیهٔ Dirac وOre نیز می پردازیم.
قضیهٔ Dirac
یک گراف ساده با n راس (2<n)همیلتونی است اگر هر راس درجه مساوی یقضیهٔ Dirac
یک گراف ساده با n راس (2<n)همیلتونی است اگر هر راس درجه مساوی یا بزرکتر از n / 2 داشته باشد.ا بزرکتر از n / 2 داشته باشد.
قضیهٔ Ore
یک گراف ساده با n راس (2<n)همیلتونی است اگر هر دو راس غیر مجاور مجموعه درجات آن ها بزرگتر یا مساوی n باشد. البته دو قضیه هم برای گراف های جهت دار وجود دارد
قضیهٔ Ghouil Houiri
یک گراف قویا همبند جهت دار ساده با n راس همیلتونی است یا این که تعدادی از راس ها درجهٔ کامل کمتر از n باشند
قضیهٔ Meyneil
یک گراف قویا همبند ساده با n راس همیلتونی است یا این که جمع درجه کامل از دو راس مجزای غیر مجاور کمتر از 2n − 1 باشد
تعریف
یک مسیر همیلتونی یا یک مسیر قابل ردیابی یک مسیر است که از هر راس فقط یک بار عبور می‌کند و گرافی که شامل یک مسیر همیلتونی است را یک گراف همیلتونی یا گراف قابل ردیابی می نامیم و اگر برای هر دو جفت راس یک مسیر همیلتونی بین آن دو راس وجود داشته باشد آن را یک گراف همیلتونی پیوسته می نامیم.
و یک دور همیلتونی یک دور است که از هر راس فقط یک بار عبور می‌کند به جز راسی که در ابتدا و انتها است که دوبار پیموده شده است و گرافی که شامل یک دور همیلتونی است را گراف همیلتونی می نامیم و همین نامگذاری را می‌توان برای گراف های جهت دار تعمیم داد با توجه به این که هر یال ار یک مسیر یا دور در یک جهت خاص قرار دارد.
قضیهٔ Bondy chvatal
بهترین خاصیت گراف های همیلتونی در سال ۱۹۷۲ توسط Bondy chavatal بیان شد که تعمیم قضیهٔ Dirac و Ore بود که به نحوی بیان می‌کند یک گراف همیلتونی است اگر به اندازهٔ کافی یال داشته باشد که در زیر بیش تر توضیح داده می‌شود.
ابتدا خاتمهٔ یک گراف را به این شکل تعریف می کنیم که یک گراف G با n راس داریم(cal(G را خاتمهٔ G را می نامیم که از G ساخته می‌شد و با وصل کردن هر دو راس غیر همجوار v و U که مجموع درجات آن ها برابر یا بزرگتر از n است.
و قضیهٔBondy chvatal در سال ۱۹۷۲ بیان می‌کند که یک گراف همیلتونی است اگر و فقط اگر خاتمهٔ آن همیلتونی باشد. و اکنون به بیان قضیهٔ Dirac وOre نیز می پردازیم.
قضیهٔ Dirac
یک گراف ساده با n راس (2<n)همیلتونی است اگر هر راس درجه مساوی یقضیهٔ Dirac
یک گراف ساده با n راس (2<n)همیلتونی است اگر هر راس درجه مساوی یا بزرکتر از n / 2 داشته باشد.ا بزرکتر از n / 2 داشته باشد.
قضیهٔ Ore
یک گراف ساده با n راس (2<n)همیلتونی است اگر هر دو راس غیر مجاور مجموعه درجات آن ها بزرگتر یا مساوی n باشد. البته دو قضیه هم برای گراف های جهت دار وجود دارد
قضیهٔ Ghouil Houiri
یک گراف قویا همبند جهت دار ساده با n راس همیلتونی است یا این که تعدادی از راس ها درجهٔ کامل کمتر از n باشند
قضیهٔ Meyneil
یک گراف قویا همبند ساده با n راس همیلتونی است یا این که جمع درجه کامل از دو راس مجزای غیر مجاور کمتر از 2n − 1 باشد