درس ۱ · صفحهٔ ۳۱ تا ۴۳ · حدود ۱۵ دقیقه · تولید هوش مصنوعی
درس ۱: معرفی گراف
در این درس یاد میگیری موقعیتهای ساده را با گراف نمایش دهی، ویژگیهای اصلی گراف و ارتباط رأسها را تشخیص دهی و با رابطهٔ مجموع درجهها، تعداد یالها و امکانپذیری بعضی گرافها را بررسی کنی.
پیش از شروع
آیا ممکن است در یک جمع هفتنفره، هر نفر دقیقاً با سه نفر دیگر دوست باشد، اگر دوستی همیشه دوطرفه باشد؟ چطور میتوان بدون امتحانکردن همهٔ حالتها پاسخ داد؟
نه؛ اگر هر نفر سه دوست داشته باشد، مجموع تعداد دوستها برابر با میشود. اما هر دوستی در این شمارش دو بار حساب میشود، یک بار برای هر طرف؛ پس این مجموع باید زوج باشد! با تبدیل افراد به نقطه و دوستیها به خط، میتوانیم این استدلال را به زبان گراف بیان کنیم.
از یک موقعیت تا یک گراف
از یک موقعیت تا یک گراف
اگر بخواهی ارتباطهای یک گروه را خلاصه نشان دهی، لازم نیست همهچیز را جملهبهجمله بنویسی. برای هر عضو یک نقطه به نام رأس بگذار و ارتباط میان دو عضو را با یک یال نشان بده. یال میتواند خط راست یا منحنی باشد؛ مهم این است که کدام رأسها را به هم وصل میکند.
پیش از رسم، مشخص کن یال چه معنایی دارد: دوستی، انجامشدن مسابقه یا وجود راه میان دو شهر؟
گراف را با مجموعهها هم معرفی میکنیم: مجموعهٔ رأسها و مجموعهٔ یالهاست. مثلاً و یعنی ارتباط میان و و نیز میان و وجود دارد، اما میان و نیست.
گاهی جهت ارتباط مهم است. اگر پیکان را از تیم برنده به تیم بازنده بکشیم، یک گراف جهتدار داریم. در این حالت یال را با زوج مرتب مینویسیم: یعنی پیکان از به است؛ پس جابهجایی ترتیب، معنی را عوض میکند.
کتاب درسی، صفحهٔ ۳۲
شمارش رأسها، یالها و درجهها
شمارش رأسها، یالها و درجهها
در گرافِ دوستیِ یک کلاس، تعداد دانشآموزان و تعداد رابطههای دوستی دو چیز متفاوتاند. برای بیان دقیق این تفاوت، سه اصطلاح داریم:
- مرتبه، تعداد رأسهای گراف است: .
- اندازه، تعداد یالهای گراف است: .
- درجهٔ رأس، تعداد یالهای متصل به همان رأس است و با یا نمایش داده میشود. پس در گراف دوستی، درجهٔ هر دانشآموز تعداد دوستان اوست، نه تعداد کل دوستیها.
اگر درجهٔ رأسی فرد باشد، آن را رأس فرد و اگر زوج باشد، رأس زوج مینامیم. بزرگ یا کوچک بودن تصویر و صاف یا خمیده کشیدن یالها این شمارشها را تغییر نمیدهد؛ مهم این است که کدام رأسها به هم وصلاند.
اگر درجهٔ همهٔ رأسها برابر با باشد، گراف ـ منتظم است. رأسی که درجهاش باشد، رأس تنها نام دارد؛ چنین رأسی همچنان در مرتبهٔ گراف شمرده میشود. اگر همهٔ رأسها تنها باشند، گراف تهی است: رأس دارد، اما هیچ یالی ندارد.
کتاب درسی، صفحهٔ ۳۵
همسایهها، زیرگراف و مکمل
همسایهها، زیرگراف و مکمل
در گراف ساده، طوقه نداریم؛ یعنی یالی از یک رأس به خودش وصل نمیشود. بین هر دو رأس هم حداکثر یک یال داریم.
در یک شبکهٔ دوستیِ دوطرفه، دوستان مستقیمِ فرد ، همسایههای او هستند. مجموعهٔ آنها، یعنی ، همسایگی باز است؛ با افزودن خودِ ، همسایگی بسته به دست میآید:
دو یال هم وقتی مجاورند که سرِ مشترک داشته باشند. پس یالهای و مجاورند، حتی اگر و همسایه نباشند.
با مقایسهٔ درجهٔ همهٔ رأسها، کمترین درجه را با و بیشترین را با نشان میدهیم.
حالا دو روش متفاوت برای ساختن گراف داریم:
- زیرگراف: فقط از رأسها و یالهای گراف اصلی انتخاب میکنیم؛ نمیتوانیم یال تازهای بسازیم و دو سر هر یال انتخابشده باید باقی بمانند.
- مکمل: همهٔ رأسها را نگه میداریم، اما اتصال هر دو رأس متمایز را برعکس میکنیم: یالهای قبلی حذف و یالهای غایب اضافه میشوند.
در مثال دوستی، مکمل نشان میدهد چه کسانی با هم دوست نیستند؛ نه اینکه بعضی افراد را از جمع کنار بگذاریم.
کتاب درسی، صفحهٔ ۳۷
از اتصال مستقیم تا مسیر و دور
از اتصال مستقیم تا مسیر و دور
در یک شبکهٔ دوستی، لازم نیست دو نفر مستقیماً دوست باشند تا بتوان از راه دوستانِ مشترک بین آنها ارتباط پیدا کرد. این تفاوتِ «اتصال مستقیم» و «وجود راه» در گراف مهم است.
گراف کامل گرافی است که هر رأس آن به تمام رأسهای دیگر وصل باشد؛ گراف کامل با رأس را با نشان میدهیم.
مسیر دنبالهای از رأسهای بدون تکرار است که هر دو رأسِ پشتسرهم آن با یک یال وصلاند. طول مسیر، تعداد یالهای آن است، نه تعداد رأسها. مثلاً در مسیر از سه یال میگذریم، پس طول آن است. گرافی که فقط یک مسیر با رأس باشد، نام دارد.
دور راهی بسته است: به رأس شروع برمیگردیم، اما هیچ رأس دیگری تکرار نمیشود. دور دستکم سه یال دارد؛ گرافی که فقط یک دور با رأس باشد، نام دارد.
گراف همبند است اگر بین هر دو رأس آن دستکم یک مسیر وجود داشته باشد. پس همبندبودن الزاماً به معنای کاملبودن نیست!
کتاب درسی، صفحهٔ ۳۸
هر یال، دو سهم در درجهها
هر یال، دو سهم در درجهها
یک رابطهٔ دوستی دوطرفه را تصور کن: این رابطه هم در تعداد دوستان تو حساب میشود و هم در تعداد دوستان طرف مقابل. در گراف هم هر یال دو سر دارد؛ پس هنگام جمعکردن درجهٔ همهٔ رأسها، هر یال دقیقاً دو بار شمرده میشود. بنابراین برای گرافی با اندازهٔ داریم:
پس مجموع درجهها همیشه زوج است. درجههای زوج بهتنهایی مجموعی زوج دارند؛ بنابراین مجموع درجههای فرد هم باید زوج باشد. جمعِ تعداد فردی عدد فرد، فرد میشود؛ پس تعداد رأسهای فرد حتماً زوج است، نه لزوماً درجهٔ تکتک رأسها!
حالا به جمع هفتنفرهٔ ابتدای درس فکر کن: اگر همه دقیقاً سه دوست داشته باشند، همهٔ رأسها فرد میشوند؛ اما تعدادشان فرد است، پس چنین وضعیتی ممکن نیست.
این رابطه یک میانبُر هم میدهد: در گراف رأسیِ ـ منتظم، مجموع درجهها است، پس . در گراف کامل، درجهٔ هر رأس است؛ بنابراین .
کتاب درسی، صفحهٔ ۴۰
مثال حلشده
دوستی را رابطهای دوطرفه در نظر بگیر. اگر در یک جمع ششنفره هر نفر دقیقاً سه دوست در همان جمع داشته باشد، گراف دوستی چند یال دارد؟ آیا در یک جمع هفتنفره هم ممکن است هر نفر دقیقاً سه دوست داشته باشد؟
هر نفر را یک رأس و هر دوستی دوطرفه را یک یال میگیریم؛ پس درجهٔ هر رأس برابر تعداد دوستان آن فرد است.
در جمع ششنفره، مجموع درجهها برابر است با .
چون هر دوستی در درجهٔ هر دو نفر شمرده میشود، داریم ؛ بنابراین .
این وضعیت برای شش نفر شدنی است: آنها را به دو گروه سهنفره تقسیم کن و هر نفر را فقط با تمام افراد گروه مقابل دوست در نظر بگیر.
در جمع هفتنفره، فرض مسئله مجموع درجهها را برابر میکند؛ اما مجموع درجهها باید زوج باشد. پس چنین جمعی ممکن نیست.
نکات مهم
- در مدلسازی با گراف، اعضا را رأس و ارتباطها را یال میگیریم؛ مرتبه تعداد رأسها، اندازه تعداد یالها و درجهٔ هر رأس تعداد یالهای متصل به آن است.
- همسایگی اتصالهای مستقیم را نشان میدهد، مسیر و دور اتصالهای پیاپی را توصیف میکنند و مکمل با حفظ همهٔ رأسها، یالهای موجود و ناموجود میان رأسهای متمایز را جابهجا میکند.
- هر یال دو سهم در مجموع درجهها دارد؛ بنابراین و تعداد رأسهای دارای درجهٔ فرد، زوج است.