سایت پاورپوینت دانشجویی آماده درسی با طبقه بندی ,نمونه پاورپوینت

نام فایل : جايگاه مراكز رشد(Incubator) در توسعه کار آفرینی

فرمت : .ppt

تعداد صفحه/اسلاید : 84

حجم : 4078 کیلوبایت

مقدمه ای بر نظریه گراف
اردیبهشت 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 برقرار باشد، مسأله حل است:
....