گراف چیست؟
مدت ها پیش در شهری به نام کونیگسبرگ رودخانه ای قرار داشت و شهر را به 4 بخش تقسیم کرده بود.
اون 4 بخش با 7 پل به هم متصل بودند.
مردم این شهر آخر هفته ها روی این پل ها پیاده روی میکردند. در هنگام پیاده روی سوالی برایشان پیش می آید:
آیا میشود از یکی از 4 بخش شهر شروع کرده و روی هر 7 تا پل پیاده روی کنیم و دوباره به همان بخشی که ازش شروع کردیم برگردیم، بدون اینکه از پلی دوبار عبور کنیم؟
(با بله یا خیر پاسخ دهید)
این سوال به گوش آقای اویلر میرسه و آقای اویلر هم مثل شما سعی میکنه اون را حل کنه. قبل از اینکه راه حل مسئله رو بگم، بیاین با هم ببینیم آقای اویلر برای حل این مسئله چه کار کرده.
آقای اویلر دید که یه سری ویژگی ها در شکل مسئله وجود دارد که برای حل مسئله به آن ها نیازی نیست. مثلا مساحت هر کدوم از 4 بخش یا طول ویا شکل پل ها اهمیتی نداره و تنها چیز مورد نیاز، این است که هر پل بین کدام دوبخش است.
برای همین یه شکل جدید درست میکنه و توی اون شکل به جای هر کدوم از 4 بخش یه نقطه و به جای پل ها، پاره خط میذاره.
حواستون باشه توی این شکل جدید مکان هندسی نقاط و شکل پاره خط ها اهمیتی نداره.
آقای اویلر که دید این شکل جدید (مدل سازی کردن با نقطه و پاره خط) میتونه خیلی پرکاربرد باشه براش اسم گذاشت و یه سری چیزمیز روش تعریف کرد.
اسم این شکل یا مدل سازی "گراف" عه.
- راس: اسم اون نقطه ها
- یال: اسم اون پاره خط ها
- درجه: به ازای هر راس تعریف میشه و برابر تعداد یال هایی ست که به اون راس متصله.
- دنباله درجات: دنباله ای ایست شامل درجه راس ها.
توی گراف دو سر هر یال باید به راس وصل باشه (مثلا نمیتونه یه سرش رها باشه) ولی دو سر یک یال میتونه فقط به یک راس وصل باشه که اسمش هست "طوقه".
اگه راسی طوقه داشته باشه، اون طوقه هه به درجه اون راس دو تا اضافه میکنه.
بین هر دو راس هر تعدادی یال میتونه وجود داشته باشه (مثلا میتونه یالی بینشون نباشه، یک یال باشه و یا 13 تا یال باشه)
پس تعریف گراف اینه: یه سری راس و یال که هر یال بین دو راس می باشد. (لزومی نداره اون دو راس، دو راس مختلف باشند)
بریم سراغ مسئله بالای صفحه؛ چون دیگه گراف رو گفتیم چیه همون مسئله را روی گرافش حل میکنیم.
توی اون مسیر هر یال رو دقیقا یکبار میبینیم و در پایان به راسی که ازش شروع کردیم بر میگردیم. پس هرباری که با یک یال به راسی میرویم باید با یک یال دیگه از اون راس خارج بشیم که در نتیجه درجه هر راس باید زوج باشه. (برای راس شروع در ابتدا با یک یال ازش خارج میشویم و در انتها با یک یال دیگر وارد میشویم که درنتیجه درجه راس شروع هم باید زوج باشه)
ولی درجه همه ی رئوس فرد است.
یادته توی چند درس پیش ببعییی میخواست بره مسافرت. اگه هر کشور را یه راس و هر راه بین دو کشور را یال در نظر بگیریم؛ دنباله درجات این گراف چقدر میشه؟
(دنباله درجات را از بزرگ به کوچیک، از چپ به راست بنویس و بین هر دوتا عدد یه فاصله بده)
پاسخ - 5 5 4 4 4
- درجه راس ایران:
5 - درجه راس گینه نو:
5 - درجه راس فنلاند:
4 - درجه راس اتریش:
4 - درجه راس هندوراس:
4
مجموع درجات یک گراف چند برابر تعداد یال های آن است؟
(یه سری گراف برای خودت بکش ببین جواب چی میشه)
ببین هر یال توی درجه چند تا راس حساب میشه.
پاسخ - 2
هر یال بین دوتا راس عه.
- یا بین دوتا راس مختلفه پس دو بار شمرده میشه.
- یا طوقه ست که قبل تر گفتیم توی درجه اون راس
2تا حساب میشه.
پس مجموع درجات دو برابر تعداد یال ها در تمامی گراف هاست.
تعریف مسیر در گراف:
دنباله ای از رئوس گراف که راس تکراری ندارد و هر دو راس متوالی در دنباله به هم یال داشته باشند.
مثال:
الان دنباله (e, j, h, f) یک مسیر از این گراف است. دقت کن که مسیر (e, j, h, f) با مسیر (f, h, j, e) یکسان است.
طول بلندترین مسیر در گراف زیر چند است؟
(طول یک مسیر برابر تعداد یال های آن است)
تعریف همبندی در گراف:
اگر در گرافی از هر راس به راسی دیگر مسیری وجود داشت؛ به آن گراف همبند میگیم.
و اگه یه گراف همبند نباشه، ناهمبند هستش.
کشوری 15 شهر داره که هر یک از اونا به حداقل 7 شهر دیگه جاده های مستقیم دارن. ببعییی میخواد بدونه اگر با هواپیما به یکی از این شهرها بره و داخل کشور فقط از طریق جاده ها سفر کنه، حداقل چند شهر رو میتونه ببینه؟
اگه شهرها رو راس و جاده ها رو یال در نظر بگیریم به یک گراف همبند میرسیم. (به نظرت چرا؟)
پاسخ - 15
گراف همبنده
اثبات:
فرض کن گراف همبند نباشه، اونوقت دوتا راس وجود داره که به هم مسیری ندارند و از طرفی هرکدوم به حداقل 7 تا راس دیگه یال دارند. پس تعداد رئوس گراف حداقل 16 تا میشه. ※
※ علامت تناقض است.
پس بین هر دو شهری یه مسیری وجود داره و ببعییی میتونه همه شهرها رو ببینه.
تعریف دور در گراف:
دنباله ای از رئوس گراف که در وسط دنباله راس تکراری ندارد، هر دو راس متوالی در دنباله به هم یال داشته باشند و همچنین راس شروع و پایان دنباله یکسان باشند.
مثال:
(a, b, c, d, e, a)
شکل زیر نقشه شهرهای یک کشور با جاده های بین آنها را نشان می دهد. در این نقشه، نقاط توپر نشان دهنده شهرها و پاره خط های بین آنها نشان دهنده جاده ها هستند. عددهای روی جاده ها، طول جاده ها را نشان می‌دهند. ببعییی می‌خواهد از یکی از شهرها شروع و از همه شهرها بازدید کند. او حداقل چه مسافتی را باید طی کند؟
پاسخ - 47
ترتیب رفتن به شهرها:
f → i → e → i → j → g → a → g → b → g → j → h → c → h → d