مقاطع تحصیلی
جستجو در منظومه
مثال: برای گراف شکل 3 که دور C 7 است، ٔ مجموعه } v 1, v 3, v 5, v 7 { یک v 1 vٔ مجموعه احاطه گر و مجموعه های } v 1, v 4, v 7 { و } v 1, v 2, v 5 { دو ٔ مجموعه 2احاطه گر مینیمم یا اصطالحاً دو γ ــ مجموعه اند؛ و داریم = 3 (γ . v 7 v)G36 v4 vشکل v 5 3مثال: فرض کنید a ، b ، c ، d ، e ، f ، g ، h ، i ، j و k شهرهای یک استان باشند و فاصله های مستقیم این شهرها از یکدیگر،دو به دو، مطابق جدول زیر باشد.k j i h g f e d c b a50 60 50 70 50 90 60 40 80 50 0 a80 85 90 60 60 70 60 30 55 0 50 b90 95 100 55 50 20 60 40 0 55 80 c70 75 80 30 30 55 30 0 40 30 40 d55 55 60 5 10 50 0 30 60 60 60 e80 90 100 45 40 0 50 55 20 70 90 f60 65 70 5 0 40 10 30 50 60 50 g55 60 65 0 5 45 5 30 55 60 70 h10 5 0 65 70 100 60 80 100 90 50 i5 0 5 60 65 90 55 75 95 85 60 j0 5 10 55 60 80 55 70 90 80 50 kمی‌خواهیم تعدادی ایستگاه رادیویی در برخی از شهرهای این استان تأسیس کنیم به طوری که ٔ همه شهرهای استان از پوششامواج رادیویی برخوردار گردند. و از طرفی برای کاهش هزینه ها می‌خواهیم کمترین تعداد ممکن ایستگاه رادیویی را احداثکنیم. اگر هر ایستگاه رادیویی تا 50 کیلومتر اطراف خود را پوشش دهد، حداقل چند ایستگاه رادیویی احتیاج داریم و در چهشهرهایی باید آنها را احداث کنیم؟حل: برای مدل سازی این مسئله کافی است گراف مربوط به آن را به این طریق رسم کنیم که به جای هر شهر یک رأس قراردهیم و سپس دو رأس را به هم وصل کنیم اگر و تنها اگر ٔ فاصله مستقیم آن دو شهر از 50 کیلومتر بیشتر نباشد. در این صورتٔ مجموعه احاطه ِ گر مینیمم برای گراف مذکور، جواب مسئله را مشخص می‌کند. (چرا؟)45 درس دوم: مدل سازی با گراف