Графи.Что це таке і навіщо вони потрібні?
Одного разу великому математику Леонарда Ейлера було поставлено питання: чи можна обійти всі сім мостів, що стояли тоді в місті Кенігсберзі (сучасний Калінінград, Росія), побувавши на кожному по одному разу? Перед вами план Кенігсберга - можете спробувати!
Розглянувши цю задачу, 1736 року Ейлер довів, що це неможливо, причому він розглянув більш загальну задачу: які місцевості, розділені рукавами річок і з'єднані мостами, можливо обійти, побувавши на кожному мосту рівно один раз, а які неможливо.
Кілька модифікуємо завдання. Кожну з розглянутих місцевостей, розділених річкою, позначимо точкою, а що з'єднують їх мости - відрізком лінії (не обов'язково прямий). Тоді замість плану будемо працювати просто з якоїсь фігурою, складеної з відрізків кривих і прямих. Такі фігури в сучасній математиці називаються графами, відрізки - ребрами, а точки, які з'єднують ребра - вершинами. Тоді вихідна задача еквівалентна наступній: чи можна накреслити даний граф, не відриваючи олівця від паперу, тобто таким чином, щоб кожне його ребро пройти рівно один раз. Такі графи, які можна накреслити, не відриваючи олівця від паперу, називаються унікурсальнимі (від латинського unus cursus - один шлях), або ейлеровимі. Отже, завдання ставиться таким чином: за яких умов граф унікурсален? Ясно, що унікурсальний граф не перестане бути унікурсальним, якщо змінити довжину або форму його ребер, а також змінити розташування вершин - аби не змінювалося з'єднання вершин ребрами (в тому сенсі, що якщо дві вершини з'єднані, вони повинні залишатися з'єднаними, а якщо роз'єднані - то роз'єднаними).
Якщо граф унікурсален, то і топологічно еквівалентний йому граф теж буде унікурсальним. Унікурсальность, таким чином, є топологічним властивістю графа.
По-перше, треба відрізняти зв'язкові графи від незв'язних. Зв'язковими називаються такі фігури, що будь-які дві точки можна з'єднати якимось шляхом, що належить цій фігурі. Наприклад, велика частина букв російського алфавіту зв'язні, але ось буква И - немає: неможливо перейти з її лівої половинки на праве по точкам, що належить цій букві. Можливості підключення - це топологічний властивість: воно не змінюється при перетвореннях фігури без розривів і склеювань. Зрозуміло, що якщо граф унікурсален, то він зобов'язаний бути зв'язковим.
По-друге, розглянемо вершини графа. Будемо називати індексом вершини число ребер, що зустрічаються в цій вершині. Тепер запитаємо себе: чому можуть дорівнювати індекси вершин унікурсального графа.
Тут може бути два випадки: лінія, викреслюють граф, може починатися і закінчуватися в одній і тій же точці (назвемо її «замкнутий шлях»), а може в різних (назвемо її «незамкнений шлях»). Спробуйте самі намалювати такі лінії - з якими хочете самоперетинів - подвійними, потрійними і т. Д. (Для наочності краще, щоб ребер було не більше 15).
Неважко бачити, що в замкнутому шляху все вершини мають парний індекс, а в незамкнутому - рівно дві мають непарний (це початок і кінець шляху). Справа в тому, що, якщо вершина не є початковою або кінцевою, то, прийшовши до неї, треба потім з неї вийти - таким чином, скільки ребер входять в неї, стільки ж виходять з неї, а всього число вхідних і вихідних ребер буде парних . Якщо початкова вершина збігається з кінцевою, то її індекс також четен: скільки ребер з неї вийшло, стільки ж і увійшло. А якщо початкова точка не збігається з кінцевою, то їх індекси непарні: з початкової точки потрібно один раз вийти, а потім, якщо в неї і повернемося, то вийти знову, якщо ще раз повернемося - знову вийти, і т. Д .; а в кінцеву потрібно прийти, а якщо з неї потім і виходимо, то знову потрібно повернутися, і т. д.
Отже, щоб граф був унікурсальним, необхідно, щоб всі його вершини мали парний індекс або щоб число вершин з непарним індексом дорівнювало двом.
Тепер подивіться ще раз на граф завдання про кенігсберзькими мостах.
Порахуйте індекси його вершин і переконайтеся, що він ніяк не може бути унікурсальним. Ось тому-то у вас нічого не виходило, коли ви хотіли обійти всі мости.