>)-маршрутом. Маршрут замкнутий, якщо v 0 = v n , і відкритий в іншому випадку. Маршрут називається ланцюгом, якщо всі його ребра різні, і простий ланцюгом, якщо всі вершини (а отже, і ребра) різні. Замкнута ланцюг називається циклом. Замкнуте маршрут називається простим циклом, якщо всі його n вершин різні і n Ві 3.
Граф G називається зв'язковим, якщо будь-яка пара його вершин з'єднана простий ланцюгом. [6]
Задача про кенігсберзькими мостах.
Отцем теорії графів є Ейлер (1707-1782), який вирішив в 1736г. широко відому в той час завдання, яка звалася проблемою Кенигсбергских мостів. У місті Кенігсберзі (нині Калінінград) було два острови, з'єднаних сім'ю мостами з берегами річки Преголя і один з одним так, як показано на малюнку 5. Завдання полягало в наступному: знайти маршрут проходження всіх чотирьох частин суші, який починався б з будь-якої з них, кінчався б на цій же частині і рівно один раз проходив по кожному мосту.
В
В В
Рис.5.
Легко, звичайно спробувати вирішити цю задачу емпірично, виробляючи перебір всіх маршрутів, але всі спроби закінчаться невдачею. Винятковий внесок Ейлера у вирішення цього завдання полягає в тому, що він довів неможливість такого маршруту.
Для доказу того, що завдання не має рішення, Ейлер позначив кожну частину суші точкою (вершиною), а кожен міст - лінією (ребром), що з'єднує відповідні точки. Вийшов "Граф". Цей граф зображений на малюнку 6, де точки відзначені тими ж буквами, що і чотири частини суші на малюнку 5. <В
Рис.6. p> Твердження про не існування "Позитивного" рішення у цієї задачі еквівалентно твердженням про неможливість обійти спеціальним чином граф, представлений на малюнку 6.
Вирушаючи від цього приватного випадку Ейлер узагальнив постановку завдання і знайшов критерій існування обходу у даного графа, а саме граф повинен бути зв'язковим і кожна його вершина має бути інцидентна парним числом ребер. [6]
Ейлерови графи
Рішення Ейлером задачі про Кенигсбергских мостах призвела до першої опублікованій роботі з теорії графів. Задачу про обхід мостів можна узагальнити і отримати таку завдання теорії графів: чи можна знайти в даному графі G цикл, що містить всі вершини і всі ребра? Граф, у якому це можливо, називається ейлеровим. Таким чином, Ейлером граф має Ейлером цикл - замкнутий ланцюг, що містить всі вершини і всі ребра. Ясно, що Ейлером граф повинен бути зв'язковим. [6]
Якщо зняти обмеження на замкнутість ланцюга, то граф називається полуейлеровим.
В
Теорема 1 (критерій):
Граф з більш ніж однією вершиною має Ейлером цикл тоді і тільки тоді, коли він зв'язний і кожна його вершина має парну ступінь.
Доказ: Припустимо, ...
