2, а3, ..., А23. Цей перехід також можна замінити двадцятьма трьома транспозиція.
Таким чином, будь-який обгін зводиться до непарному числу транспозицій. Якщо б загальне число обгонів було непарним, то непарних виявилося б і загальне число транспозицій. Залишається скористатися результатом завдання 2.16. br/>
3. Графи
Графом на площині називається кінцеве безліч точок площини, деякі з яких з'єднані лініями. Ці точки називаються вершинами графа, а що з'єднують їх лінії - ребрами. Число ребер, що виходять з вершини графа, називається ступенем цієї вершини. p> З графами ми зустрічаємося частіше, ніж це, можливо, здається на перший погляд. Прикладами графа може служити будь-яка карта доріг, електросхема, креслення багатокутника і т. д.
Теорія графів виникла в 1736 р., коли Леонард Ейлер опублікував першу статтю про графах. Починалася вона з розбору широко відомої тепер задачі про кенігсберзькими мостах. Довгий час вважалося, що теорія графів застосовується головним чином для вирішення логічних завдань, а сама теорія розглядалася як частина геометрії. Проте в ХХ столітті були знайдені широкі застосування теорії графів в економіці, біології, хімії, електроніці, мережевому плануванні, комбінаторики й інших галузях науки і техніки. У результаті вона стала бурхливо розвиватися і перетворилася в самостійну розгалужену теорію.
Завдання на відповідність між множинами.
3.1. У п'яти корзинах А, Б, В, Г і Д лежать яблука п'яти різних сортів. У кожній з кошиків А і Б знаходяться яблука 3-го і 4-го сорту, у кошику В - 2-го і 3-го, в кошику Г - 4-го та 5-го, в кошику Д - 1-го та 5-го. Занумеруйте корзини так, щоб у кошику № 1 були яблука 1-го сорту (щонайменше одне), в кошику № 2 - яблука 2-го сорту і т. Д
Рішення.
Зобразимо два безлічі безліч кошиків та безліч їх номерів. У кожному з цих множин по п'ять елементів позначимо їх точками
Встановимо відповідність між цими двома множинами так, щоб умови завдання виконувалися. Будемо відповідні елементи двох множин з'єднувати суцільними лініями, а не відповідні - пунктирними або зовсім не з'єднувати. Так як яблука першого сорту лежать тільки в кошику Д, то саме цьому кошику і потрібно дати номер 1; проведемо суцільну лінію між точками Д і 1. Далі номер 2 можна присвоїти тільки кошику В, а після цього номер 5 - лише кошику Г. Нарешті, номери 3 і 4 дамо кошиках А і Б (в будь-якому порядку). p> Відповідь: кошики розташувалися, починаючи з № 1, в послідовному порядку Д, В, А, Б, Г або в порядку Д, В, Б, А, Г.
3.2. Петро, ​​Геннадій, Олексій і Володимир займаються в одній дитячій спортивній школі в різних секціях: гімнастики, легкої атлетики, волейболу та баскетболу. Петро, ​​Олексій і волейболіст навчаються в одному класі. Петро і Геннадій на тренування ходять пішки разом, а гімнаст їздить на автобусі. Ле...
