در حال بارگذاری...
خطا
در گراف روبهرو، کدام مجموعه، احاطهگر مینیمال نیست؟
کمی جستجو کنید! به نظر میرسد با دو رأس، نمیتوانیم کل رأسهای دیگر را پوشش دهیم. من میگویم بهتر است از قسمت چپ گراف، $i$ را در نظر بگیریم و از راستی هم، $j$ را بگیریم، اما هنوز رأس $d$ به هیچکدام وصل نیست. مجموعهی $\left\{ i,j,d \right\}$ یک مجموعهی احاطهگر مینیمم است، پس $\gamma (G)=3$ میشود. با حذف هر کدام از سه عضو $i$ یا $j$ یا $d$، مجموعهی $\left\{ i,j,d \right\}$، دیگر یک $-\gamma $ نیست، پس این مجموعه، احاطهگر مینیمال هم میشود. در بالا هم گفتیم که هر مجموعهی احاطهگر مینیمم، مینیمال هم هست. اما مجموعهی $\left\{ i,d,b,g \right\}$ مینیمال نیست، زیرا اگر $g$ را حذف کنیم، مجموعهی $\left\{ i,d,b \right\}$ نیز باز احاطهگر است. بنابراین 2، پاسخ سؤال است. مجموعههای $\left\{ h,g,j,e \right\}$ و $\left\{ a,f,d,b \right\}$، نیز دو مجموعهی احاطهگر مینیمال هستند، زیرا اگر هر کدام از اعضای آن حذف شوند، مجموعههای باقیمانده، دیگر احاطهگر نیستند.