Как найти количество цепей в графе

2.4. Эйлеровы циклы и цепи

Исходя из утверждений 1 и 2, чтобы найти Эйлерову цепь, нужно соединить две вершины с нечетными степенями фиктивным ребром. Тогда задача сводится к нахождению Эйлерова цикла по приведенному ниже алгоритму. Из найденного цикла удаляется фиктивное ребро, тем самым находится искомая Эйлерова цепь.

Алгоритм выделения эйлерова цикла в связном мультиграфе с четными степенями вершин

1) Выделим из G цикл m1. (так как степени вершин четны, то висячие вершины отсутствуют). Положим L=1, G¢=G.

2) Удаляем из G¢ ребра, принадлежащие выделенному циклу m1. Полученный псевдограф снова обозначаем как G¢. Если в G¢ отсутствуют ребра, то переходим к шагу 4. Если ребра есть, то выделяем из G¢ цикл mL+1 и переходим к шагу 3.

3) Присваиваем L:=L+1 и переходим к шагу 2.

4) По построению выделенные циклы содержат все ребра по одному разу. Если L:=1, то искомый Эйлеров цикл найден (конец работы алгоритма). В противном случае находим циклы, содержащие хотя бы по одной общей вершине (в силу связности графа это всегда можно сделать). Склеиваем эти циклы. Повторяем эти операции, пока не останется один цикл, который является искомым.

Пример.

Найдем Эйлерову цепь в неориентированном графе G, изображенном на рис. 10.

Прежде, чем приступать к нахождению Эйлеровой цепи, необходимо проверить степени вершин графа G − согласно утверждению 2, для существования Эйлеровой цепи, необходимо и достаточно, чтобы в графе G ровно 2 вершины нечетной степени.

В рассматриваемом графе нечетные степени имеют вершины V3 и V1 (степень этих вершин равна 3). Соединяя эти вершины фиктивным ребром так, как показано на рис. 11, получаем граф G¢:

Поскольку в конечном итоге будет получена цепь, то очевидно, что началом и концом этой цепи будут вершины с нечетными степенями. Поэтому, следуя описанному выше алгоритму, будем циклы mI так, чтобы хотя бы один из них начинался или кончался на вершинах V3 или V1.

Пусть цикл m1 составят ребра, проходящие через следующие вершины: V3 V4 V7 V6 V1 V2 V3. Согласно алгоритму, удаляем из G¢ Все ребра, задействованные в цикле m1. Теперь граф G’ будет таким, как показано на рис. 12.

Составляем следующий цикл m2: V4 V5 V6 V2 V5 V7 V4. Граф G¢ после удаления ребер, составляющих цикл m2, изображен на рис. 13.

Очевидно, что последний цикл m3 будет состоять из V3 V5 V1|V3, где последнее ребро, соединяющее вершины V1 и V3 – фиктивно. После удаления ребер, составляющих цикл m3, в графе G¢ не останется ни одного ребра.

Теперь по общим вершинам склеиваем полученные циклы. Поскольку m1 и m2 имеют общую вершину V4, то, объединяя их, получим следующий цикл: V3 V4 V5 V6 V2 V5 V7 V4 V7 V6 V1 V2 V3. Теперь склеим получившийся цикл с циклом m3: V3 V4 V5 V6 V2 V5 V7 V4 V7 V6 V1 V2 V3 V5 V1|V3. Удаляя фиктивное ребро, получаем искомую Эйлерову цепь: V3 V4 V5 V6 V2 V5 V7 V4 V7 V6 V1 V2 V3 V5 V1.

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode

Поиск элементарных цепей в графе

В этой статье речь пойдет об алгоритме поиска всех элементарных цепей в неориентированном графе. Будет приведено описание алгоритма и его реализация на языке программирования C#.

Цепью в графе называется последовательность ребер , когда каждое предыдущее ребро соприкасается одним из своих концов со следующим ребром . Цепь обозначается последовательностью вершин, которые она содержит (2-5-3-6).

Цепь называется элементарной, если все вершины, входящие в нее, различны.

Приведем пример. Пусть дан граф, как на рисунке ниже:

Все элементарные цепи в нем: 1-2, 1-3-2, 1-2-3, 1-3, 1-2-3-4, 1-3-4, 2-1-3, 2-3, 2-1-3-4, 2-3-4, 3-4.

Пусть граф задан, как G = (V, E), где V — множество вершин графа, а E — множество его ребер. Вершины и ребра можно представить объектами следующих классов:

ЭЙЛЕРОВЫ ЦЕПИ И ЦИКЛЫ

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

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

Определение 7.1. Эйлеровой цепью в неориентированном графе G назы­ва­ется простая цепь, содержащая все ребра графа G. Эйлеровым циклом назы­вается замкнутая Эйлерова цепь. Аналогично, эйлеров путь в орграфе G — это простой путь, содержащий все дуги графа G. Эйлеров контур в орграфе G — это замкнутый эйлеров путь. Граф, в котором существует эйлеров цикл, называется эйлеровым.

Простой критерий существования эйлерова цикла в связном графе дается следующей теоремой.

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

Доказательство. Необходимость. Пусть m — эйлеров цикл в связном гра­фе G, x — произвольная вершина этого графа. Через вершину x эйлеров цикл проходит некоторое количество k (k³1) раз, причем каждое прохождение, очевидно, включает два ребра, и степень этой вершины равна 2k, т.е. четна, так как x выбрана произвольно, то все вершины в графе G имеют четную сте­пень.

Достаточность. Воспользуемся индукцией по числу m ребер графа. Эйле­ровы циклы для обычных (не псевдо) графов можно построить начиная с m=3.Легко проверить, что единственный граф с m=3, имеющий все вершины с четными степенями, есть граф K₃ (рис. 7.2). Существование эйлерова цикла в нем очевидно. Таким образом, для m=3 достаточность условий доказываемой теоремы имеет место. Пусть теперь граф G имеет m>3 ребер, и пусть утверждение справедливо для всех связных графов, имеющих меньше, чем m ребер. Зафиксируем произвольную вершину a графа G и будем искать простой цикл, идущий из a в a. Пусть m(a, x) — простая цепь, иду­щая из a в некоторую вершину x. Если x ¹ a, то цепь m можно продолжить из вершины x в некотором направлении. Через некоторое число таких про­дол­­же­ний мы придем в вершину zÎX, из которой нельзя продлить полу­чен­ную про­стую цепь. Легко видеть, что z = a так как из всех остальных вершин цепь может выйти (четные степени!); a в a она начиналась. Таким образом, нами построен цикл m, идущий из a в a. Предположим, что построенный про­стой цикл не содержит всех ребер графа G. Удалим ребра, входящие в цикл m, из графа G и рассмотрим полученный граф . В графе все вершины имеют четные степени. Пусть — компо­нен­ты связ­нос­ти графа , содержащие хотя бы по одному ребру. Соглас­но пред­поло­же­нию индукции все эти компоненты обладают эйлеровыми циклами m₁, m₁, …, m_kсоот­вет­ствен­но. Так как граф G связан, то цепь m встре­чает каждую из компонент. Пусть первые встречи цикла m с ком­понентами происходят соответственно в вершинах x₁, x₂, …, x_k. Тогда про­стая цепь

является эйлеровым циклом в графе G. Теорема доказана.

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

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

Отметим, что из существования эйле­ро­ва цикла в неориентированном графе G не следует связность этого графа. Напри­мер, неориентированный граф G на рис. 7. 3 обладает эйлеровым циклом и вместе с тем несвязен.

Совершенно также, как теорема 7.1, могут быть доказаны следующие два утверждения.

Теорема 7.2. Связный неориентированный граф G обладает эйлеровой цепью тогда и только тогда, когда число вершин нечетной степени в нем равно 0 или 2, причем если это число равно нулю, то эйлерова цепь будет являться и циклом.

Теорема 7.3. Сильно связный орграф G(X, E) обладает эйлеровым кон­ту­ром тогда и только тогда, когда для любой вершины xÎX выполняется

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

Если граф G — эйлеров, то очевидно, что это число равно 1. Пусть теперь G не является эйлеровым графом. Обозначим через k число его вер­шин нечетной степени. По теореме … k четно. Очевидно, что каждая верши­на нечетной степени должна быть концом хотя бы одной из покрывающих G цепей m_i. Следовательно, таких цепей будет не менее чем k/2. С другой сто­роны, таким количеством цепей граф G покрыть можно. Чтобы убедиться в этом, расширим G до нового графа , добавив k/2 ребер , соединяющих раз­личные пары вершин нечетной степени. Тогда оказывается эйлеровым графом и имеет эйлеров цикл . После удаления из ребер граф разло­жится на k/2 цепей, покрывающих G. Таким образом, доказана

Теорема 7.4. Пусть G — связный граф с k>0 вершинами нечетной степени. Тогда минимальное число непересекающихся по ребрам простых цепей, покрывающих G, равно k/2.