سوال ۶
در سؤال قبل فرض کنید یک گراف ۱۶ رأسی داریم که هر رأس آن متناظر با یک رشتهی دودویی ۴ رقمی متمایز است. دو رأس در این گراف به هم یال دارند، اگر و تنها اگر رشتههای متناظر آن رأسها دقیقاً در یک رقم تفاوت داشته باشند. حداقل چند یال به این گراف اضافه کنیم تا فرد زده شود؟
- $1$
- $2$
- $3$
- $4$
- $8$
پاسخ
گزینه (۴) درست است.
هر یال اضافه میتواند دو مثلث ایجاد کند و در نتیجه چهار راس را شامل شود. پس حداقل چهار یال لازم است.
از طرفی با اضافه کردن این چهار یال بین $xx00$ و $xx11$ ها گراف فرد زده میشود.
| ▸ سوال قبل | سوال بعد ◂ |