شرکت در آزمون آنلاین ریاضیات گسسته - فصل دوم: گراف و مدل سازی | آزمون شماره 417

مجموعة A، يك مجموعة احاطه‌گر مينيمال براي گراف زير است. اين مجموعه حداكثر چند عضو مي‌تواند داشته باشد؟

در گرافی با درجه رئوس $۳,۳,۲,۲$ کوچک ترین مجموعه احاطه گر چند عضو دارد و چند مجموعه احاطه گر با این تعداد اعضا داریم؟(از راست به چپ)

در گراف $G$ با مجموعه رأس‌های $\text{V}=\left\{ \text{a }\!\!~\!\!\text{ },\text{ }\!\!~\!\!\text{ b},\text{ }\!\!~\!\!\text{ c},\text{ }\!\!~\!\!\text{ d},\text{ }\!\!~\!\!\text{ e},\text{f} \right\}$ شرایط زیر برقرار است:

$\begin{cases} {{\text{N}}_{\text{G}}}\left( \text{d} \right)=\left\{ \text{b},\text{e,f} \right\}\\\!\text{ }\!\!~\!\!\text{ }{{\text{N}}_{\text{G}}}\left( \text{f} \right)=\left\{ \text{d} \right\}\\\text{ }\!\!~\!\!\text{ }\!\!~\!\!\text{ }{{\text{N}}_{\text{G}}}\left( \text{a} \right)=\left\{ \text{b},\text{c},\text{e} \right\}\\\text{ }\!\!~\!\!\text{ }\!\!~\!\!\text{ }{{\text{N}}_{\text{G}}}\left[ \text{b} \right]=\left\{ \text{b},\text{d},\text{a} \right\} \\\deg(e)=۲\\\deg(c)=۱\end{cases}$

​​​​​​کدام گزینه زیرگرافی از $G$ نیست؟

در یک جمع $۱۱$ نفره، هر نفر دقیقاً $k$ نفر دیگر را می‌شناسد. اگر بدانیم حداقل دو نفر وجود دارند که همدیگر را می‌شناسند و دو نفر نیز وجود دارند که همدیگر را نمی‌شناسند، $k$ چند مقدار مختلف ممکن است داشته باشد؟

در گراف ۷ رأسی $-k$منتظم و غیر تهی، حداقل دو رأس برای احاطه تمام رأس‌ها مورد نیاز است. چند مقدار ممکن برای $k$ وجود دارد؟