Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 26
Текст из файла (страница 26)
Таким образом, любые вершины одного и того же класса эквивалентности принадлежат некоторому циклу, однако простого цикла, проходящего через эти вершины, может и не быть. На множестве Ь'; классов эквивалентности вершин графа отношение достижимости индуцирует отношение частичной упорядоченности: г';('г'; в том и только том случае, когда некоторая вершина па~о,' достижима из некоторой вершины о1енР;. Если граф — ациклический, то каждый класс эквивалентности состоит из одной вершины и само отношение достижимости является отношением частичной упорядоченности.
Ориентированный граф 6' называется трапзитивным замыканием 6, если отношение, соответствующее 6', является транзитивным замыканием отношения, соответствующего 6. Граф 6' получается из 6 добавлением ребра (в', в") (если оно отсутствует в 6) всякий раз, когда в 6 есть путь (о', ..., о") и и'чьи". Если 6'=6 (т. е.
все такие ребра есть уже в 6), то граф 6 изображает транзитивное отношение и сам называется транзитивным. Граф 6' определяет то же отношение транзитивности, что и исходный граф. Минимальный граф 6а, индуцирующий на множестве вершин г' то же отношение достижимости, что и данный ориентированный граф 6, т.е. граф с неуменьшаемым далее множеством ребер, называется базисным графом для графа 6. Если 6 — конечный граф, то базисный граф для него можно построить причем для ациклического графа единственным образом. В каждом классе эквивалентности вершин, порожденном отношением достижимости, вершины нумеруются произвольным образом и определяются ребра (оь огы) (1=1, ..., й, где й — число элементов класса) и (ам о1).
Таким образом, каждая вершина рассматриваемого класса достижима из остальных вершин этого класса, чего с меньшим числом ребер добиться нельзя, Пусть 1', и У; .— различные классы эквивалентности вершин графа 6 и в последнем есть ребро (оа, огх), где оиенУ;, оменР'.
Это ребро можно заменить ребром (е1ь ом), после чего параллельные ребра склеить. Действительно, в любом пути Ь(„.ои, ом...) его можно заменить участ- ком (пп, он.гл, ..., оьь огь опь пап ..., ом). Теперь в ациклическом подграфе 6, порожденном множеством первых вершин каждого класса эквивалентности, выбрасываются все ребра, замыкающие какой-либо путь. Г!ри этом для любой пары вершин (о', о"), удовлетворяющей отношению достижимости, в определенном выше графе 6 сохраняется путь Е(о', ..., о") максимальной длины, который в конечном ациклическом графе 6 существовал.
Действительно, если бы какое-либо ребро (оь и;+,) пути! было выкинуто, в графе 6 имелся бы более длинный путь Е'(о', ..., пь ..., о;+, „..., о"), в котором это ребро было бы заменено стягиваемым им путем. В графе 6е= 6 () ЦЯ~ (1 — класс эквивалентности для отношения достижимости) нельзя выкинуть ни одного ребра; при выбрасывании ребра (оп, п,л+,) нлн (онь оп) из цикла Я, или (оп, о; ~)ен6 конец его перестает быть достижимым из начала.
Цепи, неориентированные циклы. Любому ориентированному графу 6 соответствует неориентированный граф 6', в котором ребро (о', о") имеется тогда и только тогда, когда в исходном графе 6 есть ребро (о', о") или (о", о'). Цепи и циклы графа 6' называются также цепями и неориентироеанными циклами графа 6. Среди ориентированных графов можно выделить подмножество графов, для Рис. 4пп которых их неориентированные образы не имеют циклов, т. е.
являются деревьями или лесами. Таковы определенные в $4.3 ориентированные деревья, но нс только они. На рис. 4.15 изображен ориентированный граф без неориентированных циклов, не являющийся ориентированным деревом, хотя его неориентировапный образ — дерево. Неориентированный цикл ь(оо, о„...,оы ое) ориентированного графа 6 является либо ориентированным циклом 6, либо ориентированным циклом графа 6 с обратными направлениями ребер, либо, наконец, в нем существует такая вершина оь что (о~-ь о;)а=6, (онь о~)си6.
Здесь индексы рассматриваются по модулю й+1. Таким образом, когда ю'=Уг, то 1+1=0, а когда 1=0, то 1 — 1=й. 128 Назовем вершину пзенЬ положительной, если (оь нем) я ев6, н отрицательной, когда (ьч+ь ьч)ен6. Если все вершины неориентированного цикла Ь положительны, то это— ориеитнрованный цикл, если все они отрицательны, то это — ориентированный цикл в графе 6 с обратными направлениями ребер. В остальных случаях существует такая отрицательная в Ь вершина вь что предыдущая вершина положительна. Но тогда наши условия для вершины гн выполняются. Правильная нумерация. Пусть вершины конечного ориентированного графа занумерованы от 1 до н. Нумерация называется правильной на ребре (пь и;)ен6, если 1<1, и правильной на графе 6, если она правильна на всех его ребрах.
Правильная нумерация вершин графа 6 может сушествовать лишь в том случае, когда 6 — ациклическнй граф. Правильную нумерацию можно рассматривать как расширение отношения частичной упорядоченности, заданной на множестве Г вершин конечного ориентированного ацнкличсского графа, до отношении полной упорядоченности. Строится это расширение следующим образом. Пусть 6 — конечный ориентированный ациклическнй граф, и'<о" — соответствующее отношение строгой частичной упорядоченности. Если вершины о', ви не удовлетворяют ни отношению о'<и", ни обратному отношению п" <о', то к множеству истинных формул можно добавить одно из этих соотношений, например и'(и", и замкнуть это расширение отношения <': п~<'пз =— в«аз~/(о~< <п'Йо"<оз).
Когда выполняются отношения и,<'пз и пз<'пз, возможны три случая: 1) и, <пзйпз<пз, тогда в, <пз, т. е. и, <'пз,' 2) о~<пзйпз<п'Йп"<вз, тогда п~<п'Йп"<пз, т.е. п~< ('пз., 3) п~<п'Йв"<пзйпз<пз, тогда п~<п'Йп" <пз, т.е. в,< ('о,. Четвертый случай — п~(п'йп"<взйвз<п'йп"<вз невозможен.
По транзнтивпостн старого отношения < в этом случае в"<и'; что не выполняется по условию. Таким образом, новое отношение транзптивно. Оно антирефлексивно, так как выполнение отношений оз<'пз и пз<'п~ означает, что: 1) п,(пзйпз<п, — сочетание условий, невозможное изза антирефлексивности старого отношения <; 9 — 750 129 2) в!(ож'оэ(о', во(оь тогда по транзнтнвностн старого отношения вн(п', а это по условию не так; 3) п1<о', ам<ею о,(о, — так же, как н для второго случая, отсюда следует о"<о', 4) и!<о', нп <пю о, и'-н со<вы но н в этом случае по тра из нтнв ности отношен ня ( на < и'.
Продолжая, если нужно, этот процесс расширения отношения строгой частнчной упорядоченности, вследствие конечности числа вершин графа 6 через конечное число шагов получим отношение строгой полной упорядоченности 5, Для любых вершин и!, пз, различных между собой, будет выполняться одно н только одно нз условий ш(и, нлн оз)пь Для этого отношения есть единственная правнльная нумерация. Номер 1 получает вершина о', для которой выполняются все условня и'(и(о~о'). Существование этой вершины легко доказать — это начальная вершина ацнклнческого графа О, соответствующего нашему порядку. Номер 2 имеет всршнна, для которой выполняются условня цэ<п[эяб' (о'()оо)], начальная в подграфе б'~п' н т.
д. Такая нумерация правильна н для исходного отношения <. Длины путей, протяженности и расстояния между вершинами гра. фа уже были определены ранее. Часто рассматриваются более общие определения этих понятий. Пусть каждому ребру (о', о")шб поставлено в соответствие действительное число !(о', о") — его длина, Тогда длина любого пути й(о нн о!„,...,о! ) определяется как сумма длин э входящих в него ребер: ! (й) = ~2~ ! [о! "гь ) ' Эсн Расстоянием о(оь о!) между двумя вершинами о~ и о! графа называетсв нижняя грань длин йутей й(оь...,с!) с началом в первой и концом во второй из этих вершин; протяженностью д(эь о!) — верхняя гравь этих длин.
Считается, что длина пути (.е(о~), состоящего из одной вершины, равна О; если вершины о~ ц о! в графе 6 не связаны, то о(оь о!)=+ос, д(оь о;)= — со. Приведенные ранее определения длины пути, расстояния и протяженности являются частнымв случаями этого определения, когда длины всех ребер равны единице. Так как при изменении знаков длив !(э', о") всех ребер (о', о") на противоположные расстояния и протяткенности меняются местами с заменой знаков на противопо. ложные, достаточно исследовать свойства расстояний.
130 Если существует путь Е(иь.., иь, ..., и!), в котором некоторая вершина иь прцпадлежнт циклу 2(иь,...,ии) отрнцательной длины !'(О, то б(иь и;) = — со. Действнтельно, в этом случае путь Ет(иь ...,оь... ..., им ..., и,), состоящий вз отрезка (иь ..., и„) пути Е, и раз повторенного цикла л н отрезка (иь,..., о!) пути Е нмеет длнну |(Е) +4!', т.е. может оказаться меньше любого отрицательного числа. Если же в любом связывающем рассматрнваемые вершины пути нет вершин, прннадлежащнх циклам отрпцательной длины, то, выбросив нз таких путей циклы, получим прос~ые путн ве большей длнны. В конечном графе 6 количества таких путей конечно н нижняя грань нх длин достнгается. теорема 4.8. Расстояние г|(иь и,) между различными вершинами графа 6 удовлетворяет условию г|(иь и!) = (и! (гг(иь иь) + ("л и!)шо +|(иь, и!)).
Прн доказательстве будем считать, что ннжнпе грани достигаются (для конечных графов это всегда верно). Пусть (им и!)~и6 н Е(иь... ..., оь) — путь минимальной длины, соединяющий и~ с ию Добавив к нему ребро (им и~), получим путь Е'(иь..„ию о,), соединяющий и~ с и!. Следовательно, й(иь и!)~!(Е')=!(Е)+!(ил, и!)4 д(иь ил)+!(ил, о!), откуда й(иь и!) ~ |и| (г|(иь ил) -Ь!(иж и!)).
Если же Е(иь, (иг, и )«ао ,, их,ию ) — путь минимальной длины, соединяющий иг с ис (он не состоит нз одной вершины, так как июФи!), то Е'(иь .,., их) — путь, соеднняющнй иг н оп н о(иь и;) |(Е) = |(!.')+|(и„о!)~г((иь из)+ +|(ив и!)~ |п| (гг(иь иь)+!(им и,)). С) ( иг, и!)шп Если вершина о; нрняадлежнт какому-либо цнклу отрицательной длнны, то о(иь и~) = — со. В противном случае Ее(иг) — кратчайший путь с началом н концом и, н о(иь и~) -О. С) 4.5.
ГРАфы С ПОМЕЧЕННЫМИ ВЕРШИНАМИ И РЕБРАМИ Разбиение вершин графа на классы. Нередко приходится иметь дело с различиями между вершинами графа. Тогда последние разбивают на-классы. Каждый класс состоит из вершин, имеющих некоторое общее свойство. Свойства, определяющие разбиение вершин графов на классы, могут быть «графовымихч иметь данную степень, данное расстояние от фиксированной вершины — корня, данный ранг (в ориентированном графе), в двудольном графе вершины каждой доли составляют класс и т. д. В других случаях разбиение определяется свойствами объектов, описываемых при помощи графов.
Например, структурная формула химического соединения — это граф, в котором вершины соответствуют атомам молекулы соединения, ребра — валент- йе 13| ным связям, а классы состоят из вершин, соответствующих атомам одного и того жс элемента (рис. 4.16). Помеченные вершины. Пусть дано разбиение вершин графа на классы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
