مرجع دانلود پاورپوینت های درسی

حجم فایل : 2.4 MB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 84
مقدمه ای بر نظریه گراف اردیبهشت 1389
مثالهایی ملموس از گراف مسأله رسم شکلی بصورت زیر بدون آنکه قلم را از روی کاغذ برداریم و از یک جا شروع و به همانجا برگردیم: مثالهایی ملموس از گراف نقطه بازی: جدولی از نقاط داشته باشیم و هر نفر در نوبت خود دو نقطه ی مجاور را به هم وصل کند: سنگ بنای نظریه ی گراف پل کونیگسبرگ:
بر روی رودخانه Pregel هفت پل بصورت زیر ساخته شده بود. این 7 پل چهار خشکی C,B,A وD را به هم متصل می کرد.
سنگ بنای نظریه ی گراف آیا می توان با شروع از یک خشکی و طی کردن تمام پل ها بصورتی که از هر پل تنها یک بار گذشت به نقطه ی شروع اولیه رسید؟
سنگ بنای نظریه ی گراف اویلر در سال 1736 این مسأله را تبدیل به گراف زیر نمود و پاسخ آن را داد. معمای 1:ضیافت 6 نفره نشان دهید در هر جمع 6 نفری، یا حداقل سه نفر هستند که هر سه با هم آشنا هستند یا حداقل سه نفر هستند که هر سه با هم بیگانه اند.
جواب:
تکنیک حل این مسأله بر اساس کاربردی از گراف ها است.
بدین منظور گرافی را در نظر می گیریم که هر رأس یک نفر را نشان می دهد.
یال نقطه چین بین رئوس معادل بیگانه بودن

یال ممتد بین رئوس معادل آشنایی آن دو نفر
باید نشان دهیم که همواره مثلثی با رئوس ممتد یا مثلثی با رئوس نقطه چین موجود است!
معمای 1:ضیافت 6 نفره فرض کنیم که v یک رأس دلخواه از گراف باشد. در اینصورت 5 یال گذرا از v وجود دارد که ممتد یا نقطه چین اند. پس حداقل 3 تا از این یالها همنوعند! فرض کنیم سه یال ممتد وجود داشته باشد.(حالت مربوط به وجود لااقل 3 یال نقطه چنین، مشابه همین حالت است.)
پس گراف زیر را داریم: معمای 1:ضیافت 6 نفره اکنون اگر یکی از حالت آشنایی wبا x یا x با y ویا w با y برقرار باشد، مسأله حل است:

آشنایی x با y آشنایی w با y آشنایی w باx معمای 1:ضیافت 6 نفره در حالتی که نه w باx آشنا باشد و نه w با y و نه y با x ، گراف زیر را داریم:





یعنی w، x و y با هم بیگانه اند.

تمرین: در هر دسته 10 نفری یا 3 نفر بیگانه با هم یا 4 نفر آشنا با هم وجود دارد.
معمای 2:مسأله 8 دایره حروفE,D,C,B,A G,F, وH را در هشت دایره ی شکل زیر چنان قرار دهید که هیچ حرفی با حرف دیگری که در الفبای لاتین مجاور آن است، همسایه نباشد. تعریف گراف بطور غیر دقیق گراف مجموعه ای از نقاط (گره ها) است که ما آنها را رأس می نامیم به همراه تعدادی از خطوط متصل کننده ی این نقاط که آنها را یال نامیم.
نکته با توجه به اینکه یک گراف تنها مجموعه ای از رئوس و یالهاست پس تفاوتی بین گراف های زیر وجود ندارد و ما آنها را یکریخت می گوییم :
تعریف: تعداد رئوس در یک گراف را مرتبه ی آن گراف و تعداد یالها را اندازه ی
گراف نامند. گراف بدون جهت نکته:هر گراف ساده با n رأس حداکثر ...