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

گراف اویلری: مسلما همه شما ماجرای شهر های کونیگسبرگ را شنیده اید و از چندو چون کار آگاه هستید اما برای آن دسته از عزیزانی که تازه وارد مبحث گراف شده اند این ماجرا در ذیل شرح داده شده است:
از وسط شهر كونيگسبرگ رودخانه اي مي گذرد كه دو جزيره را در برگرفته است . در آن زمان بين ساحل رودخانه و جزيره ها 7 پل وجود داشت.مساله اين بود كه شخصي از هر يك از نواحي A ، B ، Cو يا D حركت كند و از هر يك از پل ها يك بار و فقط يك بار بگذزرد و به نقطه شروع بازگردد. اهالي شهر در هنگام گردش وپياده روي مي كوشيدند مساله را عملا حل كنند. ولي كوشش آن ها بي نتيجه مي ماند. تا اين كه اويلر با باداع نظريه اي كه در آن هندسه بدون اندازه ناميد توانست حل ناپذيري آن را ثابت كند. اويلر ابتدا مدلي رياضي براي مساله درست كرد : به هر يك از جزيره ها و ساحل ها يك نقطه نسبت داد و دو نقطه متناظر با دو ناحيه اي را كه با پلي مرتبط بودند با پاره خط يا كماني به هم وصل كرد.اویلر با استدلالی ساده ثابت کرد که بحث راجب این موضوع بیهوده و این کار غیر ممکن است..
سر اغاز مبحث گراف اویلری را با این داستان آغاز کردیم و حالا ادامه مبحث خودمان:
تعریف دقیق گراف اویلری:گراف G را گرافی اولیری گویند هر گاه در آن مسیری وجود داشته بشاد که از هر یال تنها و تنها یک بار عبور کند.(گراف باید همبند باشد.)
به احتمال زیاد بیشتر خوانندگان تا به حال سعی کرده اند که شکلی را بدون برداشتن خودکار از روی کاغذ رسم نمایند.هر شکلی که بدین صورت بتوانید رسم نمایید یک گراف اویلری است.به شرطی که تمامی خوطوط راست باشند تا بتوان شکستگی ها را رئوس گراف و خطوط را یال ها در نظر گرفت.
چند مثال از گراف اولیری را در زیر مشاهده می کنید.
برای درک بهتر خود سعی کنید این گراف ها را بدون برداشتن خودکار از روی کاغذ رسم کنید.
  

گراف همیلتنی: گرافی همبندی که شامل مسیریست که از هر راس گراف مذکور تنها و تنها یک بار می گذرد گراف همیلتنی نام دارد.(محدودیتی در ارتباط با گذشتن از یک یال نیست.)

مسیر همیلتونی :
در تئوری گراف ها یک مسیر همیلتونی در یک گراف بدون جهت یک مسیر است که از هر راس فقط یک بار گذشته باشد.
دور همیلتونی : یک دور همیلتونی در یک گراف ساده بدون جهت یک دور است که از هر راس فقط یک بار عبور می کند و به راس اول باز می گردد و محاسبه این که یک گراف دارای مسیر یا دور همیلتونی است از مسائل NP-complete است
و باز هم در زیر چند نمونه از گراف همیلتنی را نظاره می کنید.
منبع
+ نوشته شده در پنجشنبه یازدهم مهر 1387ساعت 14:31 توسط امیرمحمدی راد |