Информатика · объяснение и практика

Почему путь через все вершины не равен пути через все рёбра

Сравните обход вершин и обход рёбер на двух небольших графах: выясните, почему знакомая проверка чётности не решает гамильтонову задачу.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

Главная мысль

Гамильтонов путь посещает каждую вершину ровно один раз. Эйлеров маршрут использует каждое ребро ровно один раз и разрешает повторные вершины. В условии нужно найти, какие объекты перечисляются без повторений: комнаты или проходы, пункты или связи между ними.

Одна картинка может задавать две разные задачи

В графе полного соединения четырёх вершин А, Б, В и Г есть ребро между каждой парой. Последовательность А, Б, В, Г посещает все вершины по одному разу: это гамильтонов путь. Он использовал только три из шести рёбер. Поэтому такая запись не является ответом на требование пройти каждую связь.

У каждой вершины этого графа степень три. Четыре нечётные степени исключают эйлеров маршрут, хотя гамильтонов путь мы уже построили. Этот пример сразу опровергает перенос критерия нечётных степеней на другую задачу. Совпадение слов «путь» и «обход» в переводе не делает требования одинаковыми.

Обратный пример: все рёбра доступны, а вершину придётся повторить

Пусть три треугольника имеют ровно одну общую вершину О и не имеют других общих точек. У О степень шесть, у остальных шести вершин — по два. Граф связен, поэтому эйлеров цикл существует: можно последовательно обойти все три треугольника, возвращаясь в О. Общая вершина встретится несколько раз, что для этой задачи допустимо.

Гамильтонова пути через все семь вершин нет. Удаление О оставляет три отдельные пары вершин. Простой путь, проходящий через О лишь один раз, может связать не более двух таких частей: одну до О, другую после неё. Для третьей потребовалось бы повторное посещение О. Важно именно число отдельных частей, а не только наличие общей вершины.

Пример

Для двух треугольников с общей О рассмотрите порядок А, Б, О, В, Г, где А—Б—О—А и О—В—Г—О — треугольники. Является ли он гамильтоновым?

Да: все пять вершин различны, и каждую соседнюю пару соединяет ребро. Поэтому утверждение об отсутствии гамильтонова пути здесь было бы ошибочным. Отсутствует гамильтонов цикл: после удаления О граф распадается на две части, которые один цикл без повторения О связать не может.

Различайте путь и цикл даже внутри одной темы

Гамильтонов цикл дополнительно возвращается к началу, не повторяя других вершин. Это сильнее существования гамильтонова пути. Для наглядного примера без пути можно взять звезду с тремя листьями: посещение трёх тупиков потребовало бы три конца, а у пути их только два. Такой граф отличается от двух соединённых через О треугольников.

Для проверки предложенного гамильтонова пути достаточно проверить набор вершин, отсутствие повторений и каждое соседнее ребро. Поиск пути в произвольном большом графе значительно сложнее такой проверки готового ответа. Эйлеров критерий решает другую задачу и не служит универсальным быстрым тестом. Начинайте с точной формулировки, а найденный маленький маршрут используйте как проверяемое свидетельство существования.

От чтения к действию

А теперь — вы

В графе только четыре вершины П, Р, С, Т и рёбра П—Р, Р—С, С—П, П—Т. Дана последовательность Р, С, П, Т. Что она выполняет?

Частые вопросы

Если путь посещает все вершины, он обязательно использует все рёбра?

Нет. В графе могут оставаться связи, по которым путь не проходил. Гамильтоново требование относится к вершинам.

Наличие гамильтонова пути означает наличие цикла?

Нет. Для цикла требуется дополнительное замыкание без повторных промежуточных вершин; путь может существовать без такого замыкания.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться