XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 57
Текст из файла (страница 57)
Построенный таким образом ориентированный граф 6 будет сетью. Действительно, предположим, что в нем существует контур, содержащий некоторую вершину к. Тогда и ~+ и, так как контур есть путь ненулевой длины. Если и =«1 к, то существует дуга (петля), ведущая из к в к, т.е. и ~ и.
Но такой петли в графе 6 быть не может, так как ни один элемент не может доминировать над самим собой (отношение доминирования иррефлексивно). Если же к ~в к, где и ) 1, то существует вершина о, отличная от к, такая, что и ~+ о и о ~+ к, откуда, согласно построению графа 6, следует, что к < о и о < и, но зто невозможно. Итак, 6 — бесконтурный ориентированный граф, т.е.
сеть. Входы сети 6 есть минкмалькые элеменчпы исходного упорядоченного множества, а выходы — максимальные. Кроме 356 5. 'ГЕОРИЯ ГРАФОВ того, каждый уровень сети образует аннгццепь в упорядоченном множестве (А, <). Построенная сеть С будет обладать еще одним интересным свойством: для любых трех попарно различных вершин и, е и гв из того, что н-+е и е-+го, следует и гиг.
Иначе говоря, в сети С отсутствуют все „замыкающие дуги", подобные дуге ег -+ еэ для сети, изображенной на рис. 5.39. Такие сети будем называть просюпмми. (а» (а,Ь» (а,ь,е» "г "г (е» (Ь,е» Рис. 5.40 Рис. 5.39 Итак, каждому упорядоченному множеству может быть сопоставлена простая сеть согласно описанной вьппе процедуре. Эта простая сеть может рассматриваться как вариант наглядного изображения конечного упорядоченного множества и использоваться как диаграмма Хассе.
На рис. 5АО показана сеть, сопоставленная множеству всех подмножеств трехзлементного множества (а, Ь, с1, упорядоченного отношением включения. Полезно сравнить эту сеть с диаграммой Хассе, приведенной на рис. 1.13. 5.9. Элементы цикломатжки При обсуждении алгоритма поиска в глубину в иеоривннгированиом графе рассматривался вопрос о поиске так называемых фуидаменнгальныя циклов графа. При этом под фундаментальным понимался цикл, содержащий в точности одно обршпиое ребро, и между фундаментальными циклами и обратными 357 5.9.
Элементы цикломлтики ребрами устанавливалось взаимно однозначное соответствие. Фундаментальные циклы возникают всякий раэ, как только фиксировано произвольное разбиение всех ребер неориентированного графа на дргвесиьде (формирующие некоторый максимальный осдповиыб лес исходного графа) и обратные, причем в общем случае это разбиение может быть задано совершенно независимо от алгоритма поиска в глубину.
Поиск в глубину есть лишь один иэ способов реализации такого разбиения. Теперь рассмотрим вопрос о фундаментальных циклах неориентированного графа с алгебраической точки зрения и покажем, что фундаментальные циклы являются базисом некоторого линейного проспдраиспдва, которое содержит все циклы графа, а алгоритм поиска в глубину вычисляет один из базисов этого линейного пространства'.
Алгебраическое изучение циклов неориентированного графа важно, в частности, при исследовании проблемы распознавания изоморфизма двух графов. Пусть с — некоторая иепь графа С. Через Е(с) обозначим множество ребер этой цепи. Для любой цепи с множество ее ребер Е(с) определяется однозначно. Обратно, если фиксировано какое-то (конечное) множество ребер (ед,..., е„) графа С, то можно доказать следуюдций факт: если указанное выше множество ребер формирует цепь, т.е.
существует такая цепь (последовательность вершин графа) оо, ид, ..., ои, что доо од) = е;„..., (о„м ин) = е;„, где 1 ( дд, ..., дн ( дд, то эта цепь при условии, что она не является циклом, определяется с точностью до порядка расположения ребер в последовательности (от оо к ии или наоборот). Если цепь является циклом, то она определяется с точностью до порядка расположения ребер в последовательности и до выбора начальной вершины ов. Так, на рис. 5.41 множество ребер Цод, оз), (ог, из), (оз, об), (об,ивЦ формирует цепь од, оз, оз, об, ов, а также цепь об, об 93 оя, од (е инверсия" предыдущей цепи). Множество ре- *Отметим, что не любой базис может быть вычислен посредством поиске в глубину (см.
граф на рис. 5.23). 358 Б. ТЕОРИЯ ГРАФОВ ов ов с, Рис. 3.41 бер ((оь ог) (ог, из), (из, о1)) формирует цикл оь иг, из, эь а вместе с ним циклы: и2в Озв О1в иг~ Озв и1в и2в из~ изв Ог~ ОЬ ОЗ~ Ог~ ОЬ ивв Ог иЬ "Зв О2в О1~ МНОжЕСтВО жЕ рсбср Ци1в Ог)э (62, ОЗ), (ОЗв иб), 1ти4в ОЕ)) НЕ формирует никакой цепи. Тогда, говоря неформально, если не различать цепи, состоящие из одних и тех же ребер, но проходимые в противоположных направлениях, и циклы, состоящие из одних и тех же ребер, но проходимые в противоположных направлениях и от различных начальных вершин, можно отождествить цепи (и циклы) с множествами их ребер. Эти соображения позволяют ввести операцию сложения цепей как операцию над множествами их ребер.
Для двух произвольных цепей а, Ь графа 0 их сумму определим (с учетом сделанного выше замечания) так: аЩЬ= Е(а) в."3Е(Ь), т.е. сложение цепей сводится к вычислению силвлвентрической разностпи множеств их ребер. Сумма цепей, вообще говоря, не является цепью, т.е. соответствующее множество ребер в общем случае не формирует цепь.
На рис. 5.41 сумма цепей о1, оз о4, иб и ог, оз, о4, об, ое не есть цепь. Алгебра, сиснтелвотг образртои4ия которой служит множество всех конечных цепей данного графа С, назы- 5.9. Элвмевтм цикломатики 359 вают алгеброй цепей неориентпированного гра4а С. Эта алгебра является абелевой группой в силу известных свойств операции симметрической разности множеств (см.
1 и 2). Любая абелева группа ст = (М, йт, 0) может быть рассмотрена как линейное простпранстпво над полем Ег (полем вмчетпов по модулю 2). Действительно, определим умножение элемента д группы на элементы поля Ег: О д= 0 и 1 д=д. Выполнение аксиом линейного пространства в этом случае можно легко проверить. Обратим внимание, что в любой линейной и комбинации 2 Аь еь элементов е1, ..., еь такого линейного Ьмт пространства каждый коэффициент Аь равен либо О, либо 1. Тогда понятно, что нетривиальнэл линейная комбинация элементов ем ..., е„,т.е.
линейная комбинация, не все коэффициенты которой равны О, есть не что иное, как сумма элементов непустого подмножества множества ~ем..., ев). Применив указанное построение к алгебре цепей неориентированного графа, получим линейное пространство цепей данного графа. Его называют простпранстпвом цепей градта. Заметим, что в этом пространстве каждый элемент противоположен себе самому, так как для каждого элемента а этого пространства а йт а = И (в силу известных свойств операции симметрической разности). Рассмотрим теперь линейное подпростпранстпво этого линейного пространства, порожденное лтножестпволт всех конечных циклов данного графа. Это линейное пространство будем называть простпранстпволв циклов данного гратра.
Пространство циклов неориентированного графа есть тем самым линейнал оболочка в пространстве цепей данного графа множества всех его конечных циклов (причем, как видно на рис. 5.42, сумма циклов в общем случае не есть цикл). Если граф конечен, то его пространство циклов также конечно. Теорема 5.6.
Множество фундаментальных циклов, вычисляемое алгоритмом поиска в глубину в неориентированном графе О, есть базис пространства циклов этого графа. 360 б. ТЕОРИЯ ГРАФОВ о~ пз оз "з Рмс. б.42 < Как следует кэ описания алгоритма поиска в глубину, каждый вычисляемый им фундаментальный цикл содержит в точности одно обратное ребро и каждое обратное ребро принадлежит в точности одному фундаментальному циклу.
Таким образом, каждый фундаментальный цикл содержит ребро, не принадлежащее остальным циклам, и, следовательно, сумма элементов любого непустого подмножества множества фундаментальных циклов отлична от нуля, т.е. фундаментальные циклы, вычисляемые алгоритмом поиска в глубину, являются линейно независимыми.
Теперь докажем, что любой цикл графа С есть линейная комбинация фундаментальных циклов. Докажем сначала, что в пространстве циклов сумма любых двух отличных друг от друга циклов есть либо замннргпал цепь (в частности, цикл), либо непустое множество попарно не пересекающихся (т.е. не имеющих один с другим ни общих ребер, ни общих вершин) циклов'. Пусть С1 и С2 — два цикла графа С. Если они не имеют ни общих вершин, ни общих ребер, то доказываемое утверждение 'Это вмраженне есть, разумеетсл, вольность речи. Строго говорл, сумму циклов нельзя назвать множеством цнкаов, но ей в данном случае можно однозначно сопоставить такое множество.
Так, на рнс. б.42 сумме цнклов соответствуют два непересекающихся между собой цнкла. 361 6.9. Заоиенты лияаоыатияя тривиально. Предположим, что ребра ео = (ам 61), ..., е„= (а„, 6„) все ребра, общие для циклов С1 и Сз (рис. 5.43). В каждом из рассматриваемых циклов для каждого о = 1, и-1 существуют цепи, соединяющие вершины 6; и а;+1. Обозначим их Ю1 для первого и И~~ для второго цикла. Также существуют цепи, в первом цикле — ЬРе~ и во втором — ФРИ, соединяющие вершины а1 и 6„. Все эти цепи таковы, что не содержат ни одного из ребер е;, о = 1, и. Поскольку ребра е;, о = 1, и,— все ребра, общие для циклов С1 и Сз, то для каждого о = = О, и — 1 цепи И~~ и И~~ не имеют общих ребер и имеют две общие вершины (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
