учебное пособие - теория графов

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

Лемма 9.2. Для произвольного графа G справедливо неравенство

x(G)≤ λ(G)≤δ(G), где δ(G) – минимальная из степеней всех вершин графа

G.

Теорема 9.1 (критерий связности графа). Граф G является связ-

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

Доказательство. 1. Необходимость. Пусть G=(V,R) – связный граф. Допустим, что существуют такие графы G1=(V1,R1), G2=(V2,R2), что

G=G1 G2 V=V1 V2, V1∩V2= и R=R1 R2. Так как. R1 V12 и R2 V22

R1∩R2= .

Пусть Gн, (G1)н, (G2)н – неоргафы, соответствующие G, G1, G2 со-

ответственно; Gн=(V,Rн), (G1)н=(V1,(R1)н), (G2)н=(V2,(R2)н) V=V1 V2, V1∩V2= , Rн=(R1)н (R2)н Gн=(G1)н (G2)н.

Так как V1≠, V2≠, то существуют вершины a V1 и b V2 . Тогда a, b V . Это означает, что в графе Gн существует (a,b)-маршрут

(a1=a, a2, a3,…, ak=b) (1) и (ai, ai+1) Rн, i=1, k 1.

С другой стороны, так как a1=a V1, ak=b V2 и V1∩V2=, то существует j, где 1≤j≤k-1, такое, что aj V1 (и значит, aj V2) и aj+1 V2 (и значит, aj+1 V1). Следовательно, (aj,aj+1) (R1)н и (aj,aj+1) (R2)н (aj,aj+1) (R1)н (R2)н=Rн. Получили противоречие. Таким образом, допущение неверно, и поэтому G нельзя представить в виде дизъюнктивного объединения двух графов.

2. Достаточность. Пусть граф G нельзя представить в виде дизъюнктивного объединения двух графов. Покажем, что G – связный граф. Допустим, что граф G не является связным. Тогда существует компонен-

51

та связности графа G, отличная от G. Пусть G1 – максимальный связный подграф графа G такой, что G1≠G. Пусть G=(V,R), G1=(V1,R1). Так как

G1 G , то V1 V и R1 R.

Предположим, что V1=V. Так как G1 – связный граф, то (G1)н – связный граф. Это означает, что любые две вершины из V1 соединены

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

V1 V. Тогда V\V1≠ , и поэтому существует граф вида G2=(V\V1, R\R1).

Тогда G=G1 G2. Противоречие. Следовательно, G – связный граф. Теорема доказана.

§ 10. Теоремы о разложении графа

на связные компоненты

Содержание параграфа

теорема о представлении неориентированного графа в виде дизъюнктивного объединения связных компонент, следствие;

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

Теорема 10.1. Всякий неориентированный граф допускает представление в виде дизъюнктивного объединения своих связных компонент, причем такое представление единственно.

Доказательство. Пусть G (V , R) неорграф.

1. Зададим на множестве V бинарное отношение по правилу:a,b V : a b a и b находятся в одной связной компоненте графа G (т.е. a и b соединены маршрутом в G).

52

Покажем, что - отношение эквивалентности.

а) Рефлексивность. Так как a V вершина a находится в одной связной компоненте с a, то a a , т.е. рефлексивно.

б) Симметричность. Пусть a b . Тогда вершины a и b находятся в одной связной компоненте. Это означает, что вершины b и a находятся в одной связной компоненте, т.е. b a . Следовательно, симметрично.

в) Транзитивность. Пусть a b и b c . Тогда a и b соединены маршрутом в G и b и c соединены маршрутом в G. Следовательно, a и c соединены маршрутом в G, т.е. a c . Следовательно, транзитивно.

Из а) – в) следует, что – отношение эквивалентности.

По основной теореме об отношении эквивалентности множество V разбивается отношением на непересекающиеся классы эквивалентных

элементов V1 ,V2 ,...,Vk , т.е.

связной компоненте (*). Это означает, что граф G имеет k связных компонент, соответствующих множествам V1 ,V2 ,...,Vk .

b соединены маршрутом в G a b . Это означает, что существует мно-

нозначности представления V в виде (1). Покажем, что Gi связная ком-

понента графа G, i 1, k .

а) Проверим, что Gi связный граф. Пусть a,b Vi a и b со-

единены маршрутом в G, ввиду (*). Следовательно, Gi связный граф.

б) Установим, что Gi максимальный связный подграф графа G.

Если G является связным графом, то G Gi , k 1. Пусть граф G не является связным и H – такой связный подграф графа G, что Gi H G .

чие. Следовательно, предположение неверно и Gi H . Тем самым уста-

новлено, что Gi максимальный связный подграф графа G.

Из а) – б) следует, что Gi связная компонента графа G, i 1, k . Теорема доказана.

54

Следствие 10.1.1. Всякий граф допускает представление в виде дизъюнктивного объединения своих связных компонент, причем такое представление единственно.

Теорема 10.2. Множество всех вершин графа G допускает представление в виде объединения непересекающихся подмножеств, соответствующих сильным компонентам графа.

Доказательство. Пусть G (V , R) граф. Зададим на множестве V бинарное отношение по правилу: a,b V : a b a и b находятся в одной сильной компоненте графа G (т.е. существует в G (a,b) -маршрут и (b, a) -маршрут). Покажем, что – отношение эквивалентности.

а) Рефлексивность. Так как a V вершина a находится в одной сильной компоненте с a, то a a . Следовательно, рефлексивно.

б) Симметричность. Пусть a b . Тогда вершины a и b находятся в одной сильной компоненте графа G, и значит, b a . Следовательно, симметрично.

в) Транзитивность. Пусть a b и b c . Тогда в G существуют (a,b) -маршрут и (b, a) -маршрут, (b, c) -маршрут и (с,b) -маршрут. Поэтому существуют (a, c) -маршрут и (c, a) -маршрут. Следовательно, транзитивно.

Из а) – в) следует, что – отношение эквивалентности. По основной теореме об отношении эквивалентности множество V разбивается

55

отношением на непересекающиеся классы эквивалентных элементов

V1 ,V2 ,...,Vk , т.е. V V1 V2 ... Vk , Vi Vj , i j (**).

Отметим, что a,b Vi a b вершины a и b находятся в одной сильной компоненте графа G. Тогда граф G имеет k сильных компонент, соответствующих множествам V1 ,V2 ,...,Vk .

Покажем, что Gi сильная компонента графа G, i 1, k .

а) Покажем, что Gi сильно связный граф. Пусть a,b Vi . Тогда в

G существуют (a,b) -маршрут и (b, a) -маршрут. Следовательно, Gi сильно связный граф.

б) Покажем, что Gi максимальный сильно связный подграф гра-

фа G. Если G – сильно связный граф, то G Gi , k 1. Пусть граф G не является сильно связным и H – такой сильно связный подграф графа G,

Из а) – б) следует, что Gi сильная компонента графа G, i 1, k . Теорема доказана.

56

§11. Оценка числа ребер графа через число вершин

ичисло компонент связности

Содержание параграфа

предварительные результаты;

теорема об оценке числа ребер графа через число вершин и число связных компонент графа;

следствие из теоремы.

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

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

Лемма 11.2. Пусть G – граф, имеющий две связные полные компо-

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

57

Следствие 11.2.1. Пусть G – граф, имеющий n вершин и k полных связных компонент, который обладает наибольшим числом ребер. Тогда граф G допускает представление в виде:

G (K1 K1 ... K1) Kn (k 1) .

Теорема 11.1. Пусть G – неорграф, имеющий n вершин, m рёбер и k

связных компонент. Тогда n k m (n k)(n k 1) . 2

Доказательство. 1. Докажем, что n k m. Доказательство проведём методом математической индукции по параметру n.

2)Пусть n 1. Предположим, что утверждение верно для любого натурального числа, большего 1 и меньшего n.

3)Докажем, что утверждение верно для n. Так как G – нетривиальный граф, то по лемме 11.1 в G существует вершина, не являющаяся точкой сочленения. Пусть a – вершина графа G, не являющаяся точкой сочленения. Пусть G' G a, n', m', k' – число вершин, рёбер и связных

компонент графа G' соответственно. Тогда n' n 1 и по предположению индукции n' k' m' . Возможны 2 случая:

а) Пусть a – изолированная вершина. Тогда

б) Пусть a – неизолированная вершина. В этом случае

графа G1 . Тогда m m1 . Пусть G2 – неорграф, имеющий n вершин и k полных связных компонент, который имеет наибольшее число рёбер, m2

– число рёбер G2 . Тогда m1 m2 m m2 . По следствию 11.2.1

Неравенство (**) возможно лишь в случае, когда k 1. Это означает, что G – связный граф. Следствие доказано.

59

§ 12. Эйлеровы графы

Содержание параграфа

эйлеровы цепи, циклы, графы;

примеры;

предварительные результаты;

критерий эйлеровости графа.

Определение 12.1. Связный неорграф G называется эйлеровым, если он имеет эйлеров цикл, т.е. цикл, содержащий все рёбра графа G.

Замечание 12.1. Другими словами, эйлеров цикл графа G – это такой маршрут G, который удовлетворяет трем условиям:

1)первая и последняя вершины маршрута совпадают (циклический мар-

шрут);

2)все ребра маршрута попарно различны (цепь);

3)маршрут содержит все ребра графа G (условие эйлеровости).

Замечание 12.2. Цепь графа G называется эйлеровой, если она содержит все рёбра графа G.

Пример 12.1. Граф G имеет эйлерову цепь (1,2,3,4,5,6) и не имеет эйлерова цикла:

Пример 12.2. Граф G имеет эйлерову цикл (1,2,3,4,5,6,7):

60