Ноу Інти, лекція, паросполучення і весілля

Паросполучення і весілля

Результати цієї глави носять більш комбінаторний характер, ніж результати всіх попередніх розділів, хоча вони тісно пов'язані з теорією графів. Обговоримо добре відому "теорему про весіллях", що належить Філіпу Холу, і деякі додатки цієї теореми, наприклад, побудова латинських квадратів.

Теорема Холла про весіллях

Теорема про весіллях, доведена Філіпом Холом в 1935 р відповідає на наступне питання, відомий під назвою завдання про весіллях. розглянемо деякий кінцеве безліч юнаків, кожен з яких знайомий з кількома дівчатами; питається, за яких умов можна одружити юнаків так, щоб кожен з них одружився на знайомій йому дівчині. (Будемо вважати, що полігамія не дозволена.) Наприклад, якщо є четверо юнаків і п'ятеро дівчат, а відносини знайомства між ними показані в таблиці 1, то можливо таке рішення: одружується на, - на, -, а - на.

Дівчата, з якими знайомий юнак