В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 26
Текст из файла (страница 26)
с 1) = 2). Пусть а и Ь вЂ” дзе вершины графа С. Рассмотрим мнояшстзо всех простых циклов графа С, содержащих и. Обозначим через П множество всех вершин, входящих в эти циклы. Ясно, что Гчь 8. действительно, простой цикл, содержащий а, можно получить, объединив два ребра ах и ау (хну) и простую (х, у)-цепь, не проходящую через а (существующую согласно свойству 4) ). Предположим, что Ь Ф Г, и положим Г~ 'т'С~У. Поскольку граф С связеп, то в нем найдется такое ребро гг, что з сг Г, 1ш Г (рпс. 34.1). Пусть Я вЂ” простой цикл, содержащий а и г.
Так как С вЂ” 2-связный граф, то в нем имеется простая (а, 1)-цепь Р, не содержащая г. Пусть и — первая, считая от 1, вершина, входящая в Я, т. е. (г, о)-подцепь цопп Р по имеет с 3 общих вершин, отличных от о. Теперь легко построить простой цикл, содержат,ий а и й Оп иолу зае;си, бьедчпением (о, г)-пепи, проходящей |срез а и ясллкпцейся частью о', с реором гЕ п (1, о)-подцепыо цепи Р (на рпс.
34.1 этот цикл показан пунктирной линией). Следовательно, 1~в П; но это протпворе шт гыбору ребра гЕ. Таким ооразом, Г = О, т. е. а п Ь лежат па общем простом цикле. 2) ~ 3). Пусть а — вершина и з1 — ребро графа С. По условию С содержит цикл о', проходящий через вершины а и г. Не теряя общности будем считать, что г1Ф 138 ФЯ.
Ксли при этом окажется, что Я проходит через вершину «, то требуемый цикл строится очевидным образом, Пусть Я не проходит через й Тогда рассмотрим простой цикл Я', проходящий через вершины ~ и а. Такой цикл, по условию, существует. Частью этого цикла является простая цепь Р, соединяющая «с некоторой вершиной о~Я.
Цепь Р можно выбрать так, чтобы УР й Рис. 34Л П ИЯ = (в). Искомый цикл теперь строится точно так же, как в предыдущем пункте. 6) =. 4).,Пусть аЬ и ~з — два ребра графа С. По условию С имеет простые циклы Я и Я, первый из которьтх содержит аЬ и з, а второй — аЬ и й Далее искомый цикл строится так же, как в предыдущих пунктах. 4)~ 5). Пусть а, Ь «н «'С, ~я яЕС.
Будучи связным, граф С содержит простую цепь Р =(а, л, ..., Ь). Согласно утверждению 4) в графе С есть простой цикл Я, содержащий ребра ах и «з. Легко видеть, что в объединении Я 0 Р имеется требуемая цепь. 5)~ 6). Пусть а, Ь, се '«'С, «НАЕС. По условию в графе имеется простая (а, Ь)-цепь, проходящая через с«« и, следовательно, содержащая с. 6)~- 1). Пусть и ~ ИС. Покажем, что граф С вЂ” о связен, т.
е. любая пара а, Ь его вершин соединена цепью. Действительно, согласно утверждению 6) в графе С имеется простая (о, Ь)-цепь, проходящая через вершину а. Эта цепь содержит (а, Ь)-подцепь, которая, очевидно, не проходит через о и, следовательно, является (а, Ь)- цепью и в графе С вЂ” п. 0 Коли в формулировке теоремы 34.1 заменить всюду слова «простая цепь» и «простой цикл» соответственьто па слова «цепь» и «цикл», то получим аналогичную теорему о 2-реберно-связных графах.
Как отмечалось выше, при решении многих задач на графах достаточно уметь решать ети задачи для каждой 139 2-связной компоненты графа. Поэтому представляет интерес взаимное расположение 2-компонент в графе. Максимальные относительно включения элементы мноя«ества связных подграфов графа С, не имеющих точек сочленения, называются его блоками. Таким образом, каждый блок графа либо 2-связен, либо совпадает с Кг или с К1 (граф К1 — блок тогда и только тогда, когда оп является связной компонентой).
Связный граф без точек д, б Рис. 34.2 сочленения также называют блоком. Множество вершин блока будем называть блоковым мнохсеством. например, граф, изображенный на рис. 34.2, содержит пять блоков В, (( 1, 5) (они обведены,пунктнрнымп линиями). Среди этих блоков Вь Вг и Вг — 2-связные графы, а каждый из двух оставшихся является ребром. Утверждение 34.2.
Любые два блока графа имеют не более одной, общей вершины. В частности, всякое ребро графа входит только в однн его блок. Утверждение 34.3. Если блок графа содерхсит вершины а и Ь, то он содержит и всякую простую (а, 6)-цепь этого графа. Утверждение 34.4. Если вершина о входит более чем в один блок графа С, то о — точка сочленения этого графа. Зги утверждения непосредственно следуют из перечисленных з начале параграфа простейших свойств 2-связных графов и теоремы 34.1. Следствие 34.5.
Система блоковых мнолсеств графа является покрьгтием мнолсества его вери«иьь Каждая пора блоковых мнохссств либо не пересекается, либо имеет единственную общую веришну, и эта вершина является, точкой сочленения графа. Следующ ~я конструкция дает предста".ление о структуре графа «с точностью до блокова. Пусть В (В;) и С = (с,) — соою етственпо множества блоков и точек сочлене|шя графа С. Сопоставим с С граф бс(С), у которого В Б С вЂ” множество вершин и (В,с,: В, ы В, с; ~ С, 140 с~иВ,) — множество ребер.
'Тем самым, ребра двудольного графа Ьс(6) указывают на принадлежность точек сочленения блокам. На рис. 34.3 представлены графы 6 и Ьс(6). Утверждение 346, Ясли граф 6 свявен, то Ьс(6) — дерево. > Очевидно, что нз связности графа С вытекает связность графа Ьс(С). Предположим, что Ьс(С) содержит Ь«Я Рнс. Зьз цикл С. Пусть этот цикл имеет вид С = (с;,, Ь;, с;,, Ь;, ..., стп Ь«и с; ).
Каждый из блоков В; содержит (с,, с1„+,)-цепь и объединение этих цепе1«дает простой цийл в графе С. Обозначим этот цикл через С'. Ясно, что С содержит по крайней мере две вершины каждого из блоков В;ы Поэтому из утверждения 34.3 следует, что цикл С должен содержаться в каждом из этих олоков. Последнее означает, что каждая пара олоков В«ь имеет не менее )С') ~ 3 общих вершин. Получаем противоречие с утверждением 34.2. 0 Граф Ьс(С) называется Ьс-деревом связного графа 6. Блоки графа С, соответствующие концовым вершинам его Ьс-дереза, называются иониевыми блоками. Похожее представление графа можно получить, по- реоерпо-2-связные подграфы, т.
е. максимальные связные подграфы, пе содержащие мостов. Такие подграфы навьи:ают листалпи Не останавливаясь на деталях, заметкм следующее. Кая.— дая вершина графа порядка и ) 1 принадлежит в точности одному листу и кан«дое ребро, не язлн|ощееся мостом, входит только в один лист. Таким образом, граф состоит пз листов и мостов, соединяющих некоторые нз них. Для описания строения графа «с точностью до листова можно ввести граф, аналогичный графу Ьс(С). Вершины такого графа биективно соответствуют листам 1И графа 6 и две его верппшы соединены ребром в том и только в том случае, когда соответствующая пара листов в С соединена мостом. Можно показатвч что введенный таким образом граф является деревом, если исходный граф связен.
На рис. 34.4 граф С имеет 5 листов Еп Ег, Ег, 5е Ег и 4 моста, а граф С' показывает, как связаны между собой листы графа С. Приведем некоторые результаты о трехсвязных графах, которые будут использованы в главе «Планарностьз. Д1 дг ц Рвс. 34.4 Пусть 6 — связный граф, Н вЂ” некоторый его подграф. Простую открытую цепь оь ом ..., он 1г ~ 3, графа С назовем Н-цепью, если выполняются условия о, и Ъ'Н, о,~н Ъ'Н, ос Ф ЪН, 4 = 2, й — 1.
Ребро е = ио графа С также будем называть Н-цепью, если и ~н ЪН, о~и Ъ"Н, е ФЕН. Лемма 34.7. Пуста С вЂ” двусвязный граф. Тогда для всякого его подграфа Н, содержащего более одной вершиньь и отличного от 6, существует Н-цепь графа С. д' Если Н вЂ” останный подграф, то любое ребро графа С, не входящее в ЕН, служит Н-цепью. Пусть подграф Н не является остовным. Рассмотрим три попарно различные вершины и е Ъ"Н, о е ЪН, ш Ф Ф Ъ'Н.
По теореме 34.1 в графе С есть простая (и, о)- цепь, проходящая через ш. Очевидно существование подцепи этой цепи, являющейся Н-цепью графа С. 0 Е1иже для и, о ~н ЪтС положпм С„„С вЂ” и — о. Теорема 34.8. Во всяком 3-связном графе С есть такое ребро ио, что граф 6„, нв имеет точек сочленения.
> Если ~6| и = 4, то утверждение теоремы очевидно. Поэтому будем считать, что и ) 5. Предположим противное, т. е. что для любого ребра ио ~и ЕС граф 6„, 142 имеет хотя бы одну точку сочленения. Тогда из 3-связности графа 6 следует, что при любом выборе ребра ни си ~ ЕС граф 6„, обладает следующими свойствамн (рис. 34.5): 1) если а — висячая вершина графа С „то аи ~ ЕС, лияЕС; 2) всякий висячий блок графа 6 ., не являющийся ребром, содержит такую пару вершин с и с), отличных от точек сочленения графа С„„что ис я ЕС, ис) си ЕС; 3) всякий блок графа С„„имеющий ровно две точки сочленения и отличный от ребра, содержит такую вершину 1, не являющуюся точкой сочленения графа 6 „, что и) ~ ЕС или в)~ ЕС, и с Обозначим череа В„, максимальный по числу вершин блок графа С„„а через 1„, — число вершин в этом блоке. Теперь выберем ребро Рве. 54.5 нн так, чтобы число 1„„было наибольшим.
Покажем, что в этом случае 1„„~ 3. Пусть 1„„= 2 и а — висячая вершина графа 6„„(являющегося деревом). Так как и ~ 5, то существует ребро ссй и ЕС„„, с зь аи д ти а. Из свойства 1) вытекает, что в графе С,с существует цикл (и, а, и, и), т. е, 1,с ) г„„. Получено противоречие, следовательно, г„. > 3. Через Р„обозначим Ьс-дерево графа 6„, и рассмотрим следующие случаи. 1. Дерево Р . не является цепью, Выберем в атом дереве цепь, соединяющую пару висячих вершин и проходящую через вершину, соответствующую блоку В„, Этой цепи соответствует последовательность Вь ..., В, блоков графа 6 „, среди которых содержится блок В „причем блоки В1 н В, являются висячими (рис. 34.6).
Пусть В' — произвольный висячий блок графа 6„., отличный от В~ и В,. Из свойств 1) и 2) вытекает существование таких отличных от точек сочленения графа С„„вершин асман Ь~ УВю с~ $'В', что исснЕС, га ~ Е6, иб ~ ЕС. Тогда в графе 6„, вершины множества г () ИВ; 0 н входят в один блок и, следовательно, с „- $=1 ( 1,. Последнее противоречит выбору ребра ии. 2.
Дерево Р, — цепь и В „— блок графа 6„„, по яэ- 143 ляющийся висячим. Пусть В„ ..., Ве — последовательность всех блоков графа 6, причем блоки В1 и В, — висячие, В;ПВы,ч~И (1=1, р — 1), В„„=В, (1<й<р) (рис. 34.7). Согласно свойству 3) найдется вершина Ь ш ~ ГВ „отличная от точек сочленения графа С„„, смежная с и пли с и. Пусть иЬ ~н ЕС. Согласно свойствам 1) и 2) существуют такие отличные от точек сочленения Рис. 34.7 Рас.
34.6 графа С„„вершины а я ГВь с ш 1'В, что иа я ЕС, ис ш ~н ЕС. Легко видеть, что в графе 6„, имеется блок, содер- а жащий все вершяны множества О ИВ; () и. Поэтому Зст 1„, ) („„ и снова получаем противоречие. 3. Дерево Р„„ — цепь и В„„ — висячий блок графа С„.. Если граф С„„содержит такое ребро ху, что РВ . й П (х, у) = Ы, то, используя свойство 2), легко показать, что в графе С есть блок, содержащий множество вершин ГВ„„0 (и, и), а, значит г„„< 1„. Так как В„„— висячий блок графа С„„, то последнее означает, что граф 6„„ состоит из блоъа В„„и ребер аЬь аЬм..., аЬ, (рис, 34.8).
Из 3-связности графа С следует, что граф 6 — а не имеет точек сочленения. Поскольку в графе 6 — а вершина Ь| смежна только с вершинами и и и, а ии ~н ЕС, то граф С~а также не имеет точек сочленения, что противоречит 1 предположению. Таким образом, показано, что во всяком 3-связном графе 6 существует такое ребро ии, что граф 6 . не имеет точек сочленения. <( 144 Рас. 34.8 8 35. Теорема Менгера Из теоремы 34.1 следует, что граф 2-связен тогда и только тогда, когда любые две его несовпадающие вершины а и Ь соединены парой простых (а, Ь)-цепей, не имеющих общих вершин, за исключением а и Ь. Аналогичный критерий й-связности справедлив при произвольном Й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
