Новиков Ф.А. Дискретная математика для программистов (860615), страница 63
Текст из файла (страница 63)
Фундаментальные циклы и разрезыРис. 10.3. Фундаментальные циклыПример На рис. 10.3 нет фундаментальных циклов, пе имеющих общих вершин. Симметрическая разность трёх фундаментальных циклов Z\ Д Z3 Д Z4 даётцикл (vi,v2), (v2,v4), (v4,v5), (v5,v6), (v6,v3), (u 3 ,ui) - «впешпию границу» графа.Симметрическая разность всех фундаментальных циклов Z\ д Z2 Д Z3 д Z 4 даётэйлеров цикл данного графа (см.
следующий раздел).10.1.3. Фундаментальная система разрезови коциклический рангПусть опять T(V, Ет) — некоторый остов графа G(V, Е). Рассмотрим ребро остова е е Ет и определим разрез Se следующим образом. Ребро е — мост в деревеТ. Следовательно, удаление ребра е разбивает множество вершин V на два непустых подмножества V\ wV2, так что Vi <zV,V\ ф 0, V2 с V, V2 Ф 0, V\ U V2 = V,VI П V2 — 0 .
Включим в разрез Se ребро e и все хорды остова Т, соединяющиевершины множества V\ с вершинами множества V2:SE= e f e + {(vuv2)е ГI Vl € Ki & V2 G V2} =E(VUV2).Тогда SE — это простой разрез. Система разрезовS ={Se]eeTназывается фундаментальной системой разрезов. Разрезы фундаментальной системы называются фундаментальными, а количество разрезов в (данной) фундаментальной системе называется коциклическим рангом (или коцикломатическимчислом) графа G и обозначается m*(G).ЗАМЕЧАНИЕМежду циклами и разрезами существует определённая двойственность, поэтому разрезыиногда называют коциклами. Отсюда название «фундаментальная система коциклов» и«коциклический ранг». Детальное рассмотрение этой двойственности выходит за рамкиданной книги.338Глава 10.
Циклы, независимость и раскраскаЛюбой правильный разрез в связном графе G(V,E) можно представитькак симметрическую разность некоторых фундаментальных разрезов из системыS, определяемой произвольным остовом Т.ТЕОРЕМАДействительно, любой разрез S содержит хотя бы одно реброиз остова Т, так как Т — связный остовный подграф. Пусть S — правильныйразрез, который содержит рёбра e i , .
. . , e n € Т. Докажем индукцией по п, чтоS = Sei А . . . Д 5 е „. База: пусть п = 1, тогда Т - е\ =U Т2, где Ti и Т2 компоненты, получаемые из остова Т удалением ребра е\. Имеем Sei с S, иначе S пе был бы разрезом, и S с Sei, иначе S пе был бы правильным разрезом.Таким образом, S = S e i . Пусть теперь S = Sei Д . . .
Д Sem для всех правильных разрезов S с числом рёбер остова тп < п. Рассмотрим правильный разрезS с п рёбрами e i , . . . , е п G Т. Положим S' : = S Д S» , то есть исключим изразреза S все рёбра фундаментального разреза Sen. Разрез S' — правильный полемме 10.1.1 и содержит рёбра e i , . . . , e n _ i , а зиачит, по индукционному предположению S' = Sei Д . . . Д 5 е п _ 1 . Имеем S = S' A Sen, и окончательноS = Sei Д . . . Д Sn-i Д Sen.•ДОКАЗАТЕЛЬСТВОСЛЕДСТВИЕКоличество разрезов в фундаментальной системе равно числу рёберостова:m*(G) =рДОКАЗАТЕЛЬСТВОПО1.определению.•Пример На рис.
10.4 представлены все пять фундаментальных разрезов, соответствующих графу и его остову, представленным на рис. 10.3Р и с . 1 0 . 4 . Фундаментальные разрезы10.1.4. Подпространства циклов и коцикловРассмотрим векторное пространство (см. 2.4.1) над двоичной арифметикой(см. пример 3 в 2.3.3), натянутое на множество рёбер Е графа G(V, Е). Элемент этого векторного пространства (линейную комбинацию, см. 2.4.2) можно отождествлять с подмножеством рёбер: если коэффициент в линейной комбинации равен 1, то ребро входит в подмножество, если коэффициент равен0, то не входит.
При такой интерпретации сложению векторов соответствуетсимметрическая разность множеств рёбер.Множество циклических векторов и множество правильных разрезов замкнутыотносительно симметрической разности, а потому являются подпространствамиобщего пространства подмножеств рёбер графа.10.1. Фундаментальные циклы и разрезы339ЗАМЕЧАНИЕСтрого говоря, множество циклов, равно как и множество разрезов, не образует подпространства, поскольку не замкнуто относительно симметрической разности. Множество циклических векторов шире множества циклов, а множество правильных разрезов уже множества разрезов.
Однако интуитивно ясно, что «по потребительским свойствам» циклические векторы и циклы, равно как разрезы и правильные разрезы, весьма близки, поэтому далее в этом подразделе рассматриваются только циклические векторы и правильные разрезы, которые для краткости называются циклами и разрезами(коциклами).Множество циклов { Z { н а з ы в а е т с я независимым, если пи один из циклов Ziне является линейной комбинацией остальных.Множество разрезов {5г}Г=1 называется независимым, если ни один из разрезов Si пе является линейной комбинацией остальных.Максимальное независимое множество циклов (или минимальное множествоциклов, от которых зависят все остальные, или независимое порождающее множество циклов) является базисом пространства циклов.
Максимальное независимое множество разрезов (или минимальное множество разрезов, от которых зависят все остальные, или независимое порождающее множество разрезов) являетсябазисом пространства разрезов.Введенная в подразделе 10.1.2 фундаментальная система циклов является базисом подпространства циклов. Действительно, циклы любой фундаментальнойсистемы Z = {ZE}E€T*независимы, поскольку каждый из них содержит индивидуальную хорду е е Т*, и по теореме 10.1.2 фундаментальная система порождает множество циклов. Таким образом, циклический ранг — это размерностьпространства циклов.ЗАМЕЧАНИЕФундаментальные системы циклов, порождаемые остовами, — это не единственные базисы пространства циклов.
Например, четыре «естественных» треугольника на рис. 10.3 —{(viiwa),(va,v3),(w3,vi)}, {(^2,и4), («4, ив), (VB,«а)}, {(«а,«в), («в,«з), («з,«я)}, {(«з,«в),(u5,ve), (ив, ^з)} — являются базисом подпространства циклов, но не являются фундаментальной системой ни для какого остова.Введенная в подразделе 10.1.3 фундаментальная система разрезов является базисом подпространства разрезов.
Действительно, разрезы любой фундаментальнойсистемы S = {SejeeT независимы, поскольку каждый из них содержит индивидуальное ребро е е Т, и по теореме 10.1.3 фундаментальная система порождаетмножество разрезов. Таким образом, коциклический ранг — это размерностьпространства разрезов.ЗАМЕЧАНИЕВсе утверждения этого и следующего разделов распространяются на случай мультиграфов.340Глава 10.
Циклы, независимость и раскраска10.2. Эйлеровы циклыЗдесь приведено исчерпывающее решение задачи о Кёнигсбергских мостах (см.подраздел 7.1.1), приведшей к исторически первой успешной попытке развитиятеории графов как самостоятельного предмета.10.2.1. Эйлеровы графыЕсли граф имеет цикл (пе обязательно простой), содержащий все рёбра графа, тотакой цикл называется эйлеровым циклом, а граф называется эйлеровым графом.Если граф имеет цепь (не обязательно простую), содержащую все рёбра, то такаяцепь называется эйлеровой цепью, а граф называется полуэйлеровым графом.Эйлеров цикл содержит не только все рёбра (по одному разу), но и все вершиныграфа (возможно, по несколько раз). Ясно, что эйлеровым может быть толькосвязный граф.ТЕОРЕМАЕсли граф G связен и нетривиален, то следующие утверждения экви-валентны:1.
G — эйлеров граф.2. Каждая вершина G имеет чётную степень.3. Множество рёбер G можно разбить на простые циклы.ДОКАЗАТЕЛЬСТВО[ 1 =>• 2 ] Пусть Z — эйлеров цикл в G. Двигаясь по Z, будем подсчитыватьстепени вершин, полагая их до начала прохождения пулевыми. Прохождениекаждой вершины вносит 2 в степень этой вершины. Поскольку Z содержит всерёбра, то, когда обход Z будет закопчен, будут учтены все рёбра, а степени всехвершин — чётные.[2=> 3 ] G — связный и нетривиальный граф, следовательно, VVi (d(vi) > 0).Степени вершин чётные, следовательно, Уг>г (d(vi) ^ 2). Имеем:рСледовательно, граф G — не дерево, а значит, граф G содержит (хотя бы один)простой цикл Z\. (Z\ — множество рёбер.) Тогда G — Zi — остовный подграф, вкотором опять все степени вершин чётные. Исключим из рассмотрения изолированные вершины.
Таким образом, G — Z\ тоже удовлетворяет условию 2, следовательно, существует простой цикл Z2 С (G - Z\). Далее выделяем циклы Zi,пока граф не будет пуст. Имеем: Е = (J Z* и f ] Z i = 0 .[ 3 = И ] Возьмем какой-либо цикл Zx из данного разбиения. Если Z\ = Е, тотеорема доказана. Если нет, то существует цикл Z2, не имеющий общих рёбер с Z\(см. рис. 10.5), такой, что((ui € Zx k vi e Z2)), так как G связен. МаршрутZ\ U Z2 является циклом и содержит все свои рёбра по одному разу.10.2. Эйлеровы циклы341Если Z\ U Z2 = Е, то теорема доказана. Если пет, то существует цикл Z3, такой,что 3 v2 (v2 6 Z\ U Z2 к v2 6 Zs). Далее будем наращивать эйлеров цикл, пока онне исчерпает разбиения.•10.2.2.
Алгоритм построения эйлерова циклав эйлеровом графеВ предыдущем разделе был установлен эффективный способ проверки наличияэйлерова цикла в графе. А именно, для этого достаточно убедиться, что степепи всех вершин чётные, что нетрудно сделать при любом представлении графа.Следующий алгоритм находит эйлеров цикл в графе, если известно, что графэйлеров.Алгоритм 10.1 Построение эйлерова циклаВход: эйлеров граф G(V,E), заданный списками смежности (Г[г;] — списоквершин, смежных с вершиной v).Выход: последовательность вершин эйлерова цикла.S : = 0 { стек для храпения вершин }select v G V { произвольная вершина }v —> S { положить v в стек S }while S ф 0 dov: = top S { v — верхний элемент стека }if Г [и] = 0 thenv <— S; yield v { очередная вершина эйлерова цикла }elseselect и е Г^] { взять первую вершину из списка смежности }и —• S { положить и в стек }r[v]: = Г[г>] - щ Г [и]: = Г [и] - v { удалить ребро (v, и) }end ifend whileОБОСНОВАНИЕПринцип действия этого алгоритма заключается в следующем.Начав с произвольной вершины v, строим путь, удаляя рёбра и запоминая вершины в стеке, до тех пор пока множество смежности очередной вершины неокажется пустым, что означает, что путь удлинить нельзя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
