Элементы теории графов
Графы - математические объекты.
Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология.
Эта теория тесно связана также со многими разделами математики, среди которых теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ.
Единого общепринятого определения графа нет. В зависимости от решаемой задачи принимается то или иное определение, которые похожи, но это не одно и то же.
Теория графов родилась на берегах Невы, в Санкт-Петербурге, и основоположником является Леонард Эйлер, публиковавший в 1736 решение задачи о Кенигсбергских мостах.
1736 год. Эйлер доказывает, что задача о Кёнигсбергских мостах не имеет решения. Центральная часть Калининграда – это два берега реки Перголя и два острова этой реки. Острова соединены между собой мостом и у одного острова 2+2 моста с берегами и у другого 1+1. Всего 7 мостов. Задача: обойти все четыре части суши – два берега и два острова, пройдя по каждому мосту по одному разу.
Следующие шаги в развитии теории графов принадлежат Г. Кирхгофу, применившему теорию графов в 1847 г. к теории электрических цепей и А. Келли, разработавшему в 1857 г. теорию деревьев и применившему ее к теории химических изомеров.
1930 год. Казимир Куратовский доказывает, что задача о трех домах и колодцах не имеет решения. Имеется три дома и три колодца. Нужно проложить тропика от каждого дома к каждому колодцу так, чтобы они не пересекались.
Родившись при решении головоломок и занимательных задач, в XX веке теория графов стала мощным средством решения проблем многих наук, широкая приложимость стала дополнительным стимулом ее бурного развития. Сам термин "граф" ровно на 200 лет моложе этой теории, он введен в употребление в 1936 г. выдающимся венгерским математиком Д. Кенигом.
1976 год. Аппель и Хейкен с помощью компьютера, перебрав около 2000 контр-вариантов показали, что достаточно 4-ёх красок для раскраски карты. Карта – это разбивка поверхности не пересекающимися областями.
Определение.
Н
еориентированным
графом
G называется множество N = {x,y,..} вместе с
множеством A = {(x,y),..}(некоторых
неупорядоченных пар), где множество N
конечно (т.е. число его элементов конечно),
а во множестве A нет элементов вида
(х,х). Элементы множества N называют
вершинами или узлами, элементы множества
A называют ребрами. Обозначение
неориентированного графа: G=(N,A)
N = {x,y,s,z} - множество вершин неориентированного графа G.
A = {(sx),(sy),(xz),(xy),(yz)} - множество ребер неориентированного графа G
Граф, вершина, ребро
Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, что
.
Ориентированным
графом (орграфом)
будем называть такую произвольную пару
G
= <V,
E>,
что
.
В обоих случаях множества V
и Е
будем называть соответственно множеством
вершин
и множеством ребер
графа G.
Элементы
множества Е
для орграфа называются дугами
Граф G задается множеством точек или вершин х1, х2, . . ., хn ,которое обозначается через X, и множеством линий или ребер a1, a2, . . ., an , которое обозначается символом A, соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (X, А).
Граф обычно изображается на плоскости в виде множества точек, соответствующих вершинам, и соединяющих их линий, соответствующих ребрам. Дуга в орграфе изображается линией со стрелкой, указывающей ориентацию дуги, т. е. направление от ее начала к концу
Л
иния,
изображающая ребро{и,
v},
или <и,
v>
(угловые
скобки используются для обозначения
дуг орграфа.),
соединяет точки, изображающие вершины
и, v
причем во втором случае стрелка обозначает
направление от и
к v
(рис. 1.1).
Рис. 1.1. а) Неориентированный граф; б) Ориентированный граф.
Дуга, ориентированный граф
Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом
Пример. (рис. (а)).
Соответствие
Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества Х в X, а граф в этом случае обозначается парой G = (X, Г).
Для
графа на рис. (а) имеем
,
т. е. вершиных2
и х5
являются конечными вершинами дуг, у
которых начальной вершиной является
х1
,
,
—пустое
множество,
.
Неориентированный граф
Е
сли
ребра не имеют ориентации, то граф
называетсянеориентированным
(неориентированный
дубликат или неориентированный двойник).
В случае когда G
= (X, А)
является ориентированным графом и не
учитывается направленность дуг из
множества А,
то неориентированный граф, соответствующий
G,
обозначается как
.
Пример. (рис. б)
Ориентированным графом или орграфом называется множество N = {x,y,..} вместе с множеством A = {(x,y),..}(некоторых упорядоченных пар), где множество N конечно (т.е. число его элементов конечно), а во множестве A нет элементов вида (х,х). Элементы множества N называют вершинами или узлами, элементы множества A называют дугами или ребрами. Обозначение неориентированного графа: G=(N,A)
В отличие от графа у орграфа пары (x,y) упорядочены.
N = {x,y,z,s} - вершины
A = {(sx),(sy),(xz),(xy),(yz)}
дуга (sx): s - начало дуги; x - конец дуги
дуга (yz): y - начало дуги; z - конец дуги
Из двух определений мы увидели, что графы бывают двух типов - неориентированные и ориентированные. В нашем курсе мы будем в основном заниматься ориентированными графами.
Для удобства вместо термина "ориентированный граф" будем употреблять термин граф(такое упрощение допускается во многих книгах).
Отметим, что из определения вытекает, что в графе не может быть петель, т.е. ребер, соединяющих вершины сами с собой.
Инцидентность, смешанный граф
Если ребро е имеет вид {и, v } или <и, v>, то будем говорить, что ребро е инцидентно вершинам и и v, в то время как вершины и и v смежны между собой.
Направление предполагается заданным от первой вершины ко второй, когда дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин, т. е. двумя концевыми вершинами дуги. Так, например, на рис. (а) обозначение (х1, х2), относится к дуге a1 , а (х2 , х1) — к дуге a2. Концевые вершины дуги инцидентны своей дуге и наоборот, дуга инцидентна своим концевым вершинам. Смешанный граф - вершины соединены дугами (a1, a2, a3, a4, a6, a7) и ребрами (a5).
Эквивалентный ориентированный граф
В
случае неориентированного графа или
графа, содержащего и дуги, и неориентированные
ребра, предполагается, что соответствиеГ
задает такой эквивалентный
ориентированный граф,
который получается
из исходного
графа заменой каждого неориентированного
ребра двумя противоположно направленными
дугами, соединяющими те же самые вершины.
Пример 1. (см., графы, изображенные на рис. (б) и (в))
Пример 2.
Так, например, для графа, приведенного на рис. (б), имеем
,
и
т. д.
Обратное соответствие
Поскольку
представляет собой множество таких
вершин
,
для которых в графе G
существует дуга (хi,
хj),
то через
естественно обозначить множество вершинхk,
для которых в G
существует дуга (хk,
хi).
Отношение
принято называтьобратным
соответствием.
Для графа, изображенного на рис (а),
имеем
и
т. д.
Для
неориентированного графа
для всех
.
Когда
отображение Г
действует не на одну вершину, а на
множество вершин
,
то под
)
понимают объединение
-
т.
е.
является множеством таких вершин
,
что для каждой из них существует дуга(хi,
хj)
в G,
где
.
Пример.
Для
графа, приведенного на рис. (а),
и
.
Отображение Г(Г(хi)) записывается как Г2(хi). Аналогично «тройное» отображение Г(Г(Г(хi))) записывается как Г3(хi) и т. д.
Пример.
Для графа, показанного на рис. (а), имеем:
Г2(х1) = Г(Г(x1)) = Г({х2, х5}) = {x1, x3, x4}
Г3(х1) = Г(Г2(x1)) = Г({x1, x3, x4}) = {x1, x2, x5} и т. д.
Аналогично понимаются обозначения Г-2 (xi), Г-3(xi) и т. д
Изоморфизм графов
Два графа G1 = <V1, E1> и G2 = <V2, E2> изоморфны (G1 ~ G2) если существует биекция φ: V1 → V2 сохраняющие смежность
е1
= (u,v)
E1
е2
= (φ
(u), φ
(v))
E2
Теорема. Изоморфизм графов есть отношение эквивалентности.
Графы
G
= <V,
E>,
G'
= <V',
E'>
изоморфны,
если существует такое взаимно однозначное
отображение f
из V
на V',
что для произвольных
имеем
(
в
случае ориентированных графов). Обычно
изоморфные графы не различаются между
собой.
Путь, ориентированный маршрут
П
утем
(или ориентированным
маршрутом)
ориентированного графа называется
последовательность дуг, в которой
конечная вершина всякой дуги, отличной
от последней, является начальной вершиной
следующей.
Пример. На рис. 2 последовательности дуг
а6, a5, a9, a8, a4 (1.1)
a1, a6, a5, a9 (1.2)
a1, a6, a5, a9, a10, a6, a4 (1.3)
являются путями.
Путем в графе G = <V, E> назовем последовательность вершин v0, v1,..., vk такую что k ≥ 0 п vi - vi+1 (или и vi → vi+1, если граф G — ориентированный), i = 0, ..., k - 1. Термин «путь» в теории графов используется только в отношении орграфов, для графов используются термины «цепь» или «маршрут». Вершины v0 и vk будем называть соответственно началом и концом пути, а число k —длиной пути. Путь, начало и конец которого совпадают, будем называть циклом. Введенный так термин «цикл» в теории графов используется только в отношении графов, для орграфов используется термин «контур».
Если все вершины пути v0, v1,..., vk различны, то будем говорить об элементарном пути. Соответственно цикл v1,..., vk (v1 = vk) будем называть элементарным, если вершины v1,..., vk различны.
Маршрут
есть неориентированный «двойник» пути,
и это понятие рассматривается в тех
случаях, когда можно пренебречь
направленностью дуг в графе. Таким
образом, маршрут
есть последовательность ребер
,
в которой каждое ребро
,
за исключением, возможно, первого и
последнего ребер, связано с ребрами
и
своими двумя
концевыми вершинами.
Пример.
Последовательности дуг
(1.4)
(1.5)
(1.6)
в графе, изображенном на рис. 2, являются маршрутами; черта над символом дуги означает, что ее ориентацией пренебрегают, т. е. дуга рассматривается как неориентированное ребро.
Смежные дуги, смежные вершины, степень вершины
Дуги а = (хi, хj), хi ≠ хj, имеющие общие концевые вершины, называются смежными. Две вершины хi и хj называются смежными, если какая-нибудь из двух дуг (хi, хj) и (хj, хi) или обе одновременно присутствуют в графе.
Если вершины x и y неориентированного графа G соединены ребром (x,y), то вершины называются смежными, в противном случае - несмежные.
Для неориентированного графа G: вершины, смежные вершине s - это x и y; смежные вершине x - это s,y,z; смежные вершине z - это x,y; смежные вершине y - это s,x,z.
Степень вершины определим как число ребер, инцидентных ей. Вершину нулевой степени будем называть изолированной (например, вершина v5 на рис. 1.1, а). Для вершин орграфа определяются полустепени захода (число заходящих в вершину дуг) и исхода (число выходящих дуг). Степень вершины определяется как сумма полустепеней захода и исхода
Компонентная связность
Пусть
G
= <V,
E>
—произвольный неориентированный граф,
и пусть
.
Пусть А
— множество
тех вершин
,
к которым существует путь из v.
Множество А
вместе с ребрами графа G,
инцидентными вершинам из А,
определяет некоторый подграф, называемый
компонентой
связности
графа G.
Очевидно, что множества вершин компонент
связности произвольного графа попарно
не пересекаются.
Ориентированная цепь
Если граф имеет цикл (необязательно простой), содержащий все рёбра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом.
Ориентированной цепью (простой путь) (или, короче орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза.
Пример.
Пути (а6, a5, a9, a8, a4) и (a1, a6, a5, a9) являются орцепями, а путь (a1, a6, a5, a9, a10, a6, a4) не является таким, поскольку дуга a6 в нем используется дважды.
Простая орцепь
IIростой орцепью (элементарный путь) называется такой путь, в котором каждая вершина используется не более одного раза.
Пример.
Путь (a1, a6, a5, a9) является простой орцепью, а пути (а6, a5, a9, a8, a4 1.1) и (1.3) — нет.
Простая орцепь является также орцепью, но обратное утверждение неверно.
Пример 1. Путь (1.1) является орцепью, но не простой орцепью.
Пример 2. Путь (a1, a6, a5, a9) является орцепью и простой орцепью.
Пример 3. Путь (1.3) не является ни орцепью, ни простой орцепью.
Цепи, простые цепи
Точно так же, как были определены орцепи и простые орцепи, можно определить цепи (простой маршрут) и простые цепи (элементарный маршрут).
Пример.
Маршрут (1.4) есть цепь и простая цепь, маршрут (1.5) — цепь, но не простая цепь, а маршрут (1.6) не является ни цепью, ни простой цепью.
Путь или маршрут можно изображать также последовательностью вершин.
Пример.
Путь (1.1) можно представить последовательностью вершин х2, х5, х4, х3, х5, х6 и такое представление часто оказывается более полезным в тех случаях, когда осуществляется поиск простых орцепей или простых цепей.
Вес, стоимость
Иногда дугам графа G сопоставляются (приписываются) числа — дуге (хi, хj) ставится в соответствие некоторое число cij называемое весом, или длиной, или стоимостью (ценой) дуги.
Связность
Две вершины в графе называются связным, если существует соединяющая их простая цепь. Граф называется связным, если все его вершины связны.
Теорема. Граф связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.
Пусть G(V,E) – связный граф, u и v – две его несмежные вершины. Две цепи < u, v > называются вершинно-непересекающимися, если у них нет общих вершин, отличных от u и v.
Теорема (Менгера). Пусть u и v – несмежные вершины в графе G. Наименьшее число вершин в множестве, разделяющем u и v равно наибольшему числу вершинно-непересекающихся простых <u,v>-цепей:
max|P(u,v) | = min|S(u,v)|
Граф со взвешенными дугами
Граф G = (N, A) называется взвешенным, если на множестве дуг A определена некоторая функция l: A → R, которую называют весовой функцией.
Тем
самым в взвешенном графе G
каждой дуги x
A
поставлено в соответствие некоторое
действительное число l(x).
Значение l(x)
называются длиной
дуги x.
Для любого пути Pi взвешенного графа G обозначающим через l(Pi) сумму длин входящих в Pi дуг, при этом каждая дуга учитывается столько раз, сколько она входит в путь. Величину l(Pi) называют длиной пути Pi в взвешенном графе G.
В мультиграфе не допускаются петли, но пары вершин могут соединяться более чем одним ребром: эти ребра называют кратными и противоположными.
Если допускаются петли, противоположные и кратные ребра, получаем псевдограф.
Определение. Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G.
Дуги 8,9 - называются параллельными (кратными). Дуги 5,6 - называются противоположными. Вершина k - называется изолированной.
Определение.
Полным графом
называется
граф с n вершинами без петель, кратных
и противоположных дуг (ориентация
безразлична), у которого любые две
вершины соединены дугой.
Определение.
Полным двудольным графом
называется
граф с n+m вершинами без петель, кратных
и противоположных дуг (ориентация
безразлична), у которого множество
вершин разбито на два непересекающихся
подмножества с n и m вершинами так, что
любые две вершины различных подмножеств
соединены дугой и никакие две вершины
одного подмножества не соединены дугой.
3.
Матрица смежности: строки и столбцы соответствуют варшинам. Элемент матрицы
Пример. Составить матрицу смежности для графа G:
Заполняем строчку s: если есть дуга из s в другую вершину графа G, то ставим 1, если нет - 0. Из s есть дуги в x:(sx) и в y:(sy). По аналогии заполняем другие строки.
Матрица инцедентности: строки соответствуют вершинам, а столбцы дугам, при этом в столбце, соответствующем дуге (x,y) 1 ставится в строке x, -1 в строке y, остальные элементы равны 0.
Рисунок 3.1.13.
4.
Определение.
Цепью длины n
на
графе (N,A) называется последовательность
дуг
такая,
что у любой дуги
одна
вершина общая с дугой f(i-1), а другая -
общая с дугой f(i+1).
Вершина дуги f(1), не являющаяся общей с дугой f(2), называется началом цепи, вершина дуги f(n), не являющаяся общей с дугой f(n-1), называется концом цепи.
Если начало цепи совпадает с ее концом, то цепь называется циклом.
Определение.
Путем длины n
на
графе (N,A) называется последовательность
дуг
такая,
что у любой дуги f:(i)(i=1..n) начала дуги
совпадает с концом дуги f(i-1), а конец
дуги совпадает с началом дуги f(i+1).
Начало дуги f(1) называется началом пути, конец дуги f(n) называется концом пути.
Если начало пути совпадает с концом пути, то путь называют контуром.
Из 2 в 7 путь длины 6:(2,1),(1,3),(3,4),(4,5),(5,6),(6,7).(Двигается по направлению стрелок). Контур длины 3:(2,1),(1,3),(3,2).
Из 2 в 8 цепь длины 4:(2,3),(3,4),(4,5),(5,8). Цикл длины 4:(2,1),(1,4),(4,3),(3,2).
Определение. Граф называется связным, если для любых двух его вершин x и y существует цепь, соединяющая x и y.
Определение. Говорят, что вершина у графа G достижима из вершины x, если существует путь из x в y.
вершина 2 достижима из 1:(1,2)
вершина 4 достижима из 1:(1,2),(2,4)
вершина 3 не достижима из 1.
Определение. Граф называется сильно связным, если для любых двух его вершин x и y, существует путь соединяющий x и y.
Определение. Компонентой сильной связности графа G называется его сильно связный подграф, не являющийся подграфом никакого другого сильно связного подграфа G.
Получили 4 компоненты сильной связности графа G1 (вершина является компонентой сильной связности).
Рисунок 3.1.22.
Получим 2 компоненты сильной связности графа G2.
Определение.
Пусть дан граф G=(N,A)(N=[V1,...,Vn]). Матрицей
достижимости графа G называется квадратная
матрица
порядка
n, у которой
,
если вершина Vj достижима из Vi, и
-
в противоположном случае.
Определение.
Матрицей сильной связности графа G=(N,A)
называется матрица
порядка
n, у которой
,
если вершина Vj достижима из Vi, и
-
в противоположном случае.
Матрица достижимости.
Матрица достижимости: по диагонали ставим 1 (считается что вершина достижима сама из себя); заполняем строку X1 - если вершина достижима из X1 то в соответствующем этой вершине столбце ставим 1, в противном случае 0; по аналогии заполняем остальные строки.
Матрица сильной связности.
Матрица сильной связности: по диагонали ставим 1; заполняем строку X1 - если вершина достижима из X1 и X1 достижима из этой вершины, то в соответствующем этой вершине столбце ставим 1, в противном случае 0; по аналогии заполняем остальные строки.
Замечание. По матрице сильной связности можно выписать компоненты сильной связности.
Выпишем компоненты сильной связности для рассмотренного графа.
Рассмотрим строку X1: вычеркнем столбцы, в которых стоят единицы X1, X2, X3.
Теперь вычеркнем строки: X1, X2, X3.
При пересечении столбцов X1, X2, X3 и строк X1, X2, X3 получилась таблица, т.е. вершины X1, X2, X3 сильно связны между собой и образуют компоненту сильной связности.
Далее рассмотрим оставшиеся невычеркнутые строки: X4 и X5.
Вычеркиваем в строке X4 столбец, в котором стоит единица X4. Теперь вычеркиваем строку X4. При пересечении строки X4 и столбца X4 получили
Вывод X4 - компонента сильной связности. Проделав аналогичную операцию для строки X5, получим X5 - компонента сильной связности.
Итак, у графа G три компоненты сильной связности.
5. Операции над графами (объединение, пересечение).
Определение.
Объединением графов
называется
граф, у которого объединены множество
вершин и множество дуг графов
.
Обозначение
.
Пример 1.
G1
G2
G1UG2
Определение.
Пересечением графов
граф,
у которого пересечены множество вершин
и множество дуг графов
.
Обозначение
.
Пример
2.
Рассмотрим графы
из
примера 1. Построим их пересечение:
выберем одинаковые вершины и дуги.
Подграф
Подграфом
графа G
= <V,
E>
будем называть такой произвольный граф
G'
= <V',
E'>,
что
и
.
В отечественной
литературе по теории графов граф G'
называется чаще частью
графа, или частичным
графом, под
подграфом же понимается частичный граф,
удовлетворяющий дополнительному условию
.
Контрольные вопросы и задачи
Лекция № 8
Когда вы убедитесь, что теорема верна, вы начинаете ее доказывать.
Традиционный профессор математики. А. Пойа Математика и правдоподобные рассуждения. М.: Наука, 1975 стр. 97
ДЕРЕВЬЯ
Деревья важны не только потому, что они находят приложения в различных областях знаний, но и Вилу особого положения их в самой теории графов. Последнее вызвано предельной простотой строения деревьев, поэтому при решении какой либо задачи о графах ее сначала исследуют на деревьях.
Одним из простейших классом графов являются деревья. Граф является деревом, если он удовлетворяет следующей теореме.
Теорема. Для графа G= <X,U> следующие утверждения эквивалентны:
1) G - дерево;
2) любые две вершины в графе G соединены единственной простой цепью;
3) граф G связен и имеет |X| - 1 ребер;
4) граф G не содержит циклов и имеет |X| - 1 ребер;
5) граф G не содержит циклов, но добавление ребра между любыми двумя несмежными вершинами приводит к появлению одного цикла;
6) граф G связен, но утрачивает это свойство после удаления любого ребра.
Деревья широко применяются в программировании.
Свободные деревья
Граф без циклов называется ациклическим, или лесом. Связный ациклический граф называется (свободным) деревом. Компонентами связности леса являются деревья.
Граф G, в котором q(G) = р(G)-1, называется древовидным.
В
ациклическом графе G
z(G)
= 0. Пусть
и, v
—
несмежные вершины графа G,
х = (и, v)
E.
Если граф G+x
имеет только один простой цикл, z(G+х)=
1, то
граф G
называется субциклическим.
Пример
На рис. 9.1 показаны диаграммы всех различных (свободных) деревьев с 5 вершинами, а на рис. 9.2 — диаграммы всех различных (свободных) деревьев с 6 вершинами.
Рис. 8.1. Свободные деревья с 5 вершинами
Рис. 8.2. Свободные деревья с 6 вершинами
Основные свойства деревьев
Следующая теорема устанавливает, что два из четырех свойств — связность, ацикличность, древовидность и субцикличность — характеризуют граф как дерево.
Теорема
Пусть G(V, Е) — граф с р вершинами, q ребрами, k компонентами связности и z простыми циклами. Пусть далее х — ребро, соединяющее любую пару несмежных вершин в G. Тогда следующие утверждения эквивалентны:
1. G — дерево, то есть связный граф без циклов, k(G) = 1&z(G) = 0;
2. любые две вершины соединены в G единственной простой цепью,
.
3. G — связный граф, и любое ребро есть мост,
;
4. G — связный и древовидный,
;
6. G — ациклический и субциклический,
;
7. G — связный, субциклический и неполный,
;
8. G — древовидный и субциклический (за двумя исключениями),
;
Доказательство
Рис. 8.3. К доказательству теоремы о свойствах деревьев
[1
2]От противного.
Пусть существуют две цепи <и,
v>
(рис. 9.3, слева). Тогда w,
w2
— простой цикл.
3.]
Имеем:
и,
v
!,
следовательно,
.
Далее от противного. Пусть реброх
— не
мост. Тогда в G
- х концы этого ребра
связаны цепью. Само ребро х
— вторая цепь.
[3
4.]
Индукция пор.
База: р = 1
q
= 0. Пусть
для всех связанных графовG
с числом
вершин меньше р,
у которых любое ребро суть мост. Тогда
удалим из G
ребро х
(которое является мостом). Получим две
компоненты G'
и G",
удовлетворяющие индукционному
предположению. Имеем:
.
[4
5.]
От противного. Пусть есть цикл сп
вершинами и п
ребрами. Остальные р
- п вершин
имеют инцидентные им рёбра, которые
связывают их с циклом, Следовательно,
q
≥ р,
что противоречит условию q
= р - 1.
[5
1.]
Граф без циклов, следовательно, его
компоненты — деревья. Пусть ихk;.
Имеем:
i
= У(pi-1)
= Уpi-k
= p-k
Но q=p-1, следовательно, k = 1.
[5
6.]
По ранее доказанному5
1
2. Имеем:
.
Соединив две несмежные вершины, получим
единственный простой цикл.
[6
7.]
Прир ≥ 3
граф Кр
содержит цикл, следовательно, G
≠ Кр.
Далее от противного. Пусть G
несвязен, тогда при соединении ребром
двух компонент связности цикл не
возникнет.
[7
2.]
Имеемk(G)
= 1,
следовательно,
.
Пусть цепь не единственная. Тогда
существует цикл Z,
причем Z
= К3,
= С3.
Действительно, пусть Z
> С3,
тогда, соединив две несмежные вершины
этого цикла, получим два цикла. Но G
связен и G
≠ К3,
следовательно, существует другая вершина
w,
смежная с Z
= К3
(см. рис. 9.3, справа). Если w
смежна
более чем с одной вершиной Z,
то имеем
больше одного цикла. Если w
смежна только с одной вершиной Z,
то соединив её с другой вершиной, получим
два цикла.
[7
8.]
Имеемk(G)
= 1,
следовательно, G
≠ К2
К3,
G
≠ К1
К3.
Имеем по доказанному: 7
2
3
4, то есть
q
= р- 1.
[8
5.]
От противного. Пусть вG
есть цикл Z
= Сп.
Если n
> 3, то
если внутри Z
уже есть
смежные вершины, имеем два цикла. Если
в Z
нет смежных вершин, то, соединив несмежные
вершины в Z,
получим два цикла. Следовательно, Z
= К3.
Этот цикл Z
является компонентой связности G.
Действительно, пусть это не так. Тогда
существует вершина w,
смежная с
Z.
Если w
смежна более чем с одной вершиной Z,
то имеем больше одного цикла. Если w
смежна
только с одной вершиной Z,
то, соединив её с другой вершиной, получим
два цикла. Рассмотрим G
:=G
- Z.
Имеем: р =
р' + 3, q
= q'
+ 3. Но q
= р - 1,
следовательно, q'
= р' - 1.
Отсюда z(С')
= 0, так как
один цикл уже есть. Следовательно,
компоненты G'
— деревья.
Пусть их k.
Имеем:
I
=
У(pi-1)
= Уpi-k
= ṕ-k
но q' = p' -1, следовательно. k = 1. то есть дерево одно. Если в этом дереве сбединить несмежные вершины, то получим второй цикл. Два исключения: деревья, которые не имеют несмежных вершин, — это К1 и K2.
Общая схема доказательства представлена на рис. 9.4. Граф доказательства сильно связен, следовательно, теорема доказана.
Вычисление
Рис. 9.4. Схема доказательства теоремы о свойствах деревьев
От противного
Следствие 1 В любом нетривиальном дереве имеются по крайней мере две висячие вершины.
Доказательство
Рассмотрим
дерево G(V,
Е).
Дерево — связный граф, следовательно,
.
Далее
от противного. Пусть
.
Тогда
2q = Уd(vi) > 2(р - 1) + 1 = 2р - 1.
Но q = р - 1, то есть 2q = 2р - 2. Имеем противоречие: 2р - 2 2 > 2р - 1.
Следствие 2. Каждая не висячая вершина свободного дерева является точкой сочленения.
Доказательство
Пусть
G(V,
Е) —
дерево, v
V
и
d(v)
>
1. Тогда
и,
w
V(u,v)
E&
(u,
w)
E.
Граф G
связен, поэтому существует цепь (и,
w).
Если v
<и,w>,
то имеем цикл v,
<и,w>
,v,
что
противоречит тому, что G
— дерево.
Следовательно,
и,
w
V
<и,w>
v
<u,
w>
и по
теореме 8.1.2 вершина v
— точка
сочленения.
Центр дерева
Свободные деревья выделяются из других графов тем, что их центр всегда оправдывает своё название.
Теорема
Центр свободного дерева состоит из одной вершины или из двух смежных вершин:
Z(G)
= 0&k(G)
= 1 → С(G)
= К1
С(G)
= К2.
Доказательство
Для
деревьев К1
и К2
утверждение теоремы очевидно. Пусть
теперь G(V,Е)
— некоторое
свободное дерево, отличное от К1
и К2.
Рассмотрим граф G'(V',Е'),
полученный
из G
удалением всех висячих вершин. Заметим,
что G'
— дерево,
поскольку ацикличность и связность при
удалении висячих вершин сохраняется.
Далее, если эксцентриситет еG(v)
= d(v,и),
то и
— висячая
вершина в дереве G
(иначе можно было бы продолжить цепь
«за» вершину и).
Поэтому
v
V' еG(v)
= еG'(v)+1
и при удалении висячих вершин
эксцентриситеты оставшихся уменьшаются
на 1.
Следовательно, при удалении висячих
вершин центр не меняется, С(G)
= С(G'}.
Поскольку дерево G
конечно, то удаляя на каждом шаге все
висячие вершины, в конце концов за
несколько шагов придём к К1
или К2.
Ориентированные, упорядоченные и бинарные деревья
Ориентированные (упорядоченные) деревья являются абстракцией иерархических отношений, которые очень часто встречаются как в практической жизни, так и в математике и программировании. Дерево (ориентированное) и иерархия — это равнообъёмные понятия.
Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами.
1. Существует единственный узел r, полустепень захода которого равна 0, d+(r) = 0. Он называется корнем ордерева.
2.
Полустепень захода всех остальных узлов
равна 1,
v
V
\ {
r
} d+(r)
= 1 == 1.
3.
Каждый узел достижим из корня,
v
V
\ {
r
}
<v,
u
>.
Пример
На рис. 9.5 приведены диаграммы всех различных ориентированных деревьев с 3 узлами, а на рис. 9.6 показаны диаграммы всех различных ориентированных деревьев с 4 узлами.
Теорема. Ордерево обладает следующими свойствами:
1. q = р - 1;
2. если в ордереве забыть ориентацию дуг, то получится свободное дерево;
3. в ордереве нет контуров
4. для каждого узла существует единственный путь, ведущий в этот узел из корня;
5. подграф, определяемый множеством узлов, достижимых из узла v, является ордеревом с корнем v (это ордерево называется поддеревом узла v);
6. если в свободном дереве любую вершину назначить корнем, то получится ордерево.
рис. 9.5. Ориентированные деревья с 3 узлами
Рис. 9.6. Ориентированные деревья с 4 узлами
Доказательство
1. Каждая дуга входит в какой-то узел. Из п. 2 определения 9.2.1 имеем:
v
V
\ {
r
} d+(r)
= 1, где r
— корень.
Следовательно, q
= р - 1.
2.
Пусть G
— ордерево, граф G'
получен из G
забыванием ориентации рёбер, r
— корень.
Тогда
v1,
v2
V
(v1,
r)
G'
&
(r,
v2)
G',
следовательно,
v1,
v2
(v1,
v2)
и граф G'
связен. Таким образом, учитывая п. 4.
теоремы 9.1.2, G'-дерево.
3. Следует из пункта 2.
4. От противного. Если бы в G существовали два пути из и в v, то в G' имелся бы цикл.
5.
Пусть Gv
— правильный подграф, определяемый
множеством узлов, достижимых из v.
Тогда
dGv+(v)
= 0, иначе
узел v
был бы
достижим из какого-то узла v'
Gv,
и, таким образом, в Gv,
а значит, и в G
имелся бы контур, что противоречит
пункту 3. Далее имеем:
v'
Gv\
{v}
d+(v')
= 1, так как
Gv
G.
Все узлы Gv
достижимы из v
по построению.
По определению 9.2.1 получаем, что Gv
— ордерево.
6. Пусть вершина r назначена корнем и дуги последовательно ориентированы «от корня» обходом в глубину. Тогда d+(r) = 0 по построению;
v
V
- d+(v)
= 1, так как
входящая дуга появляется при первом
посещении узла; все узлы достижимы из
корня, так как обход в глубину посещает
все вершины связного графа. Таким
образом, по определению 9.2.1 получаем
ордерево.
Следствие. Алгоритм поиска в глубину строит ордерево с корнем в начальном узле.
Каждое свободное дерево определяет не более р ориентированных деревьев. Таким образом, общее число различных ордеревьев с р узлами не более чем в р раз превосходит общее число различных свободных деревьев с р вершинами
Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева — это расстояние от корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.
Замечание
Наряду с «растительной» применяется еще и «генеалогическая» терминология. Узлы, достижимые из узла и, называются потомками узла и (потомки образуют поддерево). Если в дереве существует дуга (u, v), то узел и называется отцом (или родителем) узла v, а узел v называется сыном узла и. Сыновья одного узла называются братьями.
Эквивалентное определение ордерева
Ордерево Т — это конечное множество узлов, таких что:
1. Имеется один узел r, называемый корнем данного дерева.
2. Остальные узлы (исключая корень) содержатся в k; попарно непересекающихся множествах Т1,... , Тk каждое из которых является ордеревом (k ≥ 0).
Т ≡ {{r}, Т1,.. ., Тk}.
Нетрудно видеть, что данное определение эквивалентно определению 9.2.1. Достаточно построить орграф, проводя дуги от заданного узла r к корням поддеревьев Т1,.. ., Тk и далее повторяя рекурсивно этот процесс для каждого из поддеревьев.
Упорядоченные деревья
Множества Т1,.. ., Тk в эквивалентном определении ордерева являются поддеревьями. Если относительный порядок поддеревьев Т1,.. ., Тk фиксирован, то ордерево называется упорядоченным.
Пример
Ориентированные и упорядоченные ориентированные деревья интенсивно используются в программировании.
1. Выражения. Для представления выражений языков программирования, как правило, используются ориентированные упорядоченные деревья. Пример представления выражения а+b*с показан на рис. 9.7, а.
2. Для представления блочной структуры программы и связанной с ней структуры областей определения идентификаторов часто используется ориентированное дерево (может быть, неупорядоченное, так как порядок определения переменных в блоке в большинстве языков программирования считается несущественным). На рис. 9.7.б показана структура областей определения идентификаторов а, b, с, d е, причем для отображения иерархии использованы вложенные области.
3. Для представления иерархической структуры вложенности элементов данных и/или операторов управления часто используется техника отступов, показанная на рис. 9.7, в.
4. Структура вложенности каталогов и файлов в современных операционных системах является упорядоченным ориентированным деревом. Обычно для изображения таких деревьев применяется способ, показанный на рис. 9.7, г.
5. Различные «уравновешенные скобочные структуры» (например (а(b)(с(d)(е)))) являются ориентированными упорядоченными деревьями.
Рис. 9.7. Примеры изображения деревьев в программировании
Отступление
Тот факт, что большинство систем управления файлами использует ориентированные деревья, отражается даже в терминологии — «корневой каталог диска».
Замечание
Общепринятой практикой при изображении деревьев является соглашение о том, что корень находится наверху и все стрелки дуг ориентированы сверху вниз, поэтому стрелки можно не изображать. Таким образом, диаграммы свободных, ориентированных и упорядоченных деревьев оказываются графически неотличимыми, и требуется дополнительное указание, дерево какого класса изображено на диаграмме. В большинстве случаев это ясно из контекста.
Пример
На рис. 9.8 приведены три диаграммы деревьев, которые внешне выглядят различными. Обозначим дерево слева — (1), в центре — (2) и справа — (3). Как упорядоченные деревья, они все различны: (1) ≠ (2), (2) ≠ (3), (3) ≠ (1). Как ориентированные деревья (1) = (2), но (2) ≠ (3). Как свободные деревья, они все изоморфны: (1) = (2) = (3).
Рис. 9.8. Диаграммы деревьев
Бинарные деревья
Бинарное (или двоичное) дерево - это конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев - левого и правого.
Бинарное дерево не является упорядоченным ордеревом.
Пример
На рис. 9.9 приведены две диаграммы деревьев, которые изоморфны как упорядоченные, ориентированные и свободные деревья, но не изоморфны как бинарные деревья.
Рис. 9.9. Два различных бинарных дерева
Замечание. Понятие двоичного допускает обобщение, т-ичным деревом называется конечное множество узлов, которое либо пусто, либо состоит из корня и т непересекающихся т-ичных деревьев, имеющих номера 1,... ,т. Большая часть утверждений и алгоритмов для двоичных деревьев может быть сравнительно легко распространена и на т-ичные деревья (с соответствующими модификациями). Поэтому, хотя на практике т-ичные деревья и используются достаточно часто, здесь мы ограничиваемся только двоичными деревьями.
Представление деревьев в компьютере
Обсуждению представлений деревьев можно предпослать в точности те же рассуждения, что были предпосланы обсуждению представлений графов (см. 7.4). Кроме того, следует подчеркнуть, что задача представления деревьев в программе встречается гораздо чаще, чем задача представления графов общего вида, а потому методы ее решения оказывают еще большее влияние на практику программирования.
Представление свободных деревьев
Для представления деревьев можно использовать те же приёмы, что и для представления графов общего вида — матрицы смежности и инциденций, списки смежности и другие. Но используя особенные свойства деревьев можно предложить существенно более эффективные представления.
Рассмотрим следующее представление свободного дерева, известное как код Прюфера. Допустим, что вершины дерева T(V, Е) занумерованы числами из интервала 1..р. Построим последовательность А: аrrау [1..р- 1] оf 1..р в соответствии с алгоритмом 9.1
Алгоритм 9.1. Построения кода Прюфера свободного дерева
Вход: Дерево T(V,Е) в любом представлении, вершины дерева занумерованы числами 1 ... р произвольным образом.
Выход: Массив А: аrrау [1...р- 1] оf 1..р — код Прюфера дерева Т.
for: from 1 to p – 1 do
v:
= тin
{k
V|d(k)
= 1} { выбираем
вершину v
—
висячую вершину с наименьшим номером
}
А[i]: = Г(v) { заносим в код номер единственной вершины, смежной с v}
V: = V — v { удаляем вершину v из дерева }
end for
По построенному коду можно восстановить исходное дерево с помощью алгоритма 9.2.
Алгоритм 9.2. Распаковки кода Прюфера свободного дерева
Вход: Массив А: Массив А: аrrау [1...р- 1] оf 1..р — код Прюфера дерева Т.
Выход: Дерево T(V,Е), заданное множеством рёбер Е, вершины дерева занумерованы числами 1...р.
Е:
=
{ в начале множество рёбер пусто}
В:= 1...р { множество неиспользованных номеров вершин }
for: from 1 to p – 1 do
v:
= тin
{k
В |
j
≥ i
k
≠ A[j]}
{ выбираем вершину v;
— неиспользованную вершину с наименьшим
номером, который не встречается в остатке
кода Прюфера }
Е: = Е + (v, А[i]) {добавляем ребро (v, А[i]) }
В :=В - v { удаляем вершину v из списка неиспользованных}
end for
Обоснование
Код Прюфера действительно является представлением свободного дерева. Чтобы убедиться в этом, покажем, что если Т' — дерево, построенное алгоритмом 9.2 по коду А, который построен алгоритмом 9.1 по дереву Т, то Т' изоморфно Т, Т' ~ Т.
Для
этого установим отображение f:
1..р → 1..р
между номерами вершин в деревьях Т,
и Т'
по порядку выбора вершин в алгоритмах:
если вершина v
выбрана
на i-ом
шаге алгоритма 9.1, то вершина f(v)
выбрана на i-ом
шаге алгоритма 9.2.
Заметим, что Dom
f
= 1..р,
поскольку висячие вершины есть в любом
дереве и удаление висячей вершины
оставляет дерево деревом. Далее, Iт
f
= 1..р,
поскольку на i-ом
шаге алгоритма 9.2
использовано i
- 1 число
из р
чисел и остаётся р
– i
+ 1 чисел,
а в хвосте кода Прюфера занято не более
р – i
чисел.
Более того,
v
f(v)
= v.
Действительно,
номера вершин, которые являются висячими
в исходном дереве, не появляются в коде
Прюфера (кроме, может быть, одной висячей
вершины с наибольшим номером), а номера
вершин, которые не являются висячими,
обязательно появляются. Поскольку при
выборе первой вершины v
в алгоритме
9.1
все вершины с меньшими номерами не
являются висячими, их номера будет
присутствовать в коде и, значит, не могут
быть использованы на первом шаге
алгоритма 9.2.
Таким образом, на первом шаге алгоритм
9.2
выберет ту же вершину v.
Но после
удаления вершины v
на втором
шаге снова имеется дерево, к которому
применимы те же рассуждения.
Итак, f - тождественное и, значит, взаимно-однозначное отображение. Заметим теперь, что для определения i-ого элемента кода на i-ом шаге алгоритма 9.1 используется, а затем удалется ребро (v, А[i]) и в точности то же ребро добавляется в дерево Т' на i-ом шаге алгоритма 9.2. Следовательно, f - взаимно-однозначное отображение, сохраняющее смежность и Т ~ Т'.
Пример
Для дерева, представленного на рис. 9.10, код Прюфера 7, 9, 1, 7, 2, 2, 7, 1, 2, 5, 12. На этом рисунке числа в вершинах - это их номера, а числа на рёбрах указывают порядок, в котором будут выбираться висячие вершины и удаляться рёбра при построении кода Прюфера.
Рис. 9.10. Построение кода Прюфера
Замечание
Код Прюфера — наиболее экономное по памяти представление дерева. Его можно немного улучшить, если заметить, что существует всего одно дерево с двумя вершинами — К2, а потому информацию о «последнем ребре» можно не хранить, она восстанавливается однозначно.
Представление бинарных деревьев
Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Для потомков одного узла (братьев) упорядоченного ордерева определено отношение старше-младше (левее-правее). Всякое упорядоченное дерево можно представить бинарным деревом, проведя правую связь к старшему брату, а левую — к младшему сыну.
Пример
На рис. 9.11 приведены диаграммы упорядоченного и соответствующего ему бинарного деревьев.
Таким образом, достаточно рассмотреть представление в компьютере бинарных деревьев.
Замечание
Из данного представления следует, что множество бинарных деревьев взаимнооднозначно соответствует множеству упорядоченных лесов упорядоченных деревьев.
1. Списочные структуры: каждый узел представляется записью типа N, содержащей два поля (t и r) с указателями на левый и правый узлы и еще одно поле r для хранения указателя на информацию об узле. Дерево представляется указателем на корень. Тип N обычно определяется следующим образом:
Обозначим через n(p) объем памяти, занимаемой представлением бинарного дерева, где - число узлов. Наиболее часто используются следующие представления бинарных деревьев.
N = record i: info; l,r: ↑ N end record
Для этого представления n(p) = 3p
Контрольные вопросы
Что называется графом? Ориентированным графом? Примеры.
Что такое степень вершины?
Перечислите основные понятия, связанные с неориентированными графами.
Перечислите основные понятия, связанные с ориентированными графами.
Перечислите способы задания графов.
В чем состоит аналитический способ задания графа?
В чем состоит геометрический способ задания графа?
В чем состоит матричный способ задания графа?
Какая матрица называется матрицей смежности графа?
Какая матрица называется матрицей смежности графа?
Какая матрица называется матрицей инцидентности графа?
Что называется маршрутом, циклом и цепью графа?
Сформулируйте понятие связности графа. Какой граф называется связным?
Какие два графа называются изоморфными?
Сформулируйте алгоритм изоморфизма двух графов.
Перечислите операции над графами.
Дайте определение эйлерова графа.
Сформулируйте алгоритм построения эйлерова цикла.
Какой граф называется гамильтоновым?
Лекция № 9