Задача остовных деревьев в k–связном графе (стр. 6 из 10)
Граф bc(G) называется bc–деревом связного графа G.
Блоки графа G, соответствующие концевым вершинам его bc–дерева, называются концевыми блоками.
Похожее представление графа можно получить, положив в основу его максимальные реберно-2-связные подграфы, т.е. максимальные связные подграфы, не содержащие мостов. Такие подграфы называют листами. Не останавливаясь на деталях заметим следующее. Каждая вершина графа порядка n>1 принадлежит в точности одному листу и каждое ребро, не являющееся мостом, входит только в один лист. Таким образом, граф состоит из листов и мостов, соединяющих некоторые из них. Для описания строения графа «с точностью до листов» можно ввести граф, аналогичный графу bc(G). Вершины такого графа биективно соответствуют листам графа G и две его вершины соединены ребром в том и только в том случае, когда соответствующая пар листов в G соединена мостом. Можно показать, что введенный таким образом граф является деревом, если исходный граф связен.
На рис. 5.4 граф G имеет 5 листов L1, L2, L3, L4, L5 и 4 моста, а граф G' показывает, как связаны между собой листы графа G.
Приведем некоторые результаты о трехсвязных графах, которые будут использованы в главе «Планарность».
Пусть G–связный граф, H–некоторый его подграф. Простую открытую цепь . графа G назовем H–цепь, если выполняются условия
v1 
VH, vk VH, vi 
VH, i= 
ребро e=uv графа G также будем называть Н–цепь, если u VH, v VH, e EH.
Лемма 5.6. Пусть G–двусвязный граф. Тогда для всякого его подграфа Н, содержащего более одной вершины и отличного от G, существует Н–цепь графа G.
Доказательство
Если Н–остовный подграф, то любое ребро графа G, не входящее в EH, служит Н–цепью.
Пусть подграф не является остовным. Рассмотрим три попарно различные вершины u VH, v VH, w VH. По теореме 5.1 в графе G есть проcтая (u,v) – цепь, проходящая через w. Очевидно существование подцепи этой цепи, являющейся Н – цепью графа G. Доказано.
Ниже для u,v VG положим Guv= G-u-v.
Теорема 5.7. Во всяком 3-связном графе G есть такое ребро uv, что граф Guv не имеет точек сочленения.
Доказательство
Если |G|=n=4, то утверждение теоремы очевидно . Поэтому будем считать, что n 
5. Предположим противное, т.е. что для любого ребра uv EG граф Guv имеет хотя бы одну точку сочленения. Тогда на 3-связности графа G следует, что при любом выборе ребра uv EG граф Guv обладает следующими свойствами (рис. 5.5):
1) если а – висячая вершина графа Guv, то av EG, au EG;
2) всякий висячий блок графа Guv, не являющийся ребром , содержит такую пару вершин с и d, отличных от точек сочленения графа Guv, что uc 
EG, vd EG.
3) всякий блок графа Guv, имеющий ровно две точки сочленения и отличный от ребра, содержит такую вершину l, не являющуюся точкой сочленения графа Guv, что или ul EG.
Обозначим через Buv максимальный по числу вершин блок графа Guv, а через tuv– число вершин в этом блоке . Теперь выберем ребро uv так, чтобы число tuv было наибольшим.
Покажем, что в этом случае tuv 3. Пусть tuv=2 и а – висячая вершина графа Guv (являющегося деревом). Так как n 5, то существует ребро cd EGuv. Из свойства 1) вытекает, что в графе Gcd существует цикл (u,a,v,u), т.е. tcd>tuv. Получено противоречие, следовательно, tuv 
3.
Через Duv обозначим bc-дерево графа Guv и рассмотрим следующие случаи.
1. Дерево Duv не является цепью. Выберем в этом дереве цепь, соединяющую пару висячих вершин и проходящую через вершину, соответствующую блоку Buv. Этой цепи соответствует последовательность B1,…,Bp блоков графа Guv, среди которых содержится блок Buv, причем блоки B1 и Bp являются висячими (рис. 5.6).
Пусть B'– произвольный висячий блок графа Guv, отличный от B1 и Bp. Из свойств 1) и 2) вытекает существование таких отличных от точек сочленения графа Guvвершин a VB1, b VBp, c VB', uc EG, va EG, vb EG. Тогда в графе Guc вершины множества
входят в один блок и, следовательно, tuv<tuc. Последнее противоречит выбору ребра uv.2. Дерево Duv–цепь и Buv–блок графа Guv, не являющийся висячим. Пусть B1,…,Bp– последовательность всех блоков графа G, причем блоки B1 и Bp–висячие, Bi 
Bi+1 
Ø (i= 
), Buv=Bk(1<k<p) (рис. 5.7). Cогласно свойству 3) найдется вершина b VBuv отличная от точек сочленения графа Guv, смежная с u или с v. Пусть ub EG. Согласно свойствам 1) и 2)
