![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 17. Свойства и типы графов. положило появление в печати работы Эйлера, посвященной решению этой проблемы, известная как задача о Кенигсбергских мостах (см
Эти задачи будоражили воображение энтузиастов. Их рассматривают как головоломки, по условиям которых вы должны вычертить заданную фигуру, не отрывая карандаша от бумаги, возможно, при условии, что вы должны начать и вернуться в заданную точку. Перед нами встает естественная задача поиска эйлеровых путей при разработке алгоритмов обработки графов, поскольку эйлеровы пути является эффективным представлением графов (упорядочение ребер графа определенным образом), которые могут служить основой разработки эффективных алгоритмов. Эйлер нашел легкий способ определить, существует ли такая цепь, для этого достаточно определить степень каждой вершины. Это свойство нетрудно сформулировать и применять, однако его доказательство в теории графов требует немалой изобретательности. Свойство 17.4. Граф содержит эйлеров цикл тогда и только тогда, когда он связный и все его вершины имеют четную степень. Доказательство: Чтобы упростить доказательство, допустим существование петель и параллельных ребер, хотя совсем нетрудно изменить доказательство таким образом, чтобы показать, что это свойство справедливо и для простых графов (см. упражнение 17.94). Если в графе имеется эйлеров цикл, то он должен быть связным в силу того, что цикл определяет путь, соединяет каждую пару вершин. Кроме того, степень любой заданной вершины графа v должна быть четной, поскольку, когда мы проходим цикл (начало которого находится в какой-то другой вершине), то мы входим в вершину v через одно ребро и выходим из нее через другое ребро (ни то, ни другое больше в цикл не входят); следовательно, число ребер, инцидентных вершине v, должно быть равно удвоенному числу наших посещений вершины v при прохождении эйлерова цикла, т.е. должно быть равно четному числу. Чтобы доказать достаточность, воспользуемся методом индукции по количеству ребер. Это утверждение заведомо выполняется для графов, у которых нет ребер. Рассмотрим любой связный граф, в котором содержится более одного ребра, при этом степени всех вершин четные. Предположим, что начиная с произвольной вершины, мы продвигаемся по любому ребру, после чего его удаляем. Мы продолжаем этот процесс до тех пор, пока не окажемся в вершине, у которой нет ребер. Этот процесс должен когда-нибудь завершиться, поскольку мы удаляем по одному ребру на каждом шаге, однако каким может стать результат этой процедуры? На рис. 17.22 приводятся примеры. Нам сразу становится ясно, что этот процесс должен закончиться на вершине v тогда и только тогда, когда ее степенью было число нечетное в момент, когда этот процесс начинался. Одна из возможностей состоит в том, что мы пройдем по всему циклу; если это так, то доказательство завершено. В противном случае, все вершины графа, который при этом остался, имеют четные степени, но тогда граф может оказаться несвязным. Однако в соответствии с индуктивным предположением, каждая его связная компонен- Часть 5. Алгоритмы на графах
пени (на концах пути). ■ Отсюда следует, например, что никто не может пройти через все мосты Кенигсберга так, чтобы не пройти по одному мосту дважды, поскольку в соответствующем графе все четыре составляющие его вершины обладают нечетными степенями (см. рис. 17.21). В соответствии с изложенным в разделе 17.5, мы можем найти все степени вершин за время, пропорциональное E для представления графа в виде списков смежных вершин или в виде множества ребер, либо за время, пропорциональное V2 для представления графа в виде матрицы смежности, либо мы можем поддерживать вектор, индексированный именами вершин, в котором степени вершин являются частью представления графа (см. упражнение 17.42). При наличии такого вектора мы можем проверить, выполняется ли свойство 17.4 за время, пропорциональное V. Программа 17.18 реализует эту стратегию и показывает, что проверка заданного графа на наличие в нем эйлеровою цикла представляет собой достаточно простую вычислительную задачу. Этот факт важен в силу того, что до сих пор мы не были уверены в том, что эта задача проще, чем определение гамильтонова пути в заданном графе. Теперь предположим, что мы и в самом деле хотим найти эйлеров цикл. Мы идем по тонкому льду, поскольку прямая рекурсивная реализация (поиск пути за счет проверки ребра, после которой выполняется рекурсивный вызов с целью определения пути в остальной части графа) обеспечивает ту же производительность, пропорциональную факториалу числа вершин, что и программа 17.17. Мы не можем смириться с такой производительностью, по- РИСУНОК 17.21. МОСТЫ КЕНИГСБЕРГА Широко известная задача, изучавшаяся еще Эйлером, связана с городом Кенигсберг, в котором в устье реки Лреголь расположены острова, соединенные с берегами семью мостами. Существует ли путь, который позволяет во время непрерывной прогулки по городу, обойти все семь мостов и ни на одном из них не побывать дважды? Если мы обозначим остров через 0, берега реки через 1 и 2 еще один остров через 3, а также определим ребра, соответствующие каждому мосту, мы получим мультиграф, показанный в нижней части рисунка. Суть задачи заключается в том, чтобы найти такой путь, который использует каждое ребро в точности один раз. Глава 17. Свойства и типы графов
Другой подход вытекает из доказательства свойства 17.4. Проследуем по циклическому пути, стирая все ребра и помещая в стек все вершины, которые нам встретятся, так что (i) мы можем проследить свой путь, распечатав его ребра, и (ii) проверить каждую вершину на наличие боковых путей (который может быть включен в главный путь). Этот процесс иллюстрируется рисунком 17.23. Сначала программа добавляет в искомый цикл ребро 0-1 и удаляет его из списков смежных вершин (из двух мест) (диаграмма в верхнем левом углу, списки слева от диаграммы). Затем она добавляет ребро 1-2 в искомый цикл тем же способом (диаграмма слева, вторая сверху). Далее, она поворачивает назад в 0, но при этом продолжает строить цикл 0-5-4-6-0, возвращаясь в вершину 0, при этом ребер, инцидентных вершине 0, не остается (справа, вторая диаграмм сверху). Затем она выталкивает из стека изолированные вершины 0 и 6, так что вверху стека остается вершина 4, и начинает цикл с вершины 4 (справа, третья диаграмма сверху), проходит через вершины 3, 2 и возвращается в 4, вследствие чего из стека выталкиваются все теперь уже изолированные вершины 4, 2, 3 и т.д. Последовательность вершин, вытолкнутых из стека, определяет эйлеров цикл 0-6-4-2-3-4-5-0-2-1-0 для всего графа. Программа 17.19 представляет собой реализацию изложенного в этих строках. Она предполагает, что эйлеров цикл существует, при этом она уничтожает локальную копию графа; таким образом, важно, чтобы в класс Graph, который использует рассматриваемая программа, входил конструктор копирования, который создает полностью автономную копию графа. Программный код достаточно сложен, новичкам полезно освоить алгоритмы обработки графов, рассмотренные в нескольких следующих главах, прежде чем предпринимать попытку разобраться в нем. Мы включили ее в этот раздел с тем, чтобы показать, что хорошие алгоритмы и умелая их реализация позволяют исключительно эффективно решать некоторые задачи обработки графов. РИСУНОК 17.22. ЧАСТИЧНЫЕ ЦИКЛЫ Путь вдоль ребер, начинающийся в любой из вершин графа, в котором имеется эйлеров цикл, всегда приводит нас в ту же вершину, как показано в находящихся на рисунке примерах. Цикл не обязательно проходит через все ребра в графе. Часть 5. Алгоритмы на графах
РИСУНОК 17.23. ПОИСК ЭЙЛЕРОВА ПУТИ МЕТОДОМ УДАЛЕНИЯ ЦИКЛОВ Этот рисунок служит иллюстрацией того, как программа 17.19 находит эйлеров цикл из вершины О в вершину 0 на простом графе. В этот цикл входят жирные черные ребра, содержимое стека показано под каждой диаграммой, список смежных вершин, не входящих в искомый цикл, находится слева от диаграммы, а списки смежных вершин ребер, не попавших в цикл, показаны слева от каждой диаграммы.
|