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

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

جستجو

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

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

در گراف روبه‌رو، مجموعه‌ی $\left\{ i,b,h,g,f,c \right\}$، یک مجموعه‌ی احاطه‌گر است. حداکثر چند عضو این مجموعه را می‌توان حذف کرد، به طوری‌که مجموعه به یک مجموعه‌ی احاطه‌گر مینیمال تبدیل شود؟ 

1 ) 

$1$

2 ) 

$2$

3 ) 

$3$

4 ) 

$4$

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

هر مجموعه‌ی احاطه‌گر مینیمم، مینیمال هم هست. مجموعه‌ی احاطه‌گر مینیمم، کم‌ترین تعداد رأس را در بین همه‌ی مجموعه‌های احاطه‌گر دارد. پس اگر بتوانیم با حذف رأس‌ها از مجموعه‌ی داده شده، به یک مجموعه‌ی احاطه‌گر مینیمم برسیم، با یک تیر، دو نشان زده‌ایم؛ هم مینیمال ساخته‌ایم و هم رأس‌های بیشتری را حذف کرده‌ایم. از بین $i$ و $d$ و $e$ حداقل یکی را باید بگیریم، اما رأسی که درجه‌ی بزرگ‌تری دارد و به رأس‌های بیشتری وصل است، رأس $i$ است، پس بهتر است آن‌را انتخاب کنیم. اگر $i$ را داخل مجموعه قرار دهیم، رأس‌های $b$، $d$، $e$ و $h$ را نیز احاطه می‌کند. از میان $g$ و $f$ نیز حتماً باید یک عضو در مجموعه باشد که همدیگر را احاطه کنند. هم‌چنین در مجموعه‌ی $\left\{ i,f \right\}$، $a$ و $c$ احاطه نشده‌اند، باید عضو دیگری به آن اضافه کرد که $a$ و $c$ نیز احاطه شوند. بنابراین برای داشتن یک مجموعه‌ی احاطه‌گر مینیمم، دست‌کم به سه عضو نیاز داریم. حالا مثلاً مجموعه‌ی $\left\{ i,b,f \right\}$، یک $\gamma$ - مجموعه است. به همین خاطر می‌توانیم از مجموعه‌ی $\left\{ i,b,h,g,f,c \right\}$، حداکثر سه عضو $c$، $g$ و $h$ را حذف کنیم تا به یک مجموعه‌ی احاطه‌گر مینیمال برسیم. پس 3 درست است.

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

جابر عامری