مقاطع تحصیلی
جستجو در منظومه
با توجه به آنچه گفته شد ِ گراف زیر، ِ گراف حاصل از مدل سازی برای این مسئله است.g ac ke fd شکل 4حال کافی است یک ٔ مجموعه احاطه گر مینیمم در این گراف بیابیم و ایستگاه های رادیویی را در شهرهای متناظر با رئوساین مجموعه احاطه ِ گر مینیمم مستقر کنیم. یافتن یک ٔ مجموعه احاطه گر مینیمم برای گراف فوق در تمرینات پایان درس به شماواگذار شده است.کار در کالس1 مشخص کنید کدام یک ازمجموعه های زیر برای گراف شکل 5 احاطه گر aهست و کدام نیست؟ fالف) } e, d, c, b, a { = A b g j eب) } j, i, h, g, f { = Bپ) } g, h, j, b, a { = Cت) } h, i, a { = D hث) } d, e, h, g, f { = E c iج) } e, h, g, f { = F شکل 5 dچ) e}, h, {g = H٢ از مجموعه های مطرح شده در سؤال 1 که احاطه گر بودند در کدام یک از آنها رأس یا رأس هایی وجود دارد که با حذفآنها ٔ مجموعه باقی مانده هنوز احاطه گر باشد؟تعریف: یک ٔ مجموعه احاطه گر را که با حذف هر یک از رأس هایش دیگر احاطه گر نباشد احاطه گر مینیمال می‌نامیم.3 مجموعه ای احاطه گر با کمترین تعداد رأس که می‌توانید، بنویسید و پاسخ خود را با پاسخ هم کالسی های خود مقایسه کنید.4 یک ٔ مجموعه احاطه گر مینیمال مشخص کنید که مینیمم نباشد.فصل دوم: گراف و مدل سازی 46