Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Дискретка / Графы_часть_3.pdf
Скачиваний:
30
Добавлен:
25.02.2016
Размер:
663.9 Кб
Скачать

Неориентированные деревья

Граф без циклов – ациклический / лес. Дерево – связный ациклический граф. Каждая компонента леса – дерево. Остов связного графа G – его остовной подграф, являющийся деревом. Связный подграф

дерева T поддерево T. Кодерево остова T – дополнение T

остова T в графе G, т.е.

T

– остовной

подграф G, содержащий те и только те ребра графа G, которые не входят в T.

 

 

 

 

 

 

 

 

Теорема 23. (p, q)-граф G = (V, X) является деревом тогда и только тогда,

 

 

 

 

 

 

 

 

 

G – дерево

 

 

 

 

 

 

 

когда выполняются одно из следующих условий:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

а) любые две вершины в T соединены единственной простой цепью;

 

в)

 

 

 

 

а)

б) G – связный и p = q + 1;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

в) G – ациклический и p = q + 1.

 

 

 

 

 

 

б)

 

Теорема 24. Граф G является деревом тогда и только

тогда, когда

он

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Теорема 25. Граф G – связный тогда и только тогда, когда он имеет остов.

Теорема 26. Любой лес, имеющий более одной вершины, является двудольным графом.

Дерево – реберно-критический связный граф, оно имеет наименьшее число ребер при заданном числе вершин. Каждое ребро дерева является мостом.

Ориентированные деревья

1.

!

Ориентированное

v

 

V :

1

v

 

0

 

 

 

 

0

 

(корневое) дерево – орграф G = (V, Γ), удовлетворяющий условиям:

корень дерева;

2.

v v0

: d

 

v 1 .

 

Теорема 27. Если G = (V, Γ) – корневое дерево с корнем v0, то v V ! v0 v путь .

Уровень вершины v дерева G – длина (v0 v)-пути. Уровень v0 считается равным 0. Высота дерева – наибольший уровень его вершин.

Пусть vi , v j V . Если в G vi v j путь , то говорят, что вершина vi предшествует / является

предком вершины vj (vj следует за / является потомком vi). Любая вершина уровня n следует ровно за одной вершиной уровней (n – 1), …, 2, 1, 0.

Вершина, не имеющая выходных дуг ( v ), – заключительная. Остальные – незаключительные. При построении диаграмм используются стандартные правила:

а) все вершины одного уровня располагаются на одной прямой; б) эти прямые параллельны и располагаются в порядке возрастания уровней; в) дуги дерева не пересекаются.

Бинарное (двоичное) дерево – ориентированное дерево, в котором v V : d

 

v 2 .

 

Центры и центроиды

 

 

Пусть G = (V, X) – связный граф.

 

 

 

Эксцентриситет вершины v V – число

e v max v, w .

 

 

 

w V

 

 

Радиус r(G) графа – наименьший из эксцентриситетов его вершин: r G min e v .

v V

Диаметр графа dim(G) – наибольший из эксцентриситетов его вершин: dim G max e v .

v

Иногда диаметр определяют как величину, равную удвоенному радиусу.

Вершина v называется центральной, если e(v) = r(G). Множество всех центральных вершин –

центр графа.

Теорема 28. Центр любого дерева содержит либо одну вершину, либо две смежные вершины.

1

Пусть T – дерево. Ветвь к вершине v T

– максимальное поддерево T(v), содержащее v в качестве

висячей вершины. Число ветвей к вершине v равно степени d(v) этой вершины.

Каждая висячая вершина дерева имеет одну ветвь, совпадающую с T.

 

Вес вершины v дерева T – число

P v max q T v ,

где q(T(v)) – число ребер в ветви T(v).

 

T v

 

 

Вершина v называется центроидной, если имеет наименьший вес, т.е.

P v min P w .

 

 

 

w V

Для центроидов деревьев справедлива теорема, аналогичная теореме 28.

Задача о минимальном покрывающем дереве

 

Ребро x и вершина v называются покрывающими друг друга, если они инцидентны ( v x ).

 

 

Вершинное покрытие графа – множество вершин, покрывающих все ребра графа.

 

 

Реберное покрытие графа – множество ребер, покрывающих все вершины графа.

 

 

Пусть G = (V, X) – связный взвешенный граф, cij = c(vi, vj) – вес ребра {vi, vj}. Требуется

остов (остовное дерево), имеющий наименьшую сумму весов ребер.

 

 

 

 

Алгоритм Прима:

 

 

 

 

 

 

 

 

 

 

 

 

1. Выбрать произвольную вершину vs

и рассмотреть дерево Ts = (Vs, Xs}, где Vs = {vs},

X s .

 

2.

Для v j

Т s найти w j

Т s : c w j ,v j

min c vi ,v j j

и приписать вершине vj метку [wj, βj].

 

 

 

 

 

 

 

 

 

 

 

 

v

T

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i

s

 

 

 

 

 

 

Если такой вершины wj нет, т.е. v j Т s , приписать вершине vj метку [0, ∞].

 

 

3.

Выбрать вершину w

* такую, что

 

j

*

min j

. Обновить данные: Vs Vs v

* , X s

X s w

* ,

 

 

 

 

 

j

 

 

 

 

v

Т

s

 

j

 

j

 

 

 

 

 

 

 

 

 

 

 

 

j

 

 

 

 

 

 

 

Если

Vs

n , то минимальное дерево найдено, иначе – перейти к п. 4.

 

 

 

4.

Для v j

Т s :

v j v

* , изменить метки следующим образом:

 

 

 

 

 

 

c v

 

 

j

 

 

 

 

c v

 

 

 

 

 

 

 

если

j

* , v j

, то положить

j

* , v j

, w j v

* и перейти к п. 3;

 

 

 

 

 

 

j

 

 

 

 

 

 

 

 

j

 

j

 

 

 

 

 

если

j

c v

* , v j

, перейти к п. 3.

 

 

 

 

 

 

 

 

 

 

 

 

 

j

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

найти

v

* .

j

 

Эйлеровы графы

Пусть G = (V, X) – связный граф.

Эйлерова цепь – цепь, содержащая все ребра графа.

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

Эйлеров граф – граф, в котором существует эйлеровый цикл.

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

Теорема 29. Для любого графа G = (V, X) следующие утверждения эквивалентны: а) G – эйлеров граф;

б) G – связный и v V d(v) – четна;

в) G – связный и является объединением реберно-непересекающихся простых циклов.

Теорема 30. Связный граф G содержит эйлерову цепь тогда и только тогда, когда ровно две его вершины имеют нечетные степени, причем эйлерова цепь соединяет эти вершины с нечетными степенями.

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

Аналогичные теоремы справедливы и для орграфов. Например, необходимым и достаточным условием существования контура, содержащего все дуги и каждую из них только один раз, является условие: v V : d v d v .

2

Гамильтоновы графы

Пусть G = (V, X) – связный граф.

Гамильтонова цепь – простая цепь, содержащая все вершины графа. Гамильтонов цикл – простой цикл, содержащий все вершины графа. Гамильтонов граф – граф, содержащий гамильтонов цикл.

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

Следующие теоремы описывают достаточные условия гамильтоновости графов.

 

Теорема 32 (Дирак).

Связный

(p, q)-граф

G = (V, X),

p ≥ 3,

является

гамильтоновым,

если

v V : d v p 2 .

 

 

 

 

 

 

 

Теорема 33. Связный

граф G,

имеющий

p вершин

(p ≥ 3),

является

гамильтоновым,

если

v, w V v не см w d v d w p .

 

 

 

 

 

 

Известны и другие достаточные условия гамильтоновости графов. Суть этих условий сводится к тому, что в графе должно быть достаточно много ребер.

Раскраска графов

Граф G = (V, X) называется реберно-раскрашенным, если его ребрам приписаны цвета так, что никакие два смежных ребра не имеют одинакового цвета. Если для этого используется k красок, то граф

называется реберно-k-раскрашенным.

 

 

 

 

 

 

 

Хроматический индекс графа G – минимальное число цветов G , достаточных для рёберной

 

 

 

 

раскраски графа. Если G k , то граф G называется реберно-k-хроматическим.

 

 

 

 

 

 

 

Если G k , то множество ребер X можно разбить на k непересекающихся множеств Xi, i 1, k ,

( X i

X ), в каждом из которых нет смежных ребер и все ребра имеют i-й цвет,

т.е. каждый из

одноцветных классов Xi, i 1, k , является паросочетанием в графе G. Поэтому

 

можно считать

G

наименьшим числом паросочетаний, на которые разбивается множество ребер X. Множества Xi

называются одноцветными классами.

Граф G = (V, X) называется вершинно-k-раскрашиваемым, если его вершины можно раскрасить k- красками так, чтобы никакие две смежные вершины не имели бы одинаковый цвет.

Хроматическое число графа G – минимальное число цветов χ(G), достаточных для вершинной раскраски графа. Граф G называется k-хроматическим, если χ(G) = k. Вершинную раскраску называют

простой раскраской.

Очевидно, k-раскраска порождает разбиение множества вершин V на k подмножеств (одноцветных классов) Vi, i 1, k , (Vi V ), в каждом из которых нет смежных вершин, т.е. граф можно считать k- дольным. И наоборот, всякое разбиение V на такие подмножества соответствует некоторой раскраске.

Для любого простого графа G = (V, X) имеют место оценки: G G , χ(G) ≤ Δ(G) + 1. Для двудольного графа G G . В общем случае G G .

Любой простой граф является реберно-(Δ(G) + 1)-раскрашиваемым, т.е. G G 1 .

Для полных графов и циклов нечетной длины χ(G) = Δ(G) + 1, для всех остальных графов χ(G) ≤ Δ(G).

Теорема 34. Пусть G = (V, X) – непустой граф и V p 2 . Тогда G 1 max G , где G

G

порожденный подграф графа G: G min d v , v G .

3

Алгоритм раскраски графов

 

Пусть G = (V, X) – связный граф с n вершинами.

1.

Всем вершинам G присвоить метку 1. Обозначить A(k),

 

метку k, т.е. A(1) = V; A k , k 2, n . Положить k = 1.

2.

Выбрать новый, ранее не рассмотренный элемент v A k .

 

w A k , смежных вершине v. Изменить множества

k 1, n , – множества вершин, имеющих

Обозначить A*(k + 1) – множество вершин A(k) и A*(k + 1) следующим образом:

A

k 1

*

 

A k 1 A

k

*

 

1

;

A k

A k \

A

k

*

 

1

.

3.Если в множестве A(k) имеется еще не рассмотренная вершина, перейти к п. 2, иначе – к п. 4.

4.Положить k = k + 1. Если k n, перейти к п. 2, иначе перейти к п. 5.

5.Вычислить оценку хроматического числа графа по формуле X G max k : A k .

Планарность

Нередко на практике возникает задача нахождения такого представления графа, чтобы его ребра не пересекались. Например, при рассмотрении некоторой электрической схемы необходимо, чтобы все проводники располагались в одной плоскости и не пересекались между собой. Такое представление (укладка) графа существует не всегда. В общем случае рассматривается укладка графа на произвольной поверхности.

Граф G называется уложенным на поверхности S, если его диаграмму можно нарисовать на поверхности S так, чтобы ребра пересекались только в вершинах. Граф называется плоским, если он уложен на плоскости, и планарным, если он изоморфен плоскому.

Теорема 35. Любой простой планарный граф можно уложить на плоскости так, чтобы все ребра изображались отрезками прямых.

Укладываемость графа на плоскости и на сфере эквивалентны, т.е. если граф укладывается на плоскости, то он укладывается и на сфере, и обратно. Не всякий граф может быть уложен на плоскости.

Теорема 36. Любой граф можно уложить в трехмерном евклидовом пространстве.

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

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

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

гомеоморфных графов приведён на рис. 1.

 

Рис. 1

Теорема 37 (Понтрягин-Куратовский). Граф G планарен тогда и только тогда, когда он не

содержит подграфа, гомеоморфного K5

G:

H:

K3,3:

или K3,3.

 

 

 

Теорема 38. Граф G планарен

 

тогда и только тогда, когда он не

 

содержит подграфа, стягиваемого к K5

 

или K3,3.

Рис. 2

Граф G, изображенный на рис. 2,

 

непланарный, т.к. он содержит подграф H, гомеоморфный K3,3. Кроме того, G является стягиваемым к K5.

4