XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 45
Текст из файла (страница 45)
Дугу называют инцидент«ой вершине е, если она заходит в е или исходит иэ е. Полустепенью захода вершины е называют число дд (е) заходяпцтх в нее дуг, а полусглепенью исхода вершины е — число Йб~(е) исходящих из нее дуг. Стпепень вершины е, обозначаемая дя(е), — это сумма полустепеней захода и исхода.
278 5. ТЕОРИЯ ГРАФОВ Для вершины о множество Г(е) = (х: х~-~е) называют множеством смежных с е вершин. Справедливо равен- ство День в неориентированном графе С вЂ” это последовательность вершин (конечная или бесконечная) со1 еы ю еь~ ' ~ такая> что е; ~ и,+1 для любого ю, если еьы существует.
(Под конечной последовательностью понимается кортеж вершин.) Для конечной цепи оо, ем ..., с„ число и (и ) О) называют длиноб цени. Таким образом, длина цепи есть число ее ребер, т.е. всех ребер, соединяющих вершины е; и еьы (( = О, и — 1) . Цепь длины 0 — это произвольная вершина графа. Говорят, что вершина е неориентированного графа С досгпижима из вершины и этого графа и обозначают и си" е, если существует цепь оо, ем ..., ее, такая, что и = во, с„= е (при этом говорят также, что данная цепь соединяет вершины и и с, которые называют концами целю).
Таким образом, задано Для вершины е множество Г(е) = (х: о -+ х) называют множеством преемников вершины е, а множество Г 1(е) = (х:х -+ е)— множеством иредшесгпвенников вершины е. Справедливы равенства 88 (е)=~Г(е)~, дя (о)=~Г (е)~. Путпь в ориентированном графе С вЂ” это последовательность вершин (конечная илн бесконечная) ео, ем ..., о„,..., такая, что с; -+ е;+1 для любого 1, если е;+1 существует. Для конечного пути со, ем ..., е„число и называют длиноб нрши (и ~ ~О). Тем самым длина пути есть число его дуг, т.е. всех дуг, которые ведут из вершины е; в вершину е;+1 (~ = = б,й1).
Путь длины 0 — это произвольная вершина графа. Говорят, что вершина с ориентированного графа С досгаижима из вершины и этого графа и обозначают и =~" е, если существует путь ео, ом .", еа такой, что и = ео, е = е„(при этом говорят, что данный путь ведет из вершины и в вершину с, называя первую вершину началом, а вторую — концом 279 5.1. Основные олрвдвлеювт и~" о отпношение достпизкилтостпи в неориентированном графе. Оно является рефлексивношранзитпивным замыканием отношения тч непосредственной достижимости. Отношение достижимости в не- ориентированном графе рефлексивно, симметпрично и тпранзитпивно, т.е.
является отпношенивм эквивалентпностпи. Если существует цепь ненулевой длины, соединяющая и и о, то пишут и ив+ о. Если необходимо явно указать длину цепи,то пишут и говорят, что существует цепь длины и, соединяющая и и о. Простпал цепь — это цепь, все вершины которой, кроме, быть может, первой и последней, попарно различны и все ребра попарно различны. Простую цепь ненулевой длины с совпадающими концами назы- вают циклом.
данного путпи). Таким образом, задано отпношение достпижимостпи =~' в ориентированном графе. Оно являетсл рефлексивно-тпранзитивным замыканием отношения -Ф непо- средственной достижимости. Отношение достижимости в ориентированном графе рефлексивно и транзитивно, но в общем случае не антписимметпрична если две вершины ориентированного графа достижимы одна из другой, то из этого вовсе не следует, что они совпадают. Таким образом, отношение достижимости в ориентированном графе есть отпношение предпорлдка. Если существует путь ненулевой длины, ведущий иэ и в о, то пишут и Ф+ 6.
Если необходимо явно указать длину пути, то пишут и говорят,что существует путь длины и, ведущий иэ и в о. Простпой путпь — это путь, все вершины которого, кроме, быть может, первой и послед- ней, попарно различны. Простой путь ненулевой длины, начало и конец которого совпа- дают, называют контуром. 280 3. ТЕОРИЯ ГРАФОВ Произвозьный путь ненулевой длины, начало и конец которо- го совпадают, будем называть замкнупзым пупзем. Произвольную цепь ненулевой длины с совпадающими конца мв, все ребра которой попарно различны, будем называть замкну2поб цепью. Неориевтированный граф, не содержащий циклов, называют аааклаческам графом. Ориентированный граф, не со- держащий контуров, называют бесконтпурным графом. Замечание 5.1. Требование, чтобы все ребра простой цепи неориентированного графа были попарно различными, существенно.
Если его снять, то цепь вида а, о, и, где а о, будет циклом, в котором одно и то же ребро (а, е) проходится дважды в противоположных направлениях, хотя та- С кую цепь естественно циклом не считать. Не будет эта цепь в соответствии с принятой терминологией и замкнутой цепью. В неориентированном графе на рис.
5.1 а 6 цепь анЬ~-~с>->дненс>->а является примером замкнутой цепи. Замечание 5.2. В общем случае в ориентированном графе пересечение множества преемников Г(е) вершины а и множества Г ~(а) ее предшественников будет не пусто, если есть петля (е, и): Г(о) П Г ~(о) 24 И. Пример 5.1.
Расмотрим неориентированный граф, изображенный на рис. 5.2. Он задается множеством вершин = (е1> а2> аз> а4> аз> аб> а7) и множеством неупорядоченных пар >(а1>о2)> >о1>оз)> (а2>аз)> >аз>о4)> (об>аб)) В этом графе последовательность вершин ед, оз, а4 есть простая цепь, а последовательность о4, оз, оз, ам оз, а4 — цепь, не являю- 281 5.1.
Оенонные определения Пример 5.2. Обратимся к ориентированному графу, изображенному на рис. 5.3. Он задается множеством вершин У (04 нг 4>3 >>4 65 об) и множеством дуг В= ((о1> Пг)> (Н1> ПЗ)> (Нг> о1)> (нг> нз)> (нг> я4)> (нз> о1)> (оз> Я4)> (Нб> об)> (Яб> о4)). В этом ориентированном гра фе последовательность вершин н4, о> ее ез, н4 есть простой путь, а последовательность вершин нм нг, нЗ, ЕМ ЕЗ, Н4 — ПУТЬ, НЕ ЯВЛЯЮЩИЙ- 1 ся простым, поскольку в нем, например, два раза встречается вершина ез, не служащая началом и концом пути. Последовательность вершин нз, ем иг, ез есть контур, а последовательность нз, ез, нг, н4, ез — замкнутый путь, но не О> О> О4 щаяся простой, поскольку в ней есть сон> е> е> впадающие ребра.
Последовательность о — — о вершин нз, нм 4>г> 4>4 не является цепью, поскольку в графе нет ребра (нг,4>4). о Последовательность нм нз, нг, н4 есть ЦИКЛ, а ПОСЛЕДОВатЕЛЬНОСтъ Е4, ЕЗ, НМ нг, Рис. 5.2 нз, е4 — цепь с совпадающими концами, но не цикл, поскольку эта цепь не является простой. Эта цепь не будет и замкнутой, так как в ней есть повторяющееся ребро (нз> Я4). Степени вершин графа следующие: бб(н4) = б8(нг) = 2, >>8(ез) = 3 >>я(>>4) = йя(4>з) = >>8(эб) = 1 Йя(4>г) = О.
ВеРшины н1> нг> нз> е4 попаРно Достижимы (ст нп еу, 4,У Е Е (1, 2, 3, 4)) и образуют класс эквивалентности по отношению достижимости. Для вершин нб и нб имеет место ез |=~* нб, и они также образуют класс эквивалентности. Заметим, что вершина 4>г, по определению, образует цепь длины О и эквивалентна по отношению достижимости только самой себе. 282 5. ТЕОРИЯ ГРАФОВ Отношение достижимости в неориентированных и ориентированных графах обладает следующим важным свойством. Теорема 3.1. Для любой цепи, соединяющей две вершины неориентированного графа, существует простая цепь, соединяющал те же вершины.
Для любого пути, ведущего из вершины и в вершину с ориентированного графа, существует простой путь, ведущий из и в о. ~ Проведем доказательство для неориентированного графа (для ориентированного графа доказательство проводится ана- логично). Пусть вершины и и с неориентированного графа таковы, что и ~=~* е. Если эти вершины являются концами цепи нулевой длины, то утверждение теоремы тривиально. Пусть исс+ о, т.е. существует цепь ненулевой длины, соединяющая и и с. Рассмотрим какую-либо из таких цепей (рис. 3.4). Обозначим ее С.
Если цепь С простая, то доказывать нечего. Пусть существует внутренняя (не совпадающая ни с одним из концов) вершина ю цепи С, которая повторяется в этой цепи, т.е. ис=~* ш~=~+ ш~=~' с. Это Рис. 5.4 и Ю с Ряс. б.б с ЗО Ю Рис. б.б контур, поскольку вершина е1, не являющаяся началом пути, встречается два раза. Последовательность вершин ем ез, е4, е6 не задает путь, так как в рассматриваемом ориентированном графе нет дуги (е4, е6). Полустепеви захода, полустепени исхода и степени у вершин следующие: у с1 и сз — ЙК (е1) = ЙК (ез) = 2 ЙК+(п1) = = ЙК~(~з) = 2 бК(~1) = дК(~з) = 4' у ~з — бК (~з) = 1, бК~(сз) = = 3, ЙК(сз) = 4; У ел — ЙК (е4) = 3, с1К (с4) = О, оК(с4) = 3; у сб <~К (иб) = О~ бК (пб) = 1~ сК(сб) = 1~ у сб бК (с6) = 1, бК+(е6) = 1, бК(с6) = 2 Ф 5.1. Осяовяые опрелелеяяя 283 значит, что вершина ш содержится в некоторой цепи С' ненулевой длины (подцепи цепи С) с совпадающими концами (рис. 5.5). Удалим все вершины и ребра цепи С', кроме вершины ш (служащей ее началом и концом одновременно).
После этого получим новую цепь См соединяющую вершиы и и о (рис. 5.6), в которой число повторений вершины ы будет по крайней мере на единицу меньше, чем в цепи С. Если цепь С~ просты, то утверждение доказано. В противном случае поступаем с ней так же, как и с цепью С. В силу конечности множества вершин и ребер графа после конечного числа шагов получим простую цепь, соединяющую вершиы и и е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
