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

Понятно, что концевая вершина моста является точкой сочленения, если в графе есть другие ребра, инцидентные этой вершине.

Возвращаясь к рассматриваемой в начале параграфа сети, нетрудно заметить, что число вершинной связности и число реберной связности ее графа отражают чувствительность сети к разрушению центров и каналов соответственно, а мостам и точкам сочленения отвечают наиболее уязвимые места сети.
Если [pic](G) – минимальная степень вершин графа G, то очевидно, что
[pic](G)[pic][pic](G), поскольку удаление всех ребер, инцидентных данной вершине, приводит к увеличению числа компонент графа.

Выясним теперь соотношения между числами [pic](G) и [pic](G). Если граф G не связен или имеет мост, то очевидно, что [pic](G)= [pic](G). Пусть
G– связный граф без мостов. Выберем в этом графе множество Е1, состоящее из
[pic]=[pic](G) ребер, удаление которых приводит к несвязному графу. Пусть
E2[pic] E1, |E2|=[pic]–1. Граф G – E2 связен и имеет мост, который обозначим через uv. Для каждого ребра из множества Е2 выберем какую–либо инцидентную ему вершину, отличную от u и v. Удалим теперь выбранные вершины из графа. Этим самым будут удалены, в числе прочих, и все ребра, входящие в
Е2. Если оставшийся граф не связен, то [pic]=[pic](G)2. Тогда следующие утверждения эквивалентны:

1) граф 2–связен;

2) любые две вершины графа принадлежат простому циклу;

3) любая вершина и любое ребро принадлежат простому циклу;

4) любые два ребра принадлежат простому циклу;

5) для любых двух вершин a и b и любого ребра е существует простая

(a,b)–цепь, содержащая е;

6) для любых трех вершин a,b,c существует простая (a,b)–цепь, проходящая через с.
1)[pic]2). Пусть a и b–две вершины графа G. Рассмотрим множество всех простых циклов графа G, содержащих а. Обозначим через U множество всех вершин, входящих в эти циклы. Ясно, что U[pic]Ш. Действительно, простой цикл, содержащий а, можно получить, объединить два ребра ax и ay (x?y) и простую (x, y)–цепь, не проходящую через а (существующую согласно свойству
4)). Предположим, что b[pic]U, и положим [pic]=VGU. Поскольку граф G связен, то в нем найдется такое ребро zt, что z[pic]U, t[pic][pic](рис.
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[pic]; но это противоречит выбору ребра zt. Таким образом, [pic]=Ш, т.е. a и b лежат на общем простом цикле.
2)[pic]3). Пусть а–вершина и zt–ребро графа G. По условию G содержит цикл
S, проходящий через вершины a и z. Не теряя общности будем считать, что zt[pic]S. Если при этом окажется, что S проходит через вершину t, то требуемый цикл строится очевидным образом. Пусть S не проходит через t.
Тогда рассмотрим простой цикл S', проходящий через вершины t и a. Такой цикл, по условию, существует. Частью этого цикла является простая цепь Р, соединяющая t с некоторой вершиной v[pic]S. Цепь Р можно выбрать так, чтобы

[pic]
VP[pic]VS={v}. искомый цикл теперь строится точно так же, как в предыдущем пункте.
3)[pic]4). Пусть ab и tz–два ребра графа G. По условию G имеет простые циклы S и S', первый из которых содержит ab и z, а второй – ab и t. Далее искомый цикл строится так же, как в предыдущих пунктах.
4)[pic]5). Пусть a,b [pic]VG, tz[pic]EG. Будучи связным, граф G содержит простую цепь P=(a,x,…,b). Согласно утверждению 4) а графе G есть простой цикл S, содержащий ребра ax, tz. Легко видеть, что в объединении S[pic]P имеется требуемая цепь.
5)[pic]6). Пусть a,b,c[pic]VG, cd[pic]EG. По условию в графе имеется простая (a,b)–цепь, проходящая через cd и, следовательно, содержащая c.
6)[pic]1). Пусть v[pic]VG. Покажем. Что граф G – v связен, т.е. любая a,b его вершин соединена цепью. Действительно, согласно утверждению 6) в графе
G имеется простая (v,b)-цепь, которая, очевидно, не проходит через v и, следовательно, является (a, b)-цепью и в графе G – v. Доказано.

Если в формулировке теоремы 34.1 заменить всюду слова «простая цепь» и «простой цикл» соответственно на слова «цепь» и «цикл», то получим аналогичную теорему о 2–реберно–связном графах.

Как отмечалось выше, при решении многих задач на графах достаточно уметь решать эти задачи для каждой 2–связной компоненты графа. Поэтому представляет интерес взаимное расположение 2–компонент в графе.

Максимальные относительное включения элементы множества связных подграфов графа G, не имеющих точек сочленения, называются его блоками.
Таким образом, каждый блок графа либо 2–связен, либо совпадает с К2 или К1
(граф К1 – блок тогда и только тогда, когда он является связной компонентой). Связный граф без точек сочленения также называют блоком.

[pic]
Множество вершин блока будем называть блоковым множеством.

Например, граф, изображенный на рис. 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[pic]C – множество вершин и {Bici: B[pic]B, ci[pic]C, ci[pic]Bi} – множество ребер. Тем самым, ребра двудольного графа bc(G) указывают на принадлежность точек сочленения блоками. На рис. 5.3 представлены графы G и bc(G).

Утверждение 5.5. Если граф G связен, то bc(G)–дерево.

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

Очевидно, что из связности графа G вытекает связность графа bc(G).

[pic]
Предположим, что bc(G) содержит цикл С. Пусть этот цикл имет вид С=(c[pic], b[pic],c[pic], b[pic],…,c[pic],b[pic],c[pic]). Каждый из блоков B[pic] содержит (с[pic],с[pic])- цепь и объединение этих цепей дает простой цикл в графе G. Обозначим этот цикл через С'. Ясно, что С' содержит по крайне мере две вершины каждого из блоков B[pic]. Поэтому из утверждения 34.3 следует, что цикл С' должен содержаться в каждом их этих блоков. Последнее означает, что каждая пара блоков B[pic] имеет не менее |C'|[pic]3 общих вершин.
Получаем противоречие с утверждением 5.2. доказано.

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



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

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