Первая страница / Теория / Графы. Циклы и разрезы /

Циклы и разрезы. Задача Эйлера

Голосование: 21, 7

Циклы, система фундаментальных циклов

Мультиграф — граф, где между двумя заданными вершинами может быть несколько дуг. Дуги, соединяющие одну и ту же пару вершин, принято называть параллельными. Мультиграф, у которого максимальное число параллельных дуг — s, называют s-графом.

Рассмотрим неориентированный мультиграф (s-граф) G, n — вершин, m — ребёр, p — связных компонент. ρ(G) = n − p — коцикломатическое число (число ребер в остовах всех p связных компонент графа). ν(G) = m − ρ(G) = m − n + p — цикломатическое число. Если граф отождествить с электрической цепью, то определенные числа приобретают физический смысл. ν(G) — наибольшее число независимых круговых токов в электрической цепи. ρ(G) — наибольшее число независимых разностей потенциалов в электрической цепи.

Далее в этом разделе разговор будет вестись о неориентированных графах. Напомним, что циклом в неориентированном графе называется цепь, у которой совпадают начало и конец. Цикл будем называть простым, если в нем нет одинаковых вершин (кроме первой и последней). Такие циклы можно представлять как множества ребёр. Рассмотрим операцию ⊕ сложения по модулю 2 или симметрической разности над множествами ребёр:

M1 ⊕ M2 = {e | (e ∈ M1 ∧ e ∉ M2) ∨ (e ∉ M1 ∧ e ∈ M2) }.

Рассмотрим ряд вспомогательных фактов:

  1. 0M = Ø
  2. 1M = M
  3. M ⊕ Ø = M
  4. M ⊕ M = Ø

M называется линейной комбинацией {Mi}, если M = ⊕ αiMi, где αi ∈ {0, 1}.

Таким образом множество подмножеств ребёр графа оказывается линейным пространством над полем {0, 1}.

Множество циклов {Zi} называется независимым, если ∀i Zi не является линейной комбинацией остальных.

На графе отмечено три цикла

Максимальное независимое множество циклов (или минимальное множество циклов, от которых зависят все остальные) называется фундаментальной системой циклов. Циклы системы называют фундаментальными. В приведенном на рисунке графе циклы: Φ1 = (1100100), Φ2 = (0010011), Φ3 = (1111000) — образуют фундаментальную систему циклов (разумеется, читатель знаком с формой представления подмножеств некоторого множества в виде битовых векторов). Отметим, что не любая линейная комбинация циклов является циклом (Φ1 ⊕ Φ2 = (1110111) циклом не является).

Теорема

Рассмотрим граф G = (VE): неориентированный, связный (p = 1) и немультиграф (s = 1). Тогда количество фундаментальных циклов в точности равно ν(G) = m − n + 1.

Доказательство. Приведем конструктивное доказательство этого факта (оно одновременно содержит алгоритм построения фундаментальной системы циклов). Рассмотрим T(VET) — некоторый остов графа G, который существует ввиду связности. Этому остову соответствует кодерево T*(VET*), где ET* = E \ ET. Отметим, что кодерево разумеется не является деревом. Каждое ребро e ∈ T* из кодерева при добавлении его к остову T очевидно порождает ровно один простой цикл Ze. Эти циклы независимы, так как каждый из них содержит свое индивидуальное ребро e.

Покажем, что любой цикл графа G зависит от {Ze}, где e пробегает все множество ребер кодерева T*. Понятно, что любой элемент фундаментальной системы зависит от неё же самой, поэтому далее будем считать, что Z ≠ Ze.

Пусть теперь некоторый цикл Z содержит ребра e1, …, ek ∈ T*. Такие ребра в Z обязательно есть, в противном случае Z ⊂ T, что невозможно, так как T — дерево. Обозначим цикл, соответствующий ребру ei, как Zi. Докажем индукцией по k, что Z = Z1 ⊕ … ⊕ Zk.

База: пусть k = 1, тогда e1 ∉ T, Z \ {e1} ⊂ T и Z = Z1, так как если бы Z ≠ Z1, то концы e1 были бы соединены в T двумя цепями, что невозможно.

Пусть (индукционное предположение) Z = Z1 ⊕ … ⊕ Zm для всех циклов Z, содержащих m < k ребер из кодерева. Далее ребра кодерева будем называть хордами. Рассмотрим цикл Z c k хордами e1, …, ek ∈ T*. Рассмотрим Zk. Имеем Z′ := (Z \ {ek}) ∪ (Zk \ {ek}) — тоже цикл (возможно, не простой). Но Z′ содержит только k − 1 хорду e1, …, ek−1. По индукционному предположению Z′ = Z1⊕ … ⊕ Zk−1. Добавим к этому циклу Zk. Имеем:

Z′ ⊕ Zk = (Z \ {ek}) ∪ ((Zk \ {ek}) ⊕ Zk) = (Z \ {ek}) ∪ {ek} = Z.

Таким образом, {Ze}, где e ∈ T*, является фундаментальной системой циклов. Поскольку все фундаментальные системы содержат одинаковое число элементов (как базисы векторного пространства), достаточно ограничиться рассмотрением любой, например, той, которая определяется остовом T. Число ребер в ней равно числу ребер в кодереве.

|ET*| = |E| − |ET| = m − (n − 1) = m − n + 1.

Алгоритм построения фундаментальной системы циклов (для графа такого, как в условии теоремы):

  1. Построим любое остовное дерево T исходного графа G.
  2. Добавим к T некоторое ребро e, которое является ребром графа, но не принадлежит остову.
  3. Очевидно, что после такого добавления образуется цикл Ze.
  4. Все циклы {Ze} (соответствующие всем ребрам, взятым не из остова) образуют фундаментальную систему циклов.

Разрезы, система фундаментальных разрезов

В этом разделе будем рассматривать только связные графы. Если вершины неориентированного графа G = (VE) разбиты на два множества V1 и V2, то множество ребер графа G, одни концевые вершины которых лежат в V1, а другие — в V2 называется разрезом графа G. Иногда разрезы называют коциклами. Множество ребер разреза обозначается (V1V2). Таким образом подграф Gp = (VE \ (V1V2)), полученный из G удалением ребер принадлежащих разрезу, является несвязным графом, состоящим по крайней мере из двух компонент связности.

Множество ребер S, удаление которых из графа G дает несвязный подграф Gp = (VE \ S) и при этом не существует никакого собственного подмножества S′ ⊂ S, такого, что граф Gp′ = (VE \ S′) также несвязен, называется правильным разрезом. Нетрудно понять, что правильный разрез разбивает граф G ровно на 2 компоненты связности, поэтому его можно представить S = (V1V2), где V1 — вершины первой компоненты связности, а V2 — второй. Любой разрез можно представить, как объединение правильных разрезов, поэтому далее под разрезом будем подразумевать правильный разрез.

Аналогично тому, как это было сделано в предыдущем разделе, определяются понятия: независимого множества разрезов {Si} и фундаментальной системы разрезов.

Теорема

Рассмотрим граф G = (VE): неориентированный, связный (p = 1) и немультиграф (s = 1). Тогда количество фундаментальных разрезов в точности равно ρ(G) = n − 1.

Доказательство. Доказательство проводится в той же технике, что и доказательство аналогичной теоремы из предыдущего раздела. В доказательстве может помочь описание алгоритма построения фундаментальной системы разрезов, которое будет дано ниже, и то, что в любом остове графа ровно n − 1 ребро. Упражняйтесь!

Алгоритм построения фундаментальной системы разрезов (для графа такого, как в условии теоремы):

  1. Построим любое остовное дерево T исходного графа G.
  2. Удалим некоторое ребро e из остовного дерева. Понятно, что остов распадется на две компоненты связности. Вершины первой компоненты обозначим V1, а второй — V2.
  3. Этому ребру тогда будет соответствовать разрез Se = (V1V2).
  4. Все разрезы {Se} (соответствующие всем ребрам, взятым из остова) образуют фундаментальную систему разрезов.

Матрицы фундаментальных циклов и разрезов

Матрицей фундаментальных циклов графа G называется матрица Φ = [φij], состоящая из ν(G) строк и m столбцов, в которой φij равно 1, если ребро aj принадлежит циклу Φi, и равно 0 в противном случае. Предположим, что система фундаментальных циклов порождена некоторым остовом T графа G. Тогда, если ребра не принадлежащие дереву T, пронумеровать последовательно от 1 до ν(G), а ребра дерева T от ν(G) + 1 до m, то матрица циклов Φ будет иметь вид Φ = (I|Φ12), где I — единичная матрица.

Матрица фундаментальных разрезов K = [kij] определяется аналогично — как матрица с ρ(G) строками и m столбцами, где kij есть 1, если ребро aj принадлежит разрезу Ki, и 0 в противном случае. При той же самой нумерации ребер, что и выше матрица K имеет вид K = (K11|I).

Теорема

B — матрица инциденций графа G. Тогда выполняются следующий соотношения:

  1. B × ΦT = 0
  2. Φ × KT = 0

Доказательство. Практическая ценность этих соотношений автору неизвестна. Упражняйтесь!

Эйлеров цикл

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

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

Леонард Эйлер (1707-1783) первым в своей знаменитой задаче о Кёнигсбергских мостах рассмотрел вопрос о существовании таких циклов в графах.

Карта Кёнигсберга и эквивалентный ей граф

Кёнигсберг (теперь Калининград) расположен на обоих берегах реки Преголя и на двух островах этой реки. Берега реки и два острова соединены семью мостами, как показано на карте. Вопрос — поставленный в 1736 году — состоит в том, можно ли начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Если каждый берег реки и острова считать вершинами графа, а каждый мост ребром, то карту можно представить в виде 2-графа, как показано на рисунке. Эйлер установил, что указанный граф не содержит эйлерова цикла, и этот результат ознаменовал рождение теории графов.

Теорема

Если неориентированный граф G связен и в нем более одной вершины, то следующие утверждения эквивалентны:

  1. G — эйлеров граф.
  2. Каждая вершина G имеет четную степень.
  3. Множество ребер G можно разбить на простые циклы.

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

  1. 1 ⇒ 2) Пусть Z — эйлеров цикл. Двигаясь по Z, будем подсчитывать степени вершин, полагая их до начала прохождения нулевыми. Прохождение каждой вершины вносит 2 в степень этой вершины. Поскольку Z содержит все ребра, то когда обход Z будет закончен, будут учтены все ребра, а степени всех вершин — четные.
  2. 2 ⇒ 3) G — связный граф, в котором более одной вершины, следовательно, ∀v d(v) > 0. Степени всех вершин четные, следовательно ∀v d(v) ≥ 2. Имеем:
    2m = ∑ d(v) ≥ 2n ⇒ m ≥ n ⇒ m > n − 1.
    Следовательно, граф G — не дерево, а значит, граф G содержит (хотя бы один) простой цикл Z1. (Z1 — множество ребер). Тогда G − Z1 (из графа удаляем все ребра, которые содержатся в цикле) — подграф, в котором опять все степени вершин четные. Исключим из рассмотрения изолированные вершины. Таким образом G − Z1 тоже удовлетворяет условию 2, следовательно, существует простой цикл Z2 ⊂ (G − Z1). Далее выделяем циклы Zi, пока граф не будет пуст. Имеем E = ∪ Zi и ∩ Zi = Ø.
  3. 3 ⇒ 1) Возьмем какой-либо цикл Z1 из данного разбиения. Если Z1 = E, то теорема доказана. Если нет, то существует такой цикл Z2, такой что
    v1 (v1 ∈ Z1 ∧ v1 ∈ Z2),
    так как G связен. Множество ребер Z1 ∪ Z2 является циклом и содержит все свои ребра по одному разу. Если Z1 ∪ Z2 = E, то теорема доказана. Если нет, то существует цикл Z3, такой что ∃v1 (v1 ∈ Z1 ∪ Z2 ∧ v1 ∈ Z3). Далее будем наращивать эйлеров цикл, пока он не исчерпает разбиения.

Теорема

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

Доказательство. Ниже приведено доказательство только в одну сторону. Если число вершин нечетной степени 0, то эйлеров цикл, которой найдется в графе, и будет эйлеровой цепью. Если есть 2 вершины нечетной степени, то их можно соединить ребром. В полученном графе будет эйлеров цикл. Если из этого цикла исключить фиктивное ребро, то получится эйлерова цепь.

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

Теорема

Связный ориентированный граф G (в котором более одной вершины) содержит эйлеров контур (эйлеров путь) тогда и только тогда, когда все полустепени захода dto(v) и полустепени исхода dout(v) вершин удовлетворяют условиям:

  1. Для случая контура ∀ v ∈ E: dto(v) = dout(v).
  2. Для случая пути ∀ v ≠ p и ≠ q: dto(v) = dout(v), dto(q) = dout(q) + 1 и dto(p) = dout(p) − 1, где p — начальная, а q — конечная вершины эйлерового пути.

Доказательство. Эта теорема — фактически автоматом следует из аналогичной теоремы для неориентированного графа.

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

Вход: эйлеров граф G(VE), заданный списками смежности (Γ[v] — список вершин смежных с вершиной v).

Выход: последовательность вершин эйлерового цикла.


  S := Ø { стек для хранения вершин }
  select v ∈ V { произвольная вершина }
  v → S { положить v в стек S }
  while S ≠ Ø do
    v ← S; v → S { v — верхний элемент стека }
    if Γ[v] = Ø then
      v ← S; yield v
    else
      select u ∈ Γ[v] { взять первую вершину из списка смежности }
      u → S
      Γ[v] := Γ[v] \ {u}; Γ[u] := Γ[u] \ {v} { удалить ребро (v, u) }
    end if
  end while

Обоснование. Принцип действия этого алгоритма заключается в следующем. Начиная с произвольной вершины, строим путь, удаляя ребра и запоминая вершины в стеке, до тех пор пока множество смежности очередной вершины не окажется пустым, что означает, что путь удлинить нельзя. Заметим, что при этом мы с необходимостью придем в ту вершину, с которой начали. В противном случае это означало бы, что вершина v имеет нечетную степень, что невозможно по условию. Таким образом, из графа были удалены ребра цикла, а вершины цикла были сохранены в стеке S. Заметим, что при этом степени всех вершин остались четными. Далее вершина v выводится в качестве первой вершины эйлерового цикла, а процесс продолжается, начиная с вершины, стоящей на вершине стека.

Лемма

В любом графе число вершин нечетной степени четно.

Доказательство. ∑ d(v) = 2m, то есть сумма степеней всех вершин — четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, значит, их четное число.

Пусть Γ(n) — множество всех графов с n вершинами, Ε(n) — множество эйлеровых графов с n вершинами.

Теорема

Эйлеровых графов почти нет, то есть

limn→∞ |Ε(n)|⁄|Γ(n)| = 0

Доказательство. Детали доказательства можно посмотреть например в [1]. Достаточно, используя метод математической индукции и некоторые промежуточные построения, доказать неравенство:

|Ε(n)| ≤ |Γ(n)| ⁄ 2n−1

Из него автоматом вытекает то, что требуется. Дерзайте!

Родственные задачи

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

  1. Каково наименьшее число цепей или циклов необходимо для того, чтобы каждое ребро графа G содержалось точно в одной цепи или цикле? Очевидно, что если G имеет эйлерову цепь или эйлеров цикл, то ответом будет число один.
  2. Ребрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин njc(aj), где число nj показывает, сколько раз проходилось ребро aj, а c(aj) — вес ребра) минимален. Очевидно, что если G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится только один раз и вес этого цикла равен тогда ∑ c(aj).

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

  1. Сбор мусора. Рассмотрим проблему сбора домашнего мусора. Допустим, что определенный район города обслуживается единственной машиной. Ребра графа G представляют дороги, а вершины — пересечения дорог. Величина c(aj) — вес ребра — будет соответствовать длине дороги. Тогда проблема сбора мусора в данном районе сводится к нахождению цикла в графе G, проходящего по каждому ребру G по крайней мере один раз. Требуется найти цикл с наименьшим километражем. С учетом того, как на самом деле курсирует машина, возникает задача: найти Q циклов, которые вместе покроют все ребра графа и при этом их суммарная длина будет минимальной. Машина будет ездить по расписанию и в i-ый день объезжать i-ый цикл.
  2. Доставка молока или почты. Еще две задачи, когда требуется определить маршрут, проходящий хотя бы один раз по каждой из улиц, возникает при доставке молока или почты. Здесь задача состоит в нахождении маршрута, минимизирующего общий километраж (или время, стоимость и т. д.).
  3. Проверка электрических, телефонных или железнодорожных линий. Проблема инспектирования распределенных систем (лишь некоторые, из которых названы выше) связана с непременным требованием проверки всех "компонент". Поэтому она также является проблемой тип (2) или близка к ней.
  4. Другие приложения могут быть связаны с разбрасыванием смеси песка и соли на главных дорогах зимой для предотвращения обледенения, с наилучшим методом работы автоматических вентиляционных устройств, с уборкой помещений и коридоров в больших учреждениях и даже с наилучшим маршрутом осмотра музея!

Перейдем к рассмотрению алгоритма решения задачи китайского почтальона для общего случая. Рассмотрим неориентированный граф G = (VE). Разобьем множество вершин графа V на множество вершин с четными степенями V+ и множество вершин с нечетными степенями V-. Опишем алгоритм по шагам:

  1. Пусть [cij] — матрица весов ребер графа G. Используем алгоритм кратчайшей цепи (алгоритм Флойда), образуем |V-| × |V-| — матрицу D = [dij], где dij — вес цепи наименьшего веса, идущей из некоторой вершины vi ∈ V- в другую вершину vj ∈ V-.
  2. Найдем то цепное паросочетание M* для множества V-, которое дает наименьший вес (в соответствии с матрицей весов D). Это можно сделать эффективно с помощью алгоритма построения полного паросочетания минимального веса в произвольном графе.
  3. Если вершина vα сочетается с другой вершиной vβ, то определим цепь μαβ наименьшего веса (из vα в vβ), соответствующую весу dαβ. Добавим искусственные ребра в G, соответствующие ребрам из μαβ, и проделаем это для всех других цепей из множества M*, в результате чего получится s-граф. Обозначим его G-(M*). Можно показать, что в этом графе есть эйлеров цикл.
  4. Сумма весов всех ребер графа G-(M*), найденная с использованием матрицы [cij] (вес искусственного ребра берется равным весу параллельного ему реального ребра), равна минимальному весу цикла, проходящего по G. При этом число прохождений цикла по ребру (vivj) равно общему числу параллельных ребер между vi и vj в G-(M*).

Обоснование этого достаточно нетривиального алгоритма можно найти, например, в [2].

Связь между эйлеровыми и гамильтоновыми циклами

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

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

Исходный граф и соответствующий ему реберный

Теорема

Имеют место следующие утверждения о взаимоотношениях между эйлеровыми и гамильтоновыми циклами:

  1. Если G имеет эйлеров цикл, то Gl имеет как эйлеров, так и гамильтонов циклы.
  2. Если G имеет гамильтонов цикл, то Gl также имеет гамильтонов цикл.

Доказательство. Можно проделать самому или посмотреть в книге Harrary F., Nash-Williams C. St. J. A. (1965), "On Eulerian and Hamiltonian graphs and line graphs".

Список литературы

  1. Новиков Ф.А. Дискретная математика для программистов. — СПб: Питер, 2000.
  2. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.

Владимир Лоторейчик


Владимир / 2008-03-22 10:24:36

В теореме о существовании эйлерова цикла в ориентированном графе он назван неориентированным.

Спасибо за сообщение. Ошибка исправлена.

Константин / 2011-12-05 13:05:29

Спасибо автору за раздел.

В разделе "Матрицы фундаментальных циклов и разрезов"

в доказательстве к теореме написано "Практическая ценность этих соотношений автору неизвестна. Упражняйтесь!"

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

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

Доказательство приведено К.Берж "Теория графов и ее применение" или Ф. Харари "Теория графов"

Alex / 2012-11-25 23:30:42

Не подскажите, существуют ли приложения матриц фундаментальных циклов и разрезов при анализе топологии сетей ЭВМ?

К сожалению, ничего Вам ответить не могу, поскольку топологией сетей ЭВМ не занимался.

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий