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

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

ثابت کنید در هر گراف سه منتظم همبند ‎G‎، یک گشت ‎T‎ وجود دارد، به طوری که هر یال ‎G‎ حداقل یک بار در ‎T‎ ظاهر شده است، و تعداد یال‌های درون ‎T‎ حداکثر ‎2(V+Ecut)‎ است. که در آن ‎V‎ تعداد راس‌های گراف ‎G‎ و ‎Ecut‎ تعداد یال‌های برشی گراف ‎G‎ می‌باشد.


ابزار صفحه