чки і двох островах. Різні частини міста були з'єднані сім'ю мостами (рис. 20). Можна Чи обійти всі ці мости так, щоб побувати на кожному з них рівно один раз?
Це і є завдання Ейлера про кенігсберзькими мостах , про яку згадувалося на початку параграфа.
Рішення.
Позначимо різні частини міста буквами А, В, С і К і зобразимо їх точками. Мости зобразимо лініями, з'єднують ці точки. Отримаємо граф (рис. 21). p> Завдання зводиться до наступного: чи існує шлях, що проходить по всіх ребрах графа, причому по кожному ребру тільки один раз?
Розглянемо два випадки. p> 1) Припустимо, що існує такий замкнутий шлях. Тоді ступінь кожної вершини графа повинна бути парною, оскільки, входячи в яку-небудь вершину, ми потім повинні з неї вийти, причому по іншому ребру. Що стосується початку шляху, то після виходу з нього ми повинні врешті-решт у нього і повернутися, оскільки шлях замкнутий. Однак на малюнку 20 немає жодної вершини, ступінь якої була б парному. Значить цей випадок неможливий. p> 2) Нехай існує такий незамкнутий шлях; наприклад, нехай він починається у вершині А, а закінчується в С.
Тоді з вершин А і С повинно виходити вже непарне число ребер, а з проміжних вершин В і К - як і раніше парне число. Але на малюнку ступеня вершин В і К непарні. Отже, і цей випадок відпадає.
Відповідь: не можна.
Хоча міркування проведене за вирішенні задачі 3.13, виконано для окремого випадку, воно носить загальний характер:
1) якщо існує замкнутий шлях, проходить по всіх ребрах графа, причому по кожному ребру тільки один раз, то ступеня всіх вершин графа парні ,
2) якщо існує аналогічний незамкнутий путь, то ступеня початку і кінця шляху непарні , а інших вершин - парні.
Ейлер у своїй статті довів і зворотні твердження. Нехай граф зв'язний , тобто будь-які дві його вершини можна пов'язати шляхом, який проходить по його ребрах. Тоді шлях, що проходить по всіх ребрах графа, причому по кожному ребру тільки один раз, існує лише в наступних двох випадках:
1) коли ступінь кожної вершини парна (в цьому випадку шлях замкнутий),
2) коли граф має тільки дві вершини А і В з непарної ступенем (тоді шлях не замкнутий і має своїми кінцями вершини А і В).
3.18. Чи обвести олівцем, не відриваючи його від паперу і не проводячи по одній лінії двічі:
а) квадрат з діагоналями,
б) правильний п'ятикутник з діагоналями?
3.19. Чи з дроту довжиною 12 дм виготовити каркас куба з ребром довжини 1 дм, не ламаючи дріт на частини? p> 3.20. Чи граф, зображений на малюнку 22, обвести олівцем, не відриваючи його від паперу і не проходячи ні одній лінії двічі? Якщо можна, то як? p> 3.21. У точці А розташований гараж для снігоочисної машини (рис. 23). Водієві машини було доручено прибрати сніг з...
