Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۶:سوال ۶

سوال ۶

در سؤال قبل فرض کنید یک گراف ۱۶ رأسی داریم که هر رأس آن متناظر با یک رشته‌ی دودویی ۴ رقمی متمایز است. دو رأس در این گراف به هم یال دارند، اگر و تنها اگر رشته‌های متناظر آن رأس‌ها دقیقاً در یک رقم تفاوت داشته باشند. حداقل چند یال به این گراف اضافه کنیم تا فرد زده شود؟

  1. 1
  2. 2
  3. 3
  4. 4
  5. 8

پاسخ

گزینه (۴) درست است.

هر یال اضافه می‌تواند دو مثلث ایجاد کند و در نتیجه چهار راس را شامل شود. پس حداقل چهار یال لازم است.

از طرفی با اضافه کردن این چهار یال بین xx00 و xx11 ها گراف فرد‌ زده می‌شود.


ابزار صفحه