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

Далее имеем

m=m1+m2+1=(n1-1)+(n2-1)+1=(n1+n2)-1=n-1.
2) [pic]3) Граф G связен и m=n-1. Нужно доказать, что в G нет циклов.
Пусть, напротив, в графе G есть цикл и пусть ребро е–ребро этого цикла.
Тогда граф G – е связен (лемма 4.8) и имеет n-2 ребра, что противоречит теореме 4.9. следовадельно, G –ациклический граф.
3) [pic]4) Пусть к–число компонент графа G. Пусть, далее, компонента Тi является (ni, mi)–графом. Так как Тi–дерево, то верно равенство (1). Теперь имеем n-1=m=m1+m2+…+mk=(n1-1)+(n2-1)+…+(nk-1)=(n1+…+nk)-k=n-k; т.е. к=1. Итак, G–связный граф и потому любые несовпадающие вершины u и v соединены в нем просой цепью. Если бы в G были две несовпадающие простые
(u,v)–цепи, то согласно утверждению 4.3 их объединение содержало бы цикл.
Следовательно, каждые две вершины соединены единственной простой цепью.
4) [pic]5) пара несовпадающих вершин, принадлежащих одному циклу, соединена по меньшей мере двумя простыми цепами. Следовательно, граф G ациклический.
Пусть u и v–две его нечмежные вершины. Присоединим к графу G ребро e=uv. В
G есть простая (u,v)–цепь, которая в G+e дополняется до цикла. В силу утверждения 4.4 этот цикл единственный.
5) [pic]1) нужно докакзать, что граф G связен. Если бы вершины u и v принадлежали разным компонентам графа G, то граф G+uv не имел бы циклов,что потиворечит утверждению 5). Итак, G связен и потому является деревом.
Доказано.
Следствие 3.2. В любом дереве порядка n2 имеется неменее двух концевых вершин.
Пусть d1, d2, …, dn (2)
–степенная последовательность дерева. Тогда

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

Пусть Н–остовный подграф поизвольного гафа G. Если на каждой области связности графа G графом Н порождает дерево, то Н называется остовом (или каркасом) графа G. очевидно, что в каждом графе существует остов: разрушая в каждой компоненте циклы, т.е. удаляя лишние ребра, придем к остову. Остов в графе легко найти с помощью поиска в ширину.
Следствие 3.3. число ребер произвольного графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m(G)-|G|+k(G), где m(G) и k(G)–число ребер и число компонент графа G соответственно.
Если (n1, m1)–граф Н является одной из компонент графа G, то для превращения ее в остове дерево нужно удалить m1-(n1-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, то для любого ребра е1 графа S существует такое ребро е2 графа Т, что граф также является остовом.

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

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

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

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

Глава II

Связность

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

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

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

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

Так, например, [pic](K1)=0, [pic](Kn)=n–1, [pic](Cn)=2.
Это вполне согласуется с интуитивным представлением том, что при n>3 граф
Kn сильнее связен, чем Cn.

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

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

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

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

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

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

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

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



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

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