Теория графов

рицы A2 образуется при перемножении элемента (1, 4) матрицы A на элемент (4, 2) матрицы A, т.е. следовательно, двигаясь от 1

к3 за 3 шага, получаем маршрут (1,4, 2, 3).

Вматрице A3 элемент (4, 2) равен 3, это значит, что существуют три (4,2) маршрута длины 3 : (4, 1, 4, 2), (4, 2, 4, 2), (4, 2, 3, 2).

3.4. Матрица взаимодостижимости.

Образуем из матрицы E+ A+A2+…+ An=(bi, j) матрицу С порядка n по правилу:

Полученная матрица С называется матрицей связности, если G – неорграф и матрицей достижимости, если G – орграф.

Элемент этой матрицы сi, j =1 тогда и только тогда, когда

в графе есть (vi, vj) – маршрут (i≠j).

Матрицей контрдостижимости называется матрица Q=(qi, j), элементы которой:

Отметим, что Q=CT. Матрицы достижимости и контрдостижимости используются для нахождения сильных компонент графа. Для этого используется матрица взаимодостижимости (сильных компонент) S C Q , где символ означает поэле-

ментное произведение матриц С и Q, т.е. sij=cij·qij.

Элемент sij=1 тогда и только тогда, когда вершины vi и vj взаимодостижимы. Это означает, что они находятся в одной сильной компоненте. Следовательно, сильная компонента, содержащая вершину vi, состоит из тех элементов vij, для которых

sij=1.

Пример. Для графа, изображённого ниже, определим матрицы достижимости, контрдостижимости и взаимодостижимости

20

По второй строке матрицы S находим, что сильная компонента, содержащая вершину 2 состоит из вершины (1, 2, 3).

21

4.ДЕРЕВЬЯ.

4.1.Свободные деревья.

Деревом называется связный граф без циклов (конту-

ров).

Несвязный граф без циклов (контуров) называется лесом. Компоненты связности леса являются деревьями.

Подграф G1=(V1, E1) графа G=(V, E) называется остовным деревом в графе G=(V, E), если G1=(V1, E1) – дерево и

V1=V.

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

Например: 1) Диаграммы всех различных свободных деревьев с 5-ю вершинами:

2) Диаграммы всех различных свободных деревьев с 6-ю вершинами:

Лемма 1. Если граф G=(V, E) связный и ребро (u, v) содержится в некотором цикле графа G, то при удалении этого ребра получится новый связный граф.

Доказательство: При удалении ребра (u, v), вершины u и v останутся в одной и той же связной компоненте, т.к. они остаются связными за счет оставшейся части цикла.

22

Теорема 1. Любой связный граф содержит хотя бы одно остовное дерево.

Доказательство: Если в графе G нет циклов, то G является искомым остовным деревом, если в G есть цикл, то удалим из G какое-нибудь ребро, входящее в цикл. В результате этого получается некоторый подграф G1. По лемме 1 G1 – связный граф. Если в графе G1 нет циклов, то G1 есть искомое остовное дерево. В противном случае процесс продолжается. Этот процесс должен завершиться, т.к. Е – конечное множество.

Лемма 2. Если к связному графу добавить новое ребро на тех же вершинах, то в нём появится цикл.

Доказательство: Пусть G=(V, E) – связный граф. Пусть u V, v V, (u, v) E. Т.к. G – связный граф, то в нем есть цепь от v к u, при этом она является простой цепью соединяющей v и u. Поэтому во вновь полученном графе с добавленным ребром (u, v) имеется цикл C(u, v).

Лемма 3. Пусть в графе G=(V, E) имеется n вершин и m ребер. Тогда в G не менее n-m связных компонент. Если при этом в графе G нет циклов, то он состоит ровно из n-m связных компонент.

Доказательство: Пусть к некоторому графу H, содержащему вершины u и v добавляется ребро (u, v). Тогда, если u и v лежат в разных связных компонентах графа H, то число связных компонент уменьшается на единицу. Если u и v лежат в одной связной компоненте графа H, то число связных компонент не уменьшится. Таким образом, число связных компонент при добавлении ребра уменьшается не более чем на единицу. Значит, при добавлении m ребер, число связных компонент уменьшается не более чем на m. Т.к. граф G, можно получить из графа G1=(V,Ø), добавлением m ребер, то в графе G не менее n-m связных компонент. Пусть далее в графе G нет циклов, и пусть в процессе получения G из G1 добавляется ребро (u, v). Если бы u и v лежали в одной связной компоненте, то в G, согласно лемме 2, возникал бы цикл. Следовательно, u и v лежат в разных связных компонентах и при добавлении ребра (u, v)

23

число связных компонент уменьшается ровно на 1. Следовательно, G состоит ровно из n-m компонент.

Теорема 2. О различных определениях свободного дерева. (Свойства свободных деревьев).

Следующие пять определений эквивалентны:

1)G – свободное дерево

2)G – без циклов и m=n-1

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

4)G –связный граф, но при удалении любого ребра становиться несвязным

5)G – без циклов, но при добавлении любого ребра на тех же вершинах появляется цикл

Доказательство: Если доказать, что 1)2)3)4)5) 1), то из любого условия вытекает любое другое.

1) 2) Т.к. G – связный граф и G не содержит циклов, то n-m=1 по лемме 3. Отсюда m=n-1.

2) 3) По лемме 3 число связных компонент равно n-m=1, т.е. граф G – связный граф.

3) 4) При удалении одного ребра n-m=2. Тогда по лемме 3 число связных компонент не менее, чем n-m=2 т.е. граф несвязный.

4) 5) Если G имеет цикл, то согласно лемме 1 можно удалить одно ребро так, что граф останется связным. Согласно лемме 2, если добавить любое новое ребро к связному графу на тех же вершинах, то появиться цикл.

5)1) Доказательство ведётся от противного. Предположим, что если G несвязный граф и вершины u и v лежат в разных компонентах графа G, но добавление к G ребра (u, v) очевидно, не порождает циклов, что противоречит 5). Отсюда следует, что G связный граф. Теорема доказана.

Вершина в графе называется концевой (висячей), если её степень равна 1. Ребро инцидентное концевой вершине называется концевым. Конечное дерево, состоящее более чем из одной вершины, имеет хотя бы две концевые вершины и одно концевое ребро.

24

4.2. Ориентированные, упорядоченные и бинарные деревья.

Ориентированным деревом (ордеревом, корневым деревом) называется орграф со следующими свойствами.

1)Существует единственная вершина, полустепень захода которой равна 0. Она называется корнем ориентированного дерева.

2)Полустепень захода всех остальных вершин равна 1.

3)Каждая вершина достижима из корня.

Например:

а) все возможные ориентированные деревья с 3-я вершинами:

б) с 4-я вершинами :

Концевая (висячая) вершина ордерева называется листом. Путь из корня в лист называется ветвью.

Уровень вершины ордерева – это расстояние от корня до вершины. Корень имеет уровень 0. Вершины одного уровня образуют ярус дерева.

Эквивалентное определение ориентированного дерева.

Ордерево D – это конечное множество вершин, таких

что:

25

1) имеется одна вершина r, называемая корнем данного дерева;

2) остальные вершины содержаться в k попарно непере-

Множества D1,…,Dk называются поддеревьями. Упорядоченным деревом называется ориентированное

дерево, в котором:

1)задан порядок поддеревьев

2)каждое поддерево Di является упорядоченным поддеревом.

3)дерево с одной вершиной считается упорядоченным поддеревом.

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

Например: Имеются 3 диаграммы деревьев:

26

Как упорядоченные деревья, они все различны. Как ориентированные деревья D1=D2 D3. Как свободные деревья, они все изоморфны D1=D2=D3.

Терема 3. Число упорядоченных деревьев с m дугами не превосходит 4m.

Доказательство: Рассмотрим алгоритм обхода упорядоченного дерева, называемого «поиском в глубину». Этот обход рекурсивно описывается следующим образом:

1)Начать с корня. Пока есть деревья выполнять.

2)Перейти в корень очередного поддерева, обойти это поддерево в глубину.

3)Вернуться в корень исходного поддерева.

В результате «обхода в глубину» по каждой дуге проходят ровно 2 раза: один раз при переходе в очередное поддерево, второй раз – при возвращении из него. В соответствии с «обходом в глубину» строиться последовательность из нулей и единиц. На каждом шаге записывается нуль, если происходит переход в очередное поддерево, а единица – при возвращении из поддерева. В результате получается последовательность из нулей и единиц длины 2m, которая называется кодом дерева. По этому коду однозначно восстанавливается дерево, т.к. каждый очередной разряд однозначно указывает, начинать ли строить новое очередное поддерево или возвращаться на ярус ближе к корню. Таким образом, упорядоченных деревьев с m дугами не больше, чем последовательностей из нулей и единиц длины 2m. А их число равно 22m=4m. Теорема доказана.

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

Следствие. Число неизоморфных ориентированных или свободных деревьев с m ребрами не превосходит 4m. Доказательство: Выделив в неизоморфных свободных деревьях по одной вершине, мы получаем неизоморфные ориентированные деревья. Упорядочивая поддеревья в неизоморфных ори-

27

ентированных поддеревьях, мы получаем упорядоченные деревья. Поэтому число неизоморфных свободных деревьев с m ребрами не превосходит числа неизоморфных ориентированных деревьев с m дугами, которое в свою очередь не превосходит числа неизоморфных (различных) упорядоченных деревьев с m дугами. Отсюда из теоремы 3 следует утверждение следствия.

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

Пример: два различных бинарных дерева:

Эти деревья изоморфны как упорядоченные, ориентированные и свободные, но не изоморфны как бинарные деревья.

28

5.ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ГРАФЫ.

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

Содержательная постановка задачи о Кенигсбергских мостах дана в теме 1. Переформулируем эту задачу в терминах теории графов. Для этого рассмотрим следующий неориентированный мультиграф:

v1

v2 v3

v4

В этом графе вершины v1 и v4 соответствуют берегам, а v2 и v3 – островам. Ребра отображают мосты. Таким образом, на языке теории графов исходная задача формулируется следующим образом: существует ли в указанном мультиграфе цикл, содержащий все ребра данного мультиграфа?

Определение: Цепь (цикл), содержащая все ребра графа и притом по одному разу, называется эйлеровой цепью (эйлеровым циклом). Граф, содержащий эйлеров цикл, называется эйлеровым графом.

Теорема. Для того, чтобы конечный связный неориентированный мультиграф был эйлеровым необходимо и достаточно, чтобы все его вершины имели чётные степени.

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

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

29