Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется ациклическим (или) лесом. Таким образом, компонентами леса являются деревья. На рис.12 изображены все деревья шестого порядка.

Существует несколько вариантов определения дерева; некоторые из них отражены в следующей теореме.

Теорема 3.1Для графа следующие утверждения эквивалентны:

1) G – дерево;

2) G – связный граф и m=n-1;

3) G – ациклический граф и m=n-1;

4) любые две несовпадающие вершины графа соединяет единственная простая цепь;

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

2) Воспользуемся индукцией по n. При n=1 утверждение трививально. Пусть n>1, е
EG. В дереве G нет циклов, следовательно, согласно лемме 4.1, граф G – е имеет ровно две компоненты Т₁ и Т₂,

каждая из которых есть дерево. Пусть дерево T_i является (n_i, m_i) – графом, i=1, 2. По индуктивному предположению верно равенство

m_i=n_i-1. (1)

Далее имеем

m=m₁+m₂+1=(n₁-1)+(n₂-1)+1=(n₁+n₂)-1=n-1.

3) Граф G связен и m=n-1. Нужно доказать, что в G нет циклов. Пусть, напротив, в графе G есть цикл и пусть ребро е–ребро этого цикла. Тогда граф G – е связен (лемма 4.8) и имеет n-2 ребра, что противоречит теореме 4.9. следовадельно, G –ациклический граф.

4) Пусть к–число компонент графа G. Пусть, далее, компонента Т_i является (n_i, m_i)–графом. Так как Т_i–дерево, то верно равенство (1). Теперь имеем

n-1=m=m₁+m₂+…+m_k=(n₁-1)+(n₂-1)+…+(n_k-1)=(n₁+…+n_k)-k=n-k;

т.е. к=1. Итак, G–связный граф и потому любые несовпадающие вершины u и v соединены в нем просой цепью. Если бы в G были две несовпадающие простые (u,v)–цепи, то согласно утверждению 4.3 их объединение содержало бы цикл. Следовательно, каждые две вершины соединены единственной простой цепью.

5) пара несовпадающих вершин, принадлежащих одному циклу, соединена по меньшей мере двумя простыми цепами. Следовательно, граф G ациклический. Пусть u и v–две его нечмежные вершины. Присоединим к графу G ребро e=uv. В G есть простая (u,v)–цепь, которая в G+e дополняется до цикла. В силу утверждения 4.4 этот цикл единственный.

1) нужно докакзать, что граф G связен. Если бы вершины uи vпринадлежали разным компонентам графа G, то граф G+uv не имел бы циклов,что потиворечит утверждению 5). Итак, G связен и потому является деревом. Доказано.

Следствие 3.2. В любом дереве порядка n2 имеется неменее двух концевых вершин.

Пусть

d₁, d₂, …, d_n (2)

–степенная последовательность дерева. Тогда

(лемма о рукопожатиях) и все 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(G)=m(G)-|G|+k(G) называется циклическим рангом (или цикломатическим числом) графа G. число ребер остова графа Gназывается коциклическим рангом графа G. таким образом.

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

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

Следствие 3.5.граф G имеет единственный цикл тогда и только тогда, когда 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}. Чтобы учесть это обстоятельство, введем еще одно определение.

Задача остовных деревьев в k–связном графе (стр. 3 из 10)

Далее имеем

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

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