مقاطع تحصیلی
جستجو در منظومه
بنابراین:اگر G یک گراف n رأسی با ماکزیمم ٔ درجه ∆ باشد و D یک ٔ مجموعه احاطه گر در آن باشد، آنگاه D ≥ n + 1 ∆ و از آنجا که (γ)G نیز اندازه یک ٔ مجموعه احاطه گر است همواره داریم (G γ (≥ n + 1 ∆ )اصطالحاً گفته می‌شوددر گراف G عدد n + 1 ∆ یک کران پایین است برای (γ)G ؛ یعنی (γ)G نمی‌تواند از آن کمتر شود).کار در کالس1 یک شبکه رایانه ای متشکل از 16 رایانه را در نظر بگیرید که در آن هر رایانه، مطابق شکل 9 به چند رایانه دیگر متصل است.گراف شکل 9 یک مدل سازی از شبکه مورد نظر است که در آن هر رأس i k jنمایشگر یک رایانه است و یال بین دو رأس نمایانگر آن است که رایانه های lنظیر به آن دو رأس مستقیماً با هم در ارتباط اند. می‌خواهیم مجموعه ای با a b o m nکمترین تعداد ممکن از رایانهها (رأس ها) انتخاب کنیم. به طوری که توسط c d pاین مجموعه از رایانهها به تمام رایانههای این شبکه وصل باشیم. ٔ مجموعه e fانتخاب شده از رئوس برای گراف مورد نظر چه نوع مجموعه ای است؟ شکل g h 9٢ با توجه به ٔ رابطه (G γ) ≥ n + 1 ∆ ، حداقل چند رأس برای احاطه کردن تمام رئوس این گراف الزم است؟ آیا می‌توانیدمجموعه ای احاطه گر با این تعداد رأس مشخص نمایید؟٣ گراف های C 10, P 9, P 10 و C 9 را رسم کنید و عدد احاطه گری هر یک را مشخص نمایید.٤ گرافی مشخص کنید که برای آن عدد احاطه گر برابر n + 1 ∆ باشد.٥ گرافی مشخص کنید که برای آن عدد احاطه گر برابر n + 1 ∆ نباشد.b aمثال: عدد احاطه گری گراف شکل 10 را مشخص و ادعای خود را ثابت کنید. a bحل: به سادگی می‌توان دید که ٔ مجموعه دو عضوی { a, c } یک مجموعه احاطه گر است. cبنابراین عدد احاطه گری این گراف کوچک تر یا مساوی 2 است؛ 2یعنی ≥ (γ . c d e)Gاما اگر = 1 (γ)G ، یعنی یک رأس در گراف G وجود دارد که به تنهایی تمام رئوس دیگر را e dاحاطه کرده است (به تمام رئوس دیگر وصل است) یعنی رأسی با ٔ درجه 4 در گراف وجود دارد که Gبا توجه به گراف G می‌بینیم که چنین رأسی وجود ندارد و لذا <1 (γ .)G بنابراین 2 ≥ (γ)G 1> و شکل G 10لذا = 2 (. γ)G49 درس دوم: مدل سازی با گراف