Общих вершин. Получаем противоречие с утверждением 5.2. доказано

Граф bc(G) называется bc–деревом связного графа G.

Блоки графа G, соответствующие концевым вершинам его bc–дерева, называются концевыми блоками.

Похожее представление графа можно получить, положив в основу его максимальные реберно-2-связные подграфы, т.е. максимальные связные подграфы, не содержащие мостов. Такие подграфы называют листами. Не останавливаясь на деталях заметим следующее. Каждая вершина графа порядка n>1 принадлежит в точности одному листу и каждое ребро, не являющееся мостом, входит только в один лист. Таким образом, граф состоит из листов и мостов, соединяющих некоторые из них. Для описания строения графа «с точностью до листов» можно ввести граф, аналогичный графу bc(G). Вершины такого графа биективно соответствуют листам графа G и две его вершины соединены ребром в том и только в том случае, когда соответствующая пар листов в G соединена мостом. Можно показать, что введенный таким образом граф является деревом, если исходный граф связен.

На рис. 5.4 граф G имеет 5 листов L₁, L₂, L₃, L₄, L₅ и 4 моста, а граф G' показывает, как связаны между собой листы графа G.

Приведем некоторые результаты о трехсвязных графах, которые будут использованы в главе «Планарность».

Пусть G–связный граф, H–некоторый его подграф. Простую открытую цепь . графа G назовем H–цепь, если выполняются условия

v₁VH, v_kVH, v_iVH, i=

ребро e=uv графа G также будем называть Н–цепь, если uVH, vVH, eEH.

Лемма 5.6. Пусть G–двусвязный граф. Тогда для всякого его подграфа Н, содержащего более одной вершины и отличного от G, существует Н–цепь графа G.

Если Н–остовный подграф, то любое ребро графа G, не входящее в EH, служит Н–цепью.

Пусть подграф не является остовным. Рассмотрим три попарно различные вершины uVH, vVH, wVH. По теореме 5.1 в графе G есть проcтая (u,v) – цепь, проходящая через w. Очевидно существование подцепи этой цепи, являющейся Н – цепью графа G. Доказано.

Ниже для u,vVG положим G_uv= G-u-v.

Теорема 5.7. Во всяком 3-связном графе G есть такое ребро uv, что граф G_uv не имеет точек сочленения.

Если |G|=n=4, то утверждение теоремы очевидно . Поэтому будем считать, что n5. Предположим противное, т.е. что для любого ребра uvEG граф G_uv имеет хотя бы одну точку сочленения. Тогда на 3-связности графа G следует, что при любом выборе ребра uvEG граф G_uv обладает следующими свойствами (рис. 5.5):

если а – висячая вершина графа G_uv, то avEG, auEG;

всякий висячий блок графа G_uv, не являющийся ребром , содержит такую пару вершин с и d, отличных от точек сочленения графа G_uv, что ucEG, vdEG.

всякий блок графа G_uv, имеющий ровно две точки сочленения и отличный от ребра, содержит такую вершину l, не являющуюся точкой сочленения графа G_uv, что или ulEG.

Обозначим через B_uv максимальный по числу вершин блок графа G_uv, а через t_uv– число вершин в этом блоке . Теперь выберем ребро uv так, чтобы число t_uv было наибольшим.

Покажем, что в этом случае t_uv3. Пусть t_uv=2 и а – висячая вершина графа G_uv (являющегося деревом). Так как n5, то существует ребро cdEG_uv. Из свойства 1) вытекает, что в графе G_cd существует цикл (u,a,v,u), т.е. t_cd>t_uv. Получено противоречие, следовательно, t_uv3.

Через D_uv обозначим bc-дерево графа G_uv и рассмотрим следующие случаи.

Дерево D_uv не является цепью. Выберем в этом дереве цепь, соединяющую пару висячих вершин и проходящую через вершину, соответствующую блоку B_uv. Этой цепи соответствует последовательность B₁,…,B_p блоков графа G_uv, среди которых содержится блок B_uv, причем блоки B₁ и B_p являются висячими (рис. 5.6).

Пусть B'– произвольный висячий блок графа G_uv, отличный от B₁ и B_p. Из свойств 1) и 2) вытекает существование таких отличных от точек сочленения графа G_uv вершин aVB₁, bVB_p, cVB', ucEG, vaEG, vbEG. Тогда в графе G_uc вершины множества входят в один блок и, следовательно, t_uv

Похожие работы

Нахождение минимального остовного дерева алгоритмом Краскала

Скачать

16558

0

3

... Если граф G несвязный, он не может иметь остовного дерева, но у него есть остовный лес. Также можно изменить алгоритм нахождения остовного дерева максимального веса, чтобы на выходе получать минимальный остовный лес. остовное дерево алгоритм краскал В алгоритме Краскала используется жадный подход к решению задачи, т.е. в любой момент выполнения данных алгоритмов существует множество ребер E’, ...

Алгоритмы поиска остовного дерева Прима и Крускала

Скачать

16586

0

4

... вес 37). Такое дерево не единственно: заменяя ребро (Ь, с) ребром (а,h), получаем другое дерево того же веса 37. Мы рассмотрим два способа решения задачи о минимальном покрывающем дереве: алгоритмы Крускала и Прима. Каждый их них легко реализовать со временем работы O(E logV), используя обычные двоичные кучи. Применив фибоначчиевы кучи, можно сократить время работы алгоритма Прима до O(E+V logV) ...

Aлгоритмы на графах

Скачать

20554

0

0

... источником новой волны и т.д. При этом необходимо позаботиться о том, чтобы не вернутся в ту вершину, в которой уже были. Для реализации алгоритма понадобятся: матрица m[1..n, 1..n] - матрица смежности графа; вспомогательный массив queue[1..n], в котором будет формироваться очередь, т.е. тип данных первый вошел – первый вышел (FIFO). Размер его достаточен, так как мы не посещаем вершины дважды. ...

AGraph: библиотека классов для работы с помеченными графами

Скачать

55932

2

0

... , "базовые" алгоритмы: поиск путей, определение компонент связности графа и т.д. 8. Ввод/вывод графов Одной из проблем при создании средств работы с помеченными графами является выбор внешнего файлового формата для хранения графов. До недавнего времени каждая программная система использовала свой собственный, уникальный формат, что приводило к сложностям при организации обмена данными. ...