مقاطع تحصیلی
جستجو در منظومه
شکل مقابل ٔ نقشه منطقه ای از یک شهر است. قرار است در برخیتقاطع های این شهر دستگاه های خودپرداز به گونه ای نصب شود که دو شرطزیر را داشته باشد:1 برای راحتی شهروندان دستگاه ها به گونه ای نصب شده باشند که هرفرد در هر تقاطعی که قرار گرفته باشد، یا در همان تقاطع به دستگاه خودپردازدسترسی داشته باشد و یا حداکثر با رفتن به یک تقاطع مجاور به دستگاهخودپرداز دسترسی پیدا کند. شکل ١٢ به جهت صرفه جویی در هزینه ها با کمترین تعداد دستگاه خودپرداز ممکن a a b b c cاین کار صورت بگیرد.حال فرض کنید ٔ منطقه مورد نظر را با گراف شکل 2 مدل سازی کرده باشیم.الف) در این مدل سازی تقاطع ها و خیابان های بین آنها هر کدام به چه صورت d d e eنمایش داده شده اند؟ب) رأس هایی از گراف را مشخص کنید که، با توجه به مدل سازی انجام f f g gشده، اگر خودپردازها در آن تقاطع ها قرار گیرند، 1شرط برآورده گردد. چنین h hمجموعه ای از رئوس را یک ٔ مجموعه احاطه گر برای گراف می‌نامیم. به طور Gمثال ٔ مجموعه شامل همه رئوس گراف G ، یک مجموعه احاطه گر است. آیا شکل 2 Gمی‌توانید یک ٔ مجموعه احاطه گر 4 عضوی مثال بزنید؟تعریف: زیر ٔ مجموعه D از ٔ مجموعه رئوس گراف G را ٔ مجموعه احاطه گر می‌نامیم هرگاه هر رأس از گراف یا درD باشد و یا حداقل با یکی از رئوس D مجاور باشد. 1معموال ً به سادگی می‌توان مجموعه های مختلفی از رئوس گراف G را مشخص کرد که در شرط 1 صدق کنند؛ به عبارتییک گراف می‌تواند مجموعه های احاطه گر گوناگونی داشته باشد. از طرفی واضح است که هر مجموعه که شامل یک ٔ مجموعهاحاطه گر باشد، احاطه گر است. در بین تمام مجموعه های احاطه گر یک گراف، مجموعه ای را که کمترین تعداد عضو را داشتهباشد مجموعۀ احاطه گر مینیمم آن گراف می‌نامیم. اگر چنین مجموعه ای را برای گراف G بیابیم، این مجموعه در هر دوشرط 1 و 2 مطرح شده در ٔ مسئله باال صدق خواهد کرد.تعریف: در بین تمام مجموعه های احاطه گر گراف G ، مجموعه یا مجموعه های احاطه گری که کمترین تعداد عضو رادارند مجموعۀ احاطه گر مینیمم و تعداد اعضای چنین مجموعه ای را عدد احاطه گری گراف G می‌نامیم و آن را با (γ)Gنمایش می‌دهیم.گاهی اوقات برای راحتی به یک ٔ مجموعه احاطه گر مینیمم از گراف G ، یک γ ــ مجموعه می‌گوییم.ــ1 از آنجا که عدد احاطه گری یک گراف ناهمبند، به سادگی و با استفاده از یک عمل جمع به دست می‌آید، لذا در این کتاب عدد احاطه گری گراف های همبند مد نظر استمگر اینکه مستقیم ً ا به ناهمبندی گراف اشاره شود.فصل دوم: گراف و مدل سازی 44