Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

(лемма о рукопожатиях) и все d_i>0. Следовательно, хотя бы два числа из последовательности (2) равны 1.

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

Следствие 3.3. число ребер произвольного графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m(G)-|G|+k(G), где m(G) и k(G)–число ребер и число компонент графа G соответственно.

Если (n₁, m₁)–граф Н является одной из компонент графа G, то для превращения ее в остове дерево нужно удалить m₁-(n₁-1) подходящих ребер. Суммируя по всем k(G) компонентам, получим требуемое.

Число (G)=m(G)-|G|+k(G) называется циклическим рангом (или цикломатическим числом) графа G. число ребер остова графа G называется коциклическим рангом графа G. таким образом.

Очевидны три следствия 13.4–13.6.

Следствие 3.4. Граф G является лесом тогда и только тогда, когда (G)=0.

Следствие 3.5. граф G имеет единственный цикл тогда и только тогда, когда (G)=1.

Следствие 3.6. Граф, в котором число ребер не меньше, чем число вершин, содержит цикл.

Утверждение 3.7. Если S и Т –два остова графа G, то для любого ребра е₁ графа S существует такое ребро е₂ графа Т, что граф также является остовом.

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

Не ограничивая общности, будем считать граф G связным. Граф имеет ровно две области связности; пусть это будут А и В. Поскольку граф Т связен, то в нем существует ребро е₂, один из концов которого входит в А, а другой – в В. Граф Н=S-e1+e₂ связен и число ребер в нем такое же, как в дереве S. следовательно, он сам является деревом. Итак, Н–остов графа G. Доказано.

Теорема 13.8. Центр любого дерева состоит из одной или из двух смежных вершин.

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

Очевидно, что концевые вершины дерева Т являются центральными только для T=K₁ или T=K₂.

Пусть Т дерево порядка n>2. Удалив из Т все концевые, получим дерево Т’. Очевидно, что эксцентриситет Т на единицу меньше эксцентриситета дерева Т и что центры деревьев Т и Т совпадают. Далее доказательство легео проводится индукцией по числу веншин.Доказано.

Глава II

Связность

Связный граф был определен как граф, у которого любые две вершины соединены цепью. Так, оба графа К_n и C_n связны, однако интуитивно ясно, что при n>3 граф K_n «сильнее» связен, чем C_n. В этой главе вводится и исследуются понятия, характеризующие степень связности графа.

§4 Вершинная связность и реберная связность.

Прежде чем ввести понятия вершинной и реберной связности, рассмотрим одну математическую модель, возникающую, в частности, при проектировании и анализе сетей ЭВМ. Имеется сеть, состоящая из центров хранения и переработки информации. Некоторые пары центров соединены каналами. Обмен информацией между любыми двумя центрами осуществляется либо непосредственно по соединяющему их каналу, если он есть, либо через другие каналы и центры. Сеть считается исправной, если каждая пара центров в состоянии обмениваться информацией. Такой сети естественно сопоставить граф: вершины–центры, ребра–каналы сети. Тогда исправной сети будет соответствовать связный граф. Важным понятием является надёжность (живучесть) сети, под которой обычно подразумевают способность сети функционировать при выходе из строя одного или нескольких центров или (и) каналов. Ясно, что менее надежной следует считать ту сеть, исправность которой нарушается при повреждении меньшего количества элементов. Оказывается, надежность сети можно измерять на основе вводимых ниже определений.

Числом вершин связности (или просто числом связности) (G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу.

Так, например, (K₁)=0, (K_n)=n–1, (C_n)=2.

Это вполне согласуется с интуитивным представлением том, что при n>3 граф K_n сильнее связен, чем C_n.

Граф G, представленный на рис. 4.1 связен, но его связность можно нарушить, удалив вершину 4. Поэтому (G)=1. Если же попытаться нарушить связность этого графа путем удаления ребер (а не вершин), то придется удалить не менее трех ребер. Например, G распадается на две компоненты

при удалении ребер {4,5}, {4,6}, {4,7}. Чтобы учесть это обстоятельство, введем еще одно определение.

Пусть G–граф порядка n>1. Числом реберной связности (G) графа G назовем наименьшее число ребер, удаление которых приводит к несвязному графу. Число реберной связности графа будем считать равным нулю, если этот граф одновершинный.

В качестве иллюстрации снова обратимся к графу G на рис. 4.1 Здесь (G)=3 и, следовательно, (G)> (G). Ниже будет показано, что противоположное неравенство невозможно ни для какого графа.

Определим некоторые элементы графа, играющие особую роль в дальнейших рассмотрениях.

Вершина v графа G называется точкой сочленения (или разделяющей вершиной), если граф G – v имеет больше компонент, чем G. В частности, если G связен и v – точка сочленения, то G– v не связен. Аналогично ребро графа называется мостом, если его удаление увеличивает число компонент.

Таким образом, точки сочленения и мосты – это своего рода «узкие места» графа. Граф, изображенный на рис. 4.2, имеет три точки сочленения a, b, c и один мост ab.

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

Возвращаясь к рассматриваемой в начале параграфа сети, нетрудно заметить, что число вершинной связности и число реберной связности ее графа отражают чувствительность сети к разрушению центров и каналов соответственно, а мостам и точкам сочленения отвечают наиболее уязвимые места сети.

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

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

Таким образом, доказана

Теорема 4.1: Для любого графа G верны неравенства

(G) .

Граф называется к–связным, если , и реберно–к–связным, если . Таким образом, отличный от К₁ граф 1–связен (односвязен) тогда и только тогда, когда он связен, а 2–связные (двусвязные) графы – это связные графы без точек сочленения, не являющиеся одновершинными.

Граф G, изображенный на рис. 4.1 1–связен и реберно–3–связен. Легко видеть, что этот граф содержит подграфы, являющиеся «более связными», чем сам граф. Таков, например, подграф, порожденный множеством вершин {1, 2, 3, 4, 8}. Он 3–связен.

Чтобы учесть эту и подобные ей ситуации, естественно ввести следующее определение: максимальный k–связный подграф графа называется его к–связной компонентой, или просто к–компонентой.

Это определение иллюстрируется на рис. 4.3. На этом рисунке граф G₁ имеет две 2–компоненты, а G₂–две 3–компоненты. Сами графы G₁ и G₂

являются 1–компонентами графа G₁ G₂. легко заметить, что 2–компоненты графа G₁ имеют одну большую вершину, а 3–компоненты графа G₂–две общие вершины. Следующая теорема показывает, что это обстоятельство не случайно.

Теорема 4.2: Две различные к–компоненты графа имеют не более чем к–1 общих вершин.

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

Пусть G₁ и G₂ –различные k–компоненты графа G и VG₁ VG₂=X. Предположим, что |X| k, и докажем, что тогда граф G₁ G₂ должен быть к–связным. Для этого в данном случае достаточно показать, что он остается связным после удаления любых k–1 вершин, т.е. Y V(G₁ G₂), |Y|=k-1, то граф (G₁ G₂) – Y связен. Положим

Y_i=(VG_i\X) Y, i=1,2, Y₃=X Y.

Ясно, что

|Y_i| k–1, i=1,2,3, Y= Y₁ Y₂ Y₃.

Поскольку

|Y_i Y₃| k–1, i=1,2,

и графы G₁ и G₂ k–связны, то графы

H_i=G_i–(Y_i Y₃), i=1,2,

связны. Так как по предложению |X| k, то X\Y₃ Ø, т.е. связны графы H₁ и H₂ имеют хотя бы одну общую вершину. Следовательно, связен граф H₁ H₂=(G₁ G₂)–Y. Последнее означает, что граф G₁ G₂ k–связен. Поэтому, вопреки предположению, ни G₁ не являются k–компонентами графа G.

§5 Двусвязные графы

Случаям, когда k=2 или k=3, в теории графов отведена особая роль. Это объясняется следующими причинами. Во–первых. 2– и 3–связные графы фигурируют во многих теоретических и прикладных вопросах, в частности, ряд задач достаточно уметь решать для 2–связных компонент. Во–вторых, при к=3 и, особенно, при к=2 удается дать в некоторой степени обозримое описание соответствующих графов.

Рассмотрим вначале некоторые простые свойства 2–связных графов, вытекающие непосредственно из определений:

1. степени вершин 2–связного графа больше единицы;

2. если графы G₁ и G₂ 2–связны и имеют не менее двух общих вершин, то граф G₁ G₂ также 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}. искомый цикл теперь строится точно так же, как в предыдущем пункте.

Характеристики

Список файлов реферата