المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

فرض کنید ‎$n$‎ یک عدد طبیعی فرد باشد. ‎۲‎ مربع لاتین متعامد (عمود بر هم) از مرتبه‌ی ‎$n$‎ مثال بزنید. ‎‎ فرض کنید ‎$n$‎ یک عدد طبیعی باشد. گراف ‎$K_{n‎, ‎n}$‎ را در نظر بگیرید. یک رنگ‌آمیزی یالی معتبر از آن را، ‎رنگارنگ‎ می‌گوییم اگر بتوان یال‌های گراف را به ‎$n$‎ تطابق کامل افراز کرد؛ طوری که هر تطابق از هر رنگ، دقیقن یک یال داشته باشد. ثابت کنید به ازای هر عدد طبیعی فرد ‎$n$‎، گراف ‎$K_{n‎, ‎n}$‎ یک رنگ‌آمیزی یالی معتبر با ‎$n$‎ رنگ دارد که رنگارنگ باشد.


ابزار صفحه