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

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

جستجو

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

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

در گراف $G$ از مرتبه‌ی $10$، $\delta =6$ است. کدام گزینه در مورد عددِ احاطه‌گریِ گرافِ مکملِ $G$، درست است؟ (بهترین کران پایین موردنظر است.)

1 ) 

$\gamma (\bar{G})\ge 1$ 

2 ) 

$\gamma (\bar{G})\ge 2$ 

3 ) 

$\gamma (\bar{G})\ge 3$ 

4 ) 

$\gamma (\bar{G})\ge 4$ 

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

مجموع درجه‌ی یک رأس در خود گراف و گراف مکمل، برابر $p-1$ می‌شود. فرض کنیم ${{\deg }_{G}}(a)=\delta =6$ باشد، پس:

$\underbrace{\deg (a)}_{6}+{{\deg }_{{\bar{G}}}}(a)=p-1=9\Rightarrow {{\deg }_{{\bar{G}}}}(a)=3$ 

رأس $a$ در خود گراف، دارای کم‌ترین درجه است، پس در گراف مکمل، بیش‌ترین درجه را دارد، این یعنی $\Delta $ در گراف مکمل، برابر $3$ می‌شود. حالا در گراف $\bar{G}$ داریم:

$\gamma (\bar{G})\ge \left\lceil \frac{n}{\Delta +1} \right\rceil =\left\lceil \frac{10}{3+1} \right\rceil =3$  

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

رضا زینی وند