Неориентированные деревья
Граф без циклов – ациклический / лес. Дерево – связный ациклический граф. Каждая компонента леса – дерево. Остов связного графа 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