منو
 کاربر Online
409 کاربر online

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

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


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

پس از پایان تعاریف و مفاهیم گذر اویلری باید گفت که همانطور که در گذر اویلری هدف پیمودن تمام یالها دقیقاً‌ یکبار و بازگشتن به نقطه شروع می باشد،‌ در مبحث همیلتونی هدف طی کردن تمام راسها دقیقاً یکبار و برگشتن به راس آغازین می باشد. دقت کنید در دور همیلتونی الزاماً همه یالها پیمایش نمی شوند.

تعاریف

مسیر همیلتونی

مسیری از گراف که شامل هر راس باشد مسیر همیلتونی می نامند ( در مسیر راس تکراری نداریم )

دور همیلتونی

مشابه بالا دوری است که شامل همه رئوس باشد.
دور همیلتونی دوری به طول می باشد.
نام همیلتون به این دسته از دورها از سر ویلیام همیلتون به خاطر تحقیقات وی در وجود این مدارها در گراف خاصی به نام گراف همیلتون گرفته شده است.
گراف هامیلتون یک دوازده وجهی منتظم می باشد که اگر آن را در صفحه بخواهیم رسم کنیم به صورت زیر در می آید:
img/daneshnameh_up/6/63/mco0064a.jpg

جالب است که این گراف هامیلتونی بوده و دارای دورهای هامیلتونی زیبایی است که در کمکی آموزشی آمده است.
اما در مبحث گرافهای اویلری دیدیم که با یک شرط لازم و کافی برای اویلری بودن به تمام ابهامات پاسخ داده شد و بسیار به نظر می رسد که چنین شرط لازم و کافی ای در این مبحث نیز وجود داشته باشد ولیکن تعیین شرط یا شروط لازم و کافی همیلتونی بودن یک گراف هنوز به عنوان یک مساله لاینحل باقی مانده است،
اگر چه شرط لازم کافی محکم نداریم ولیکن شروط لازم نسبتاً خوبی برای همیلتونی بودن وجود دارند که به ترتیب بیان می گردند:

قضیه

اگر یک گراف ساده با راس باشد و اگر برای هر دو راس نا مجاور داشته باشیمآنگاه هامیلتونی است
اثبات
چون همبند است پس هر دو راس آن با مسیری به هم متصل می باشند بنابراین می توان یک مسیر همیلتنی مانند بدست آورد. ( چرا؟ ) اگر این مسیر هامیلتونی خود یک مدار همیلتنی باشد حکم حاصل شده است در غیر این صورت رئوس غیر همجوارند. در این صورت می‌توان نوشت

آنگاه راسی مانند همجوار با وجود دارد به طوری که همجوار است ( چرا؟ )
img/daneshnameh_up/2/2d/mco0064b.jpg

در این صورت یک مدار هامیلتونی در مانند

یافته ایم پس همیلتونی است.

نتیجه

قضیه دیراک

اگر در گراف ساده و همبند با راس داشته باشیم:
(راس دلخواه از است)
آنگاه همیلتنی است.
اثبات
دو راس غیر همجوار مانندرا اختیار می کنیم ( حتماً دو راس غیر همجوار وجود دارد چون اگر نباشد گراف کامل است و در نتیجه همیلتنی است )
آنگاه می توان نوشت
پس طبق قضیه قبل همیلتنی است.

مثال

در گراف اویلری شرط تکراری نبودن یالها را داریم و می دانیم که ممکن است درگذر اویلری راسها تکرار شوند، در عوض در گراف های همیلتونی شرط تکراری نبودن راسها را در دور همیلتونی داریم. آیا ممکن است در دور هامیلتونی یال تکراری داشته باشیم؟
حل
معلوم است که نه! زیرا اگر یالی تکرار شود دو راس دو سر آن هم تکرار می شود و این با تعریف دور همیلتونی تناقض دارد.

پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0098.pdf

همچنین ببینید



تعداد بازدید ها: 30657


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..