Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

1. Стираем ребра по мере их прохождения (вместе с изолированными вершинами, которые при этом образуются);

2. На каждом шаге идем по мосту только в том случае, когда нет других возможностей.

Доказательство.

Убедимся сначала, что указанная процедура может быть выполнена на каждом этапе. Пусть мы достигли некоторой вершины v, начав с вершины u, v ≠ u. Удалив ребра пути из v в u, видим, что оставшийся граф G₁ связен и содержит ровно две нечетных вершины v и u. Согласно следствию #2 из теоремы 1 граф G₁ имеет эйлеров путь P из v в u. Поскольку удаление первого ребра инцидентного u пути P либо не нарушает связности G₁, либо происходит удаление вершины u и оставшийся граф G₂ связен с двумя нечетными вершинами, то отсюда получаем, что описанное выше построение всегда возможно на каждом шаге. (Если v = u, то доказательство не меняется, если имеются ребра, инцидентные u). Покажем, что данная процедура приводит к эйлерову пути. Действительно, в G не может быть ребер, оставшихся не пройденными после использования последнего ребра, инцидентного u, поскольку в противном случае удаление ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию 2).

§4. Некоторые родственные задачи

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

1. Каково наименьшее число цепей или циклов необходимое для того, чтобы каждое ребро графа G содержалось точно в одной цепи или в одном цикле? Очевидно, что если G имеет эйлеров цикл или эйлерову цепь, то ответом будет число один.

2. Р
   ебрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин n_jc(a_j), где число n_j показывает, сколько раз проходилось ребро a_j, а c(a_j) — вес ребра) минимален. Очевидно, что если G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится по один раз и вес этого цикла равен тогда

Сформулированная выше задача 2) называется задачей китайского почтальона, и ее решение имеет много потенциальных приложений, как например:

1. Сбор мусора. Рассмотрим проблему сбора домашнего мусора. Допустим, что определенный район города обслуживается единственной машиной. Ребра графа G представляют дороги, а вершины — пересечения дорог. Величина c(a_j) — вес ребра — будет соответствовать длине дороги. Тогда проблема сбора мусора в данном районе сводится к нахождению цикла в графе G, проходящего по каждому ребру G по крайней мере один раз. Требуется найти цикл с наименьшим километражем.

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

3. Проверка электрических, телефонных или железнодорожных линий. Проблема инспектирования распределенных систем (лишь некоторые из которых названы выше) связана с непременным требованием проверки всех «компонент». Поэтому она также является проблемой типа 2) или близка к ней.

§5. Задача китайского почтальона

Р
ассмотрим неориентированный граф G(X,A). Среди вершин из X некоторые вершины (скажем из множества X⁺) будут иметь четные степени, а остальные (из множества X^-=X\X⁺) — нечетные степени. Сумма степеней d_i всех вершин x_i X равна удвоенному числу ребер в A (т.к. каждое ребро добавляет по единице к степеням двух его концевых вершин) и поэтому равна четному числу 2m. Следовательно, и так как первая сумма четна, то вторая сумма также четна. Но все d_i в последней сумме нечетны, значит число |X^-| вершин нечетной степени четно.

Пусть M — множество таких цепей (скажем μ_ij) в G между концевыми вершинами x_i и x_j X^-, что никакие две цепи не имеют одинаковых конечных вершин, т.е. цепи соединяют различные пары вершин из X^- и покрывают все вершины множества X^-. Число цепей μ_ij в M равно 1/2|X^-| и всегда цело, если конечно оно определено. Предположим теперь, что все ребра, образующие цепь μ_ij, теперь удвоены (добавлены искусственные ребра). Так поступаем с каждой цепью μ_ij M и полученный граф обозначим через G^-(M). Так как некоторые ребра из G могут входить более чем в одну цепь μ_ij, то некоторые ребра из G^-(M) могут быть (после того как добавлены все «новые» цепи μ_ij) утроены, учетверены и т.д.

Теорема 3. Для любого цикла, проходящего по G, можно выбрать множество M, для которого граф G^-(M) имеет эйлеров цикл, соответствующий первоначально взятому циклу в графе G. Это соответствие таково, что если цикл проходит по ребру (x_i, x_j) из G l раз, то в G^-(M) существует l ребер (одно реальное и l-1 искусственных) между x_i и x_j, каждое из которых проходится ровно один раз эйлеровым циклом из G^-(M). Справедливо и обратное утверждение.

Доказательство.

Если цикл проходит по графу G, то по крайней мере одно ребро, инцидентное каждой вершине x_i нечетной степени, должно проходиться дважды. (Ребро, проходимое дважды, можно рассматривать как два параллельных ребра — одно реальное и одно искусственное — и каждое из них проходится один раз). Пусть это ребро (x_i, x_k). В случае нечетности степени d_k вершины x_k графа G добавление искусственного ребра прежде всего сделает d_k четным, и значит только ребро (x_i,x_k) нужно будет проходить дважды, если ограничиться рассмотрением лишь вершин x_i и x_k. В случае когда d_k четно, добавление искусственного ребра сделает d_k нечетным, а второе ребро выходящее из x_k должно быть пройдено дважды (т.е. добавляется еще одно искусственное ребро). Такая ситуация сохраняется до тех пор, пока не встретится вершина нечетной степени, о чем говорилось выше. Следовательно, чтобы удовлетворить условию возвращения в вершину x_i, нужно дважды пройти всю цепь из x_i в некоторую другую вершину нечетной степени x_{r X}^-_{. Это автоматически приводит к выполнению условия прохождения вершины xr. Аналогично обстоит дело для всех других вершин xi X}^-_{. Это значит что все множество M цепей из G, определенное выше, должно проходится дважды, и так как отсюда вытекает, что каждое ребро из G}^-_{(M) должно проходиться один раз, то теорема доказана.}

_{Алгоритм решения задачи китайского почтальона немедленно следует из доказанной теоремы, так как все, что для этого необходимо, состоит в нахождении множества цепей M}^* _{(цепного паросочетания для множества вершин нечетной степени), дающего наименьший дополнительный вес. Цикл наименьшего веса, проходящий по G, будет иметь вес, равный сумме весов всех ребер из G плюс сумма весов ребер в цепях из M}^*_{. Это то же самое, что и сумма весов всех ребер — реальных и искусственных — графа G}^-_(M^*_).

Описание алгоритма решения задачи китайского почтальона:

1. Пусть [c_ij] — матрица весов ребер G. Используя алгоритм нахождения кратчайшей цепи, образуем |X^-|_*|X^-| — матрицу D=[d_ij], где d_ij — вес цепи наименьшего веса, идущей из некоторой вершины x_{i X}^- _{в другую вершину xj X}^-_.

2. _{Найдем то цепное паросочетание M}^* _{для множества X}^-_{, которое дает наименьший вес (в соответствии с матрицей весов D). Это можно сделать эффективно с помощью алгоритма минимального паросочетания.}

3. _{Если вершина xα сочетается с другой вершиной xβ, то определим цепь μαβ наименьшего веса (из xα в xβ), соответствующую весу dαβ, делая шаг 1. Добавим искусственные ребра в G, соответствующие ребрам из μαβ, и проделаем это для всех других цепей из множества M}^*_{, в результате чего получится граф G}^-_(M^*_).

4. _{Сумма весов всех ребер графа G}^-_(M^*_{), найденная с использованием матрицы [cij] (вес искусственного ребра берется равным весу параллельного ему реального ребра), равна минимальному весу цикла, проходящего по G. При этом число прохождений цикла по ребру (xi,xj) равно общему числу параллельных ребер между xi и xj в G}^-_(M^*_).

Покажем, что указанный выше алгоритм строит минимальный цикл. Для этого следует заметить, что поскольку на шаге 2 мы используем минимальное паросочетание, никакие две кратчайшие цепи μ_ij и μ_pq при таком паросочетании (скажем, идущие из x_i в x_j и из x_p в x_q) не могут иметь общего ребра. Если бы они имели общее ребро (x_a, x_b), то сочетание вершин x_i и x_q (использующее подцепи от x_i к x_b и от x_b к x_q) и сочетание пары вершин x_p и x_j (использующее подцепи от x_p к x_a и от x_a к x_j) давало бы общее паросочетание веса 2c_ab, меньшего чем вес первоначального паросочетания, что противоречит предположению о минимальности исходного паросочетания. Следовательно, граф G^-(M^*)не должен содержать более двух параллельных ребер между любыми двумя вершинами, т.е. оптимальный цикл не проходит ни по какому ребру графа G более чем два раза.

Глава 2. Гамильтоновы циклы

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

§1. Основные понятия и определения

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

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

Замечание.

Характеристики

Список файлов реферата