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

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:گراف:سوال ۴

سوال ۴

گراف ‎n‎ راسی ‎G‎ را در نظر بگیرید. به ازای هر راس ‎G‎ مانند ‎v‎، گراف ‎Gv‎ در حد یکریختی و بدون نامگذاری رئوس داده شده است. ثابت کنید:

  • وجود دور زوج در گراف ‎G‎ را با استفاده از این ‎n‎ گراف داده شده می‌توان فهمید‎.
  • ثابت کنید اگر ‎G‎ دو بخشی باشد با استفاده از این ‎n‎ گراف، می‌توانیم تشخیص دهیم تطابق کامل دارد یا خیر.

ابزار صفحه