Маршруты, цепи, циклы

1.1. Маршруты, цепи, циклы

1.1.1. Определения

Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер v₁, e₁, v₂, e₂, ... ,v_k ,e_k,v_k+1, в которой любые два соседних элемента инцидентны.

Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер.

Если v₁=v_k+1, то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью. Если все вершины цепи различны, то цепь называется простой.

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом.

Число циклов в графе G обозначается z(G) (является инвариантом). Граф без циклов называется ациклическим.

Для орграфов цепь называется путем, а цикл - контуром.

Рекомендуемые материалы

Пример

В графе, диаграмма которого приведена на рис. 3.10:

1. v₁,v₃,v₁,v₄ - маршрут, но не цепь;

2. v₁, v₃, v₅, v₂, v₃, v₄ - цепь, но не простая цепь;

3. v₁, v₄, v₃, v₂, v₅ - простая цепь;

4. v₁, v₃, v₅, v₂, v₃, v₄, v₁- цикл, но не простой цикл;

5. v₁,v₃,v₄ - простой цикл.

Рис. 3.10. Маршруты, цепи, циклы

Две вершины графа называются связанными, если существует маршрут, соединяющий эти вершины. Граф называется связным, если любая пара его вершин связанна.

Граф называется деревом, если он связен и не содержит циклов.

1.1.2. Эйлеровы графы

Вернемся к историческому  примеру о Кенигсбергских мостах. В каком случае в графе можно найти цикл, в котором каждое ребро участвует ровно один раз?

Цикл, содержащий каждое ребро ровно один раз, называется эйлеровым. Граф, содержащий эйлеровый цикл, называется эйлеровым графом.

Теорема (критерий эйлеровости графа): конечный граф G(V,E) является эйлеровым, тогда и только тогда, когда он связен и степени всех его вершин – четны.

Цепь, содержащая каждое ребро ровно один раз, называется эйлеровой. Граф, содержащий эйлерову цепь, называется полуэйлеровым графом.

Теорема (критерий полуйлеровости графа): конечный граф G(V,E) является полуэйлеровым, тогда и только тогда, когда он связен и точно две го вершины имеют нечетную степень.

1.1.3. Гамильтоновы графы

Кроме эйлеровых графов рассматриваются также гамильтоновы графы.

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

Этот граф представляет собой укладку додекаэдра.

Рис. 3.11. Задача «Кругосветное путешествие»

Если граф имеет простой цикл, содержащий все вершины графа (по одному ра­зу), то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом.

Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамиль­тоновым может быть только связный граф.

Теорема (Дирак). Если в графе G(V, E) для любой вершины v выполняется: (v) р/2, то граф G является гамильтоновым.

Рассмотрим следующую задачу, известную как задача коммивояжера. Имеется р городов, расстояния между которыми известны. Коммивояжер должен посетить все р городов по одному разу, вернувшись в тот, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным.

Очевидно, что задача коммивояжера - это задача отыскания кратчайшего гамильтонова цикла в полном графе.

Можно предложить следующую простую схему решения задачи коммивояжера: сгенерировать все р! возможных перестановок вершин полного графа, подсчи­тать для каждой перестановки длину маршрута и выбрать из них кратчайший. Очевидно, такое вычисление потребует огромного количества шагов.

Как известно, р! с ростом р растет быстрее, чем любой полином от р, и даже быстрее, чем 2^Р. Таким образом, решение задачи коммивояжера описанным методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших р.

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

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

Уже давно Эйлером получено просто проверяемое необходимое и достаточное условие существования в графе эйлерова цикла. Что касается гамильтоновых графов, то для них не известно необходимых и достаточных условий. На основе необходимого и досточного условия существования эйлерова цикла можно построить эффективные алгорит­мы отыскания такого цикла.

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

Теорема: Эйлеровых графов почти нет (E(p) – число эйлеровых графов с p вершинами, G(p) – число всех графов с p вершинами):

.

С другой стороны, можно показать, что почти все графы гамильтоновы.

Теорема: (H(p) – число гамильтоновых графов с p вершинами, G(p) – число всех графов с p вершинами):

.

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

Заключение

Обратите внимание на лекцию "3.2 Отсечение выпуклым многоугольным окном".

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

В информатике графы используются в следующих разделах:

- операционные системы;

- алгоритмизация;

- структуры данных;

- моделирование и др.