گاما رو نصب کن!

{{ number }}
اعلان ها
اعلان جدیدی وجود ندارد!
کاربر جدید

جستجو

پربازدیدها: #{{ tag.title }}

میتونی لایو بذاری!

در گراف روبه‌رو، کدام مجموعه، احاطه‌گر مینیمال نیست؟

1 ) 

$\left\{ i,j,d \right\}$ 

2 ) 

$\left\{ i,d,b,g \right\}$ 

3 ) 

$\left\{ h,g,j,e \right\}$ 

4 ) 

$\left\{ a,f,d,b \right\}$ 

پاسخ تشریحی :
نمایش پاسخ

کمی جستجو کنید! به نظر می‌رسد با دو رأس، نمی‌توانیم کل رأس‌های دیگر را پوشش دهیم. من می‌گویم بهتر است از قسمت چپ گراف، $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\}$، نیز دو مجموعه‌ی احاطه‌گر مینیمال هستند، زیرا اگر هر کدام از اعضای آن حذف شوند، مجموعه‌های باقی‌مانده، دیگر احاطه‌گر نیستند. 

تحلیل ویدئویی تست

رضا زینی وند