Задача остовных деревьев в k–связном графе (стр. 5 из 10)
1) степени вершин 2–связного графа больше единицы;
2) если графы G1 и G2 2–связны и имеют не менее двух общих вершин, то граф G1 
G2 также 2–связен;
3) если граф G 2–связен и Р–простая цепь, соединяющая две его вершины, то граф G P также 2–связен;
4) если вершина v не является точкой сочленения связного графа, то любые две его вершины соединены цепью, не содержащей v; в частности, в 2–связном графе для любых трех несовпадающих вершин a, b, v имеется (a, b)–цепь, не проходящая через v.
Этими свойствами мы будем пользоваться без каких–либо пояснений и дополнительных ссылок на них.
Теорема 5.1пусть G–связный граф и |G|>2. Тогда следующие утверждения эквивалентны:
1) граф 2–связен;
2) любые две вершины графа принадлежат простому циклу;
3) любая вершина и любое ребро принадлежат простому циклу;
4) любые два ребра принадлежат простому циклу;
5) для любых двух вершин a и bи любого ребра е существует простая (a,b)–цепь, содержащая е;
6) для любых трех вершин a,b,c существует простая (a,b)–цепь, проходящая через с.
1)
2). Пусть a и b–две вершины графа G. Рассмотрим множество всех простых циклов графа G, содержащих а. Обозначим через U множество всех вершин, входящих в эти циклы. Ясно, что U 
Ø. Действительно, простой цикл, содержащий а, можно получить, объединить два ребра ax и ay (x≠y) и простую (x, y)–цепь, не проходящую через а (существующую согласно свойству 4)). Предположим, что b 
U, и положим 
=VG\U. Поскольку граф G связен, то в нем найдется такое ребро zt, что z 
U, t 
(рис. 5.1). Пусть S–простой цикл, содержащий a и z. Так как G – 2-связный граф, то в нем имеется простая (a, t)-цепь P, не содержащая z. Пусть v – первая, считая от t, вершина, входящая в S, т.е. (t, v)-подцепь цепи P не имеет с S общих вершин, отличных от v. Теперь легко построить простой цикл, содержащий a и t. Он получается объединением (v, z)- цепи, проходящей через а и являющейся частью S, с ребром zt и (t,v)-подцепью цепи Р (на рис. 5.1 этот цикл показан пунктирной линией). Следовательно, t 
; но это противоречит выбору ребра zt. Таким образом, =Ø, т.е. a и b лежат на общем простом цикле.2)
3). Пусть а–вершина и zt–ребро графа G. По условию G содержит цикл S, проходящий через вершины a и z. Не теряя общности будем считать, что zt S. Если при этом окажется, что S проходит через вершину t, то требуемый цикл строится очевидным образом. Пусть S не проходит через t. Тогда рассмотрим простой цикл S', проходящий через вершины t и a. Такой цикл, по условию, существует. Частью этого цикла является простая цепь Р, соединяющая t с некоторой вершиной v S. Цепь Р можно выбрать так, чтобы 
VP 
VS={v}. искомый цикл теперь строится точно так же, как в предыдущем пункте.
3)
4). Пусть ab и tz–два ребра графа G. По условию G имеет простые циклы S и S', первый из которых содержит ab и z, а второй – ab и t. Далее искомый цикл строится так же, как в предыдущих пунктах.4)
5). Пустьa,b VG, tz EG. Будучи связным, граф G содержит простую цепь P=(a,x,…,b). Согласно утверждению 4) а графе G есть простой цикл S, содержащий ребра ax, tz. Легко видеть, что в объединении S P имеется требуемая цепь.5)
6). Пустьa,b,c VG, cd EG. По условию в графе имеется простая (a,b)–цепь, проходящая через cdи, следовательно, содержащая c.6)
1). Пусть v VG. Покажем. Что граф G – v связен, т.е. любая a,b его вершин соединена цепью. Действительно, согласно утверждению 6) в графе G имеется простая (v,b)-цепь, которая, очевидно, не проходит через v и, следовательно, является (a, b)-цепью и в графе G – v. Доказано.Если в формулировке теоремы 34.1 заменить всюду слова «простая цепь» и «простой цикл» соответственно на слова «цепь» и «цикл», то получим аналогичную теорему о 2–реберно–связном графах.
Как отмечалось выше, при решении многих задач на графах достаточно уметь решать эти задачи для каждой 2–связной компоненты графа. Поэтому представляет интерес взаимное расположение 2–компонент в графе.
Максимальные относительное включения элементы множества связных подграфов графа G, не имеющих точек сочленения, называются его блоками. Таким образом, каждый блок графа либо 2–связен, либо совпадает с К2 или К1 (граф К1– блок тогда и только тогда, когда он является связной компонентой). Связный граф без точек сочленения также называют блоком.
Множество вершин блока будем называть блоковым множеством.
Например, граф, изображенный на рис. 5.2, содержит пять блоков Bi(i=1,2,3,4,5) (они обведены пунктирными линиями). Среди этих блоков В1, В2 и В3 –2-связные графы, а каждый из двух оставшихся является ребром.
Утверждение 5.2.Любые два блока графа имеют не более одной общей вершины. В частности, всякое ребро графа входит только в один его блок.
Утверждение 5.3.Если блок графа содержит вершины a и b, то он содержит и всякую простую (a, b)-цепь этого графа.
Эти утверждения непосредственно следуют из перечисленных в начале параграфа свойств 2–связных графов и теоремы 5.1.
Следствие 5.4.Система блоковых множеств графа является покрытием множеств его вершин. Каждая пара блоковых множеств либо не пересекаются, либо имеют единственную общую вершину, и эта вершина является точкой сочленения графа.
Следующая конструкция дает представление о структуре графа «с точностью до блоков». Пусть В=В{Bi} и С={ci} – соответственно множества блоков и точек сочленения графа G. Сопоставим с G граф bc(G), у которого B C – множество вершин и {Bici: B B, ci C, ci Bi} – множество ребер. Тем самым, ребра двудольного графа bc(G) указывают на принадлежность точек сочленения блоками. На рис. 5.3 представлены графы G и bc(G).
Утверждение 5.5.Если граф G связен, то bc(G)–дерево.
Доказательство:
Очевидно, что из связности графа G вытекает связность графа bc(G).
Предположим, что bc(G) содержит цикл С. Пусть этот цикл имет вид С=(c 
, b ,c 
, b ,…,c 
,b ,c ). Каждый из блоков B 
содержит (с 
,с 
)- цепь и объединение этих цепей дает простой цикл в графе G. Обозначим этот цикл через С'. Ясно, что С' содержит по крайне мере две вершины каждого из блоков B . Поэтому из утверждения 34.3 следует, что цикл С' должен содержаться в каждом их этих блоков. Последнее означает, что каждая пара блоков B
имеет не менее |C'| 
3 общих вершин. Получаем противоречие с утверждением 5.2. доказано.