در حال بارگذاری...
خطا
از مجموعهی احاطهگر $\left\{ b,c,d,e,f,g,h \right\}$ برای گراف زیر، حداکثر چند عضو میتوان حذف کرد که مجموعهی باقیمانده هنوز احاطهگر باشد؟
گراف داده شده (معروف به گراف پترسن)، $3$ - منتظم از مرتبهی $10$ است، پس: $\gamma (G)\ge \left\lceil \frac{n}{\Delta +1} \right\rceil =\left\lceil \frac{10}{3+1} \right\rceil =3$ از طرفی مجموعهی $\left\{ e,h,g \right\}$، کل رأسهای دیگر را احاطه میکند، پس $\gamma (G)=3$ میشود، پس میتوانیم رأسهای $b,c,d,f$ را با خیال راحت حذف کنیم، اما همچنان مجموعهی $\left\{ e,h,g \right\}$، یک $\gamma $ - مجموعه باشد.