Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Обходы графов

Задача о кенигсбергских мостах, которую мы уже упоминали во введении, не только знаменует начало разработки теории графов, но и определяет одно из важных для приложений направлений этой теории, связанное с задачами отыскания способов обхода (специальных маршрутов) в графе.

Сформулируем задачу о кенигсбергских мостах. В городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рис. 32. Нужно было найти маршрут прохождения всех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.

Рис. 32

В 1736 г. Эйлер доказал невозможность такого маршрута, Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост - линией (ребром), соединяющей соответствующие точки. Получился «граф» (точнее, согласно нашим определениям, «мультиграф»), изображенный на рис. 33. При этом обходу мостов соответствует последовательность ребер графа, в которой два ребра имеют общую вершину, т. е. маршрут. Так как в конце обхода нужно вернуться в исходную часть города и на каждом мосту нужно побывать только один раз, этот маршрут является циклом, содержащим все ребра графа.

Рис. 33

Задачу об обходе мостов Эйлер обобщил и получил следующую проблему теории графов: можно ли в данном графе G найти цикл, содержащий все вершины и все ребра графа? В дальнейшем такие циклы получили название эйлеровых циклов, а графы, обладающие указанными циклами, - эйлеровыми графами. Таким образом, эйлеров граф можно изобразить одним росчерком пера, не отрываясь от бумаги, причем процесс вычерчивания начинается и кончается в одной и той же точке. Ясно, что эйлеров граф должен быть связным. Эйлер нашел критерий существования в графе эйлерова цикла.

Теорема 4.13. Конечный граф является эйлеровым тогда и только тогда, когда он связен и степени всех его вершин четны.

Доказательство этой теоремы можно найти, например, в [16] глава 7.

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

Кроме эйлеровых циклов рассматривают эйлеровы цепи, т. е. такие цепи, которые содержат все ребра конечного графа, но имеют различные начало v и конец w.

Теорема 4.14. Для того чтобы связный граф обладал эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени.

Алгоритм выделения эйлеровой цепи или эйлерова цикла в графе, реализуемый на ЭВМ, можно найти в [7] §4.2.7.

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

С задачей коммивояжера тесно связаны понятия гамильтонова цикла и гамильтонова графа. Гамильтоновым циклом в графе G называется такой цикл, который проходит через каждую вершину графа точно один раз. Граф G называется гамильтоновым графом, если в нем имеется гамильтонов цикл. Кроме того, можно определить и гамильтонову цепь.

Заметим, что (как и в случае эйлеровых графов) было бы полезно иметь сравнительно простые необходимые и достаточные условия существования гамильтоновых цепей и циклов. Однако этот вопрос является весьма сложным.

Приведем некоторые сведения о гамильтоновых графах. Очевидно, что граф, в котором каждая вершина является смежной со всеми остальными вершинами (он называется полным, графом,), обладает гамильтоновыми циклами и цепями. Условие полноты графа можно рассматривать как простейшее достаточное условие того, что граф является гамильтоновым. В полном (п. т)-графе G каждая вершина v имеет наибольшую степень S(v)=n — 1, а число ребер максимально при заданном числе вершин: т = п(п — 1). Более тонкие взаимосвязи между степенями вершин графа и свойством гамильтоновости содержатся в следующих достаточных условиях.

Теорема 4.15. Если в (п,ш)-графе G п^З и степени вершин удовлетворяют неравенству 6(v)+6(w)^n для любой пары v и w несмежных вершин, то G - гамильтонов граф.

Теорема 4.16. Если в (п.т)-графе G п>3 и степень любой Вер-

72

шины v удовлетворяет неравенству , то G - гамильтонов граф.

Доказательства этих теорем приведены в [i6| глава 7.

Очевидным необходимым условием существования гамильтоновых цепей и циклов в графе G является его связность. А более тонкое необходимое условие гамильтоиовости графа содержится в следующей теореме ([7] §4.2.8).

Теорема 4.17. Если граф G обладает гамильтоновым циклом, то в нем отсутствуют точки сочленения.

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

На рис. 34 изображен гамильтонов граф, который согласно теореме 4.13 не является эйлеровым, а на рис. 35 - эйлеров, но не гамильтонов граф (см. теорему 4.17). Граф, который представлен на рис. 36, одновременно является и эйлеровым, и гамильтоновым.

Рис. 34

Рис. 35

Рис. 36

Простым способом выделения гамильтоновых цепей в графе является метод перебора всевозможных перестановок множества вершин V = {^1,^2? • • •, vn} графа G. Для каждой перестановки проверяем, является ли она маршрутом. Если да, то это означает, что найдена гамильтонова цепь, в противном случае переходим к следующей перестановке. После окончания перебора будут выделены все гамильтоновы цепи в графе G. Аналогично для выделения всех гамильтоновых циклов перебираем все возможные перестановки вида гц, гщ, .... щп_1 множества вершин V, для каждой из которых проверяем, является ли гд, гщ, .... Vin-1, гд маршрутом в G. Очевидно, что при выделении всех гамильтоновых цепей придется перебирать п перестановок, а при выделении всех гамильтоновых циклов - (п — 1)! перестановок.

Описанный выше метод не учитывает информации об исследуемом графе G. Рассмотрим метод, аналогичный предыдущему, но использующий информацию о графе G. Составим всевозможные последовательности вершин г>ц, V{k, где щ2 G (ДщД {щД,

Vi3eG(vi2){vil,vi2}, •••,vikeG(vik_1){vi1,...,Vik_1}, до тех пор, пока не получим G(vik){vi1, ...,^fc} = 0. Тогда в каждом случае, когда к = п, последовательность гд, щп есть гамильтонова цепь в графе G7 Соответственно, когда к = п и гд ? G(vn), последовательность ... v%n - гамильтонов цикл графа G. Через G(v) обозначено множество всех вершин графа G=(V,E), инцидентных вершине v, т. е. G(v) = {wweV и (vpw) G Е}. Число переборов при использовании второго метода в общем случае меньше, чем для первого.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>