Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Граф 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.

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

[pic]

Пусть G–связный граф, H–некоторый его подграф. Простую открытую цепь . графа G назовем H–цепь, если выполняются условия v1[pic]VH, vk[pic]VH, vi[pic]VH, i=[pic] ребро e=uv графа G также будем называть Н–цепь, если u[pic]VH, v[pic]VH, e[pic]EH.

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

Доказательство

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

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

Ниже для u,v[pic]VG положим Guv = G-u-v.

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

Доказательство

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

1) если а – висячая вершина графа Guv, то av[pic]EG, au[pic]EG;

2) всякий висячий блок графа Guv, не являющийся ребром , содержит такую пару вершин с и d, отличных от точек сочленения графа Guv, что uc[pic]EG, vd[pic]EG.

3) всякий блок графа Guv, имеющий ровно две точки сочленения и отличный от ребра, содержит такую вершину l, не являющуюся точкой сочленения графа Guv, что или ul[pic]EG.

[pic]

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

Покажем, что в этом случае tuv[pic]3. Пусть tuv=2 и а – висячая вершина графа Guv (являющегося деревом). Так как n[pic]5, то существует ребро cd[pic]EGuv. Из свойства 1) вытекает, что в графе Gcd существует цикл
(u,a,v,u), т.е. tcd>tuv. Получено противоречие, следовательно, tuv[pic]3.
Через Duv обозначим bc-дерево графа Guv и рассмотрим следующие случаи.

1. Дерево Duv не является цепью. Выберем в этом дереве цепь, соединяющую пару висячих вершин и проходящую через вершину, соответствующую блоку

Buv. Этой цепи соответствует последовательность B1,…,Bp блоков графа

Guv, среди которых содержится блок Buv, причем блоки B1 и Bp являются висячими (рис. 5.6).

Пусть B'– произвольный висячий блок графа Guv, отличный от B1 и Bp. Из свойств 1) и 2) вытекает существование таких отличных от точек сочленения графа Guv вершин a[pic]VB1, b[pic]VBp, c[pic]VB', uc[pic]EG, va[pic]EG, vb[pic]EG. Тогда в графе Guc вершины множества [pic] входят в один блок и, следовательно, tuv0, то есть дерево Ti содержит новые ребра.
Поставим в соответствие дереву Ti подграф Ti* графа G, в котором каждое новое ребро xy дерева Ti заменим на два ребра xy и yz графа G. Каждое новое ребро в дереве Ti соответствует двум ребрам в графе Ti*, при этом, к вершинам дерева добавляется вершина z. Следовательно, мы получили связный остовный подграф Ti* графа G, в котором количество ребер на mi-1 больше , чем в дереве. Таким образом, в графе Ti* ровно mi-1 цикл, причем не трудно заметить, что каждый из этих циклов проходит через вершину z.
Следовательно, из графа Ti* можно удалить mi-1 инцидентных вершине z ребер так, что получится отстовное дерево Ti' графа G. В дерево Ti' входит mi+1 ребро, инцидентное вершине z. По построению очевидно, что при i[pic]j, mi>0 и mj>0 остовные деревья Ti' и Tj' графа не имеют общих ребер.

Пронумеруем k непересекающихся по ребрам остовных деревьев графа G таким образом, чтобы деревья T1, …, Tn содержали новые ребра, а деревья
Tn+1, …, Tk не содержали новых ребер (где 0[pic]). С помощью описанного выше способа построим по остовным деревьям T1, …, Tn графа G1 остовные деревья T'1, …, T'n графа G, никакие два из этих деревьев не будут иметь общих ребер. Всего при построении этих n деревьев использовано
(m1+1)+…+(mn+1) ребер графа G, инцидентных вершине z. В силу неравенства
(1), мы получаем, что

Рекомендуем скачать другие рефераты по теме: реферат сила, скачать контрольную.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки