В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 53
Текст из файла (страница 53)
Рассмотрим отдельно два случая. 4) В 6 нет ГЯ-путей. Возьмем какие-либо две вершины — одну в Я, а другую — вне Я. В сильном орграфе 6 есть контур Я', содержащий этн две вершины и потому Рис. 65.2 Рнс. 65.3 отличающийся от Я. Эти два контура имеют ровно одну общую вершину, скажем, ц„иначе в 6 был бы КЯ-путь. Пусть теперь и„+~ и и — вершины, непосредственно следующие за о в контурах Я и Я' соответственно (рис. 65.2) .
Так как в орграфе 6 яет $'Я-путей, то вершина о не смежна ни с одной из вершин, входящих в Я и отличных от о . По той же причине для любой вершины и ~н ~ Р6~(Л0 и) верно неравенство !Е(и, (и„~ь о))) <2. Следовательно, для несмежных вершин и и и,1 имеем бени+ йен иа+т = Х (й(и, (и„+и и)) ~ + иеуе,юа+1 + Х ~ Е(и~ (иа-~-ы и)) ~ ~< ие ко' (увью -(2+ 2(й 1))+ 2(п — й — () = 2и — 2 что противоречит условию теоремы (здесь первая сумма учитывает дуги, соединяющие вершины и„д и и с вершинами нз ГЯ, а вторая — дуги, соединяющие и ы и и с остальными вершинами графа).
2) В орграфе 6 есть ГЯ-пути. Выберем среди них путь =(оа~ иь ип . ~ ио паы) 288 с минимальным у (см. рис. 65.3). Из максимальности контура о' следует, что ( ) 1. Определим р как максимальное среди таких чисел й что 1 « 1 « "( и в С есть (имен и )-путь Р', для которого = УС ~(иае' ° °, иае1 — 1) (возможно, р = 1 и тогда Р' =(иа+„и„ел+и ..., га) ) .
Таким образом, !ИР'! = й — (+ 6. Так как Р 0 Р' также является контуром, из максимальности ъонтура 8 вытекает, что р « "(. Из выбора числа р следует, что в С нет (о„„ь га)-пути с множеством вершин УР 0 (и„ее), так что в силу леммы 65.4 вершина о„ее соединена с Р' не более чем й — (+ р+ 1 дугами.
Пусть Р" =(о„.„г иа,ьеь ° ., иа). Так как контур Я максимален, то в С нет (г„„.н и„)-пути с множеством вершин гр" 0 иь Из леммы 65.4 теперь следует, что вершина и1 соединена с Р" не более чем й — у+ 2 дугами. Из минимальности числа ( вытекает, что и| не смежна ни с какой вершиной и„ем 1 «е «(, и что для любой вершины и = — РС~(КЯ 0 и1) выполняется неравенство (Е(и, [ин иа,,е)) ! «2. Учитывая вышесказанное, получаем для несмежных вершин и1 и иа+е дели -!- 6ец иатз = Х ! Ь'(и, (и1 оа+З)) ! + еегз' лата ! Е (и, (иы гата)) ! = иеуо' (тз е ] )Н(, Ур ))+ !Е(и„рЯ рр )!+ !Ь(га з, рр)!+ + !Р( р~ Ир')! ! ~л !К (и, (и,, оа+з))! чего; (гя~.'чл) Учитывая полученные выше соотношения, а также то, что !РС~(гЯ 0 и1) ! = и — й — 1, !УРА'! = "( — р — 1 и в графе могут существовать дуги вида (о ее, иа+е), (иа„о и +е), 1 «е « "(, получаем 6ея и, + 6ея и„„е «(й — у+ 2)+ О+(й — "(+ (3+ 1)+ + 2(( — ~ — 1)+ 2(н — й — 1) = 2и — 1 — ~, что противоречит условию теоремы.
ч! 19 в л. нмеллчее и лр, 289 Очевидно С л е д с т в и е 65,5. Сильный орграф порядка и бев петель и параллельных дуг, степень каждой вершины которого не льеььее и, имеет гамильтонов контур. 5 66. Пути Пусть М = (Рь Рг, ..., Рь) — какое-либо множество путей орграфа 6, попарно не имеющих общих вершин. Если множества т'Р< вершин этих путей составляют разбиение для Р'6, т. е. РС = )Рь 0 РРг 9 ... 9 РРь то множество путей М называется разбиением орграфа 6 на пути. Минимальное число 1 путей, составляющих разбиение орграфа С, обозначим через 1(6). Ниже фигурируют понятия числа независимости ао(6) и хроматического числа )((6) орграфа 6, которые для ориентированных графов определяются так же, как и для неориентированных, т.
е. сьо(6)=по(Сь), Х(6) = х(Сь). Теорема 66.1 (Т. Галлаи и А. Милгрэм, 1960 г.). Для любого орграфа 6 верно неравенство 1(6)~ сьо(6). Фиксируем некоторое разбиение (1) орграфа 6 на пути. Пусть ьо'(М)= (ан аь ..., а,), аьонРч — множество начальных вершин этих путей. Докажем более сильное утверждение: существует такое рагбиеььие ЛХ' орграфа 6 на пути, что Аь(М')': — Аь(М), !М'! ( ао(6). > Доказательство последнего утверждения проведем индукцией по и = ~61. Утверждение очевидно при и = = 1, 2. Пусть и) 2 и утверждение верно для орграфов, порядки которых меньше и. Вначале покажем, что, не ограничивая общности, можно считать 1М~ ( сьо(6)+ 1.
В самом деле, пусть ~М! > ~ сьо(С)+ 2. Рассмотрим орграф Сь = 6 — РРс Очевидно, что сьо(Сь) ~ ао(6). По индуктивному предположению существует разбиение Мь орграфа Сь на пути с ьт'(Мь) — ьу(М) и !ЛХь! (сьо(Сь)<ао(6). Но тогда М'= = Мь 0 Рь — разбиение орграфа С с ьу(М') — Аь(М) н 1М'~ ~ ао(6)+ 1.
Поэтому всегда можно считать, что !М! ~ ао(6)+ 1. 290 Пусть теперь (М! = ао(6)+ 1. Тогда множество |ч(М) = (а|, аг, ..., а,) не является независимым, т. е, в нем есть хотя бы одна пара смежных вершин. Предположим, что (а|, аг)~ АС. Если путь Р| состоит из единственной вер|пины а|, то объединив Р| и Рг в путь (а|, аг, ...), получим нужное разбиение.
Если же путь Р| =(а|, Ь|, ...) имеет более чем одну вершину, то рассмотрим орграф 6| = 6 — а|. По индуктивному предположению существует такое разбиение М| орграфа 6| на пути, что (М|! ( ио(6|) < ао(6) и А|(М|) — (Ь|, аг, аг, ..., а,!. Если Ь| |нЛ'(М|), то М получим из М|, добавив вершину а| к пути, начинающемуся в Ь|. Аналогично моя|но поступить и тогда, когда аз гн шд|(М|).
Если же Ь| ФХ(М|) и аз ФА|(М|), то М' = = М| 0 ((а|) ). »! Из теоремы 66.1 вытекают два валсных следствия. Орграф 6 называется транзитивным, если истинна импликация ((к, у)~ АС и (у, г)~АС)=»-(г, г)ив АС. С л е д от в не 66.2 (теорема Дилворта, 1950 г.). Если орграф 6 транзитивен, то 1(6) = ио(6) . > Согласно предыдущей теореме !(6) ( ао(6). Но две вершины транзитивного орграфа, принадлежащие одной цепи, смежны, поэтому ао(6)~1(6). Итак, !(6)= = ао(6). 4 С л е дс т в и е 66.3. В каждом турнире существует гам л.ьтонов путь. > Поскольку любые две вершины произвольного турнира Т смежны, то ао(Т) = 1.
Поэтому существует цепь Р, содер|кащая все вершины турнира Т. 0 Для сильных турниров верно следующее более общее утверлодение. Т е о р е м а 66А. Пусть Т вЂ” сильный турнир порядка п. Тогда для любой его вершины и и для любого числа й, 3 < Ь ( и, в Т есть контур длины Ь, содержащий вершину и. > Пусть Я(и) и Р(и) — множество всех тех вершин и и, соответственно, и турнира Т, для которых (и, и)ги ы АТ и (ю, и)гв АТ.
Оба эти множества не являются пустыми, поскольку орграф Т сильный. По той же причине существует хотя бы одна дуга (о, и|), идущая из Я(и) в Р(и) (рис. 66.1). Следовательно, вершина и лежит на контуре длины 3. 19» 291 Далее воспользуемся ипдукцией по й. Пусть вершина и входит в контуры всех длин от 3 до й, где й ( и. Покажем, что оиа входит в коктур длины й+ 1. Пусть С=(гь о1, ..., о,), ос=о, = и,— контур длипы й. Предположим, что для некоторои вершины 10, не Ы входящей в этот контур, существуют такие дуги (й, х) и (у, 10), что х УС и у1и 1и УС. Тогда в Сесть такие две смежвые вершины и1 И Оы1, ЧтО (ич Ш) И (и1, О,Э1) — ДУ- ги турнира Т (рис. 66.2) . Следовательио, вершина и вхои~ дит в контур 5М ( 110 о!~ .
пь Ой-1~ ° ° ~ ПА) ~ Пс Пь Пв длины й+ 1. Если же указанной выше вершины л1 нет, то миожество вершин турнира Т, не входящих в контур С, можно разбить па две части Я(С) и Р(С) так, чтобы для любых вершин а 1и Я(С), Ь = — Р(С) и о 1и С выполнялись условия (и, а) ~ АС и (Ь, и) = — АС. Так как орграф Т сильный, то Я(С) и Р(С) не пусты и существует дуга, идущая из 0Ы1 Рис. 66Л Рис. 66.2 Рис. 66.3 некоторой вершины а~Я(С) в некоторую вершину Ьси сиР(С) (рис.
66.3). Таким образом, вершина и входит в контур С' =(ис, ц Ь, ог,, оь), оо = ои = и, длины й+ 1. <~ Очевидно С л е д с т в и е 66.5, Сильный турнир гамильтонов. Заметим, что предыдущее следствие вытекает также из теоремы 66.3. 292 Т е о р е м а 66.6 (Т. Галлаи и Б. Руа, 1967 г.) . Если й — максимальная длина путей в орграу7е 6, то 1~(6)~ <й+1. Г. Обозначим через В такое минимальное относительно включения подмножество в А6, что орграф 61 = 6 — В пе имеет контуров. Для любой вершины о определим ~(о) как число вершин пути в орграфе 61 с началом в о, имеющем максимальную длину. Приписав каждой вершине о цвет г(о), получим раскраску орграфа 6 не более чем й + 1 цветами.
Остается доказать, что зта раскраска правильная, т. е. что г(и)чь ~(о) для любых двух смежных вершин и и и. Но если (и, о) ~ А6п то г(и) ) 1(о). Если же (и, о) - =В, то 6~+(и, о) имеет контур. Поэтому в 61 существует (о, и)-путь и, следовательно, г(о)) г(и). Итак, доказано, что т(6)< й+ 1. 2 9 67. База и ядро Пусть 6 — ориентированный граф, а  — такое подмножество его вершин, что любая вершина из т'6~В достижима пз какой-либо вершины, принадлежащей В.
Если, к тому же, множество В минимально относительно включения среди всех подмпокгеств вершин с описанным свойством, то оно называется базой орграфа С. Очевидно, что в любом орграфе существует база и что никакие две вершины базы не соединены маршрутом. Поскольку вершины с нулевыми полуступенями захода не достижимы ни из каких вершин„то все они принадлежат базе. В бесконтурном орграфе база состоит только из таких вершин. Для поиска базы в орграфе 6, содержащем контуры, рассмотрим его конденсацию 6г, не имеющую контуров согласно утверждению 63.3.
Сильные компопенты орграфа 6, в которые не входят дуги из других сильных компонент, соответствуют в орграфе 6* вершинам с нулевыми полустепепями захода. Назовем такие сильные компоненты базовыми. Все вершины каждой сильной компоненты взаимно достижимы и любая вершина небазозой компоненты достижима из любой вершины некоторой базовой компоненты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
