یه ترکیبیات

[mimilad]

یک جدول 10 در 10 داریم به طوری که هر خانه ی ان را با رنگی رنگ امیزی میکنیم حداکثر تعداد رنگ های ممکن رابیابید که بتوان خانه های جدول را به گونه ای با ان رنگ کرد که در هر سطر و ستون حداکثر 5 رنگ قرار گیرد ؟

 

[jei javad]

پاسخ : یه ترکیبیات

راهنمایی
یک گراف دو بخشی با بخش های X و Y تعریف کنید که بخش بالایی آن یعنی X مجموعه ی همه ی سطر ها و ستونها است(پس تعداد اعضای آن 20 است) و بخش پایین یعنی Y را مجموعه ی همه ی رنگ های بکار رفته بگیرین(با تعداد اعضای y). فرض کنید رنگ

در جدول در دقیقا

خانه تکرار شده .
از طرفی میدانیم درجه هر راس در X حداکثر 5 است پس کل یالها حداکثر 100 تاست.از طرفی اگر رنگ

در m سطر و n ستون بیاید آنگاه

پس

پس مجموع درجات رووس Y حداقل

همچنین داریم

حالا کافیه این نامساوی رو حل کنید