3.2. Разбиения ребер

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

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

Рис. 3.1.

Если в любом из этих реберных разделений объединить цикл с одной из цепей, то образуется не простая цепь, а число множеств уменьшается на 1.

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

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

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

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

Доказательство. Если граф содержит петли, то удалим их и рассмотрим полученный таким образом новый граф, все вершины которого сохраняют четную степень. Начнем движение с любой вершины по некоторому ребру к другой граничной точке ребра, скажем Так как вершина имеет четную степень, то она инцидентна второму ребру, которое приводит нас к вершине Продолжая такой процесс обхода, мы всегда дойдем до вершины так как четность всех вершин гарантирует, что в любом случае мы можем «покинуть» любую вершину, используя ребро, отличное от того, по которому мы пришли в эту вершину. Так как число ребер конечно, то в результате для некоторого мы имеем Пройденные ребра образуют цикл. Если при этом оказалось, что пройдены все ребра, то теорема доказана. В противном случае мы удалим полученный цикл и рассмотрим оставшийся подграф. Каждая вершина этого подграфа имеет четную степень (почему?), и следовательно, мы можем повторить предыдущее построение, найти и удалить второй цикл. За конечное число шагов удаление очередного цикла приведет к тому, что в подграфе не останется ребер Полученное множество циклов вместе с удаленными вначале петлями образует реберное разделение графа . А так как связен, то объединение этих циклов, т. е. снова является циклом. (Проверьте это.) Теорема доказана.

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

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

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

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

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

Из теорем 3.1 и 3.2 непосредственно следует следующее свойство уникурсальных графов.

Теорема 3.3. Связный граф является уникурсальным тогда и только тогда, когда он имеет или точно 2 вершины нечетной степени. В первом случае он покрывается циклом; в последнем — цепью, соединяющей две вершины нечетной степени.

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

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

Рис. 3.2.

Так как все четыре вершины имеют нечетную пень, то граф не является уникурсальным.

Рис. 3.3.

Согласно теореме 3.2 требуется, по крайней мере, две цепи для того, чтобы покрыть этот граф.

На рис. 3.3 показаны два минимальных реберных разделения. (В обоих случаях одна из цепей показана пунктиром, а другие — сплошной линией.)

Упражнения

(см. скан)