Тема. Теория конечных графов

Лекция 7. Неориентированные графы: основные понятия; маршруты, цепи, циклы; связность; деревья и леса.

Основные понятия

Пусть V - непустое множество, V(2) - множество всех его двухэлементных подмножеств, т.е. (u,v) V(2), если u,v V.

Определение. Неориентированным графом (или просто графом) называется пара G=(V,E), где E V(2).

Элементы множества V называются вершинами графа, а элементы множества E - ребрами.

Определение. Если e=(u,v) E, то вершины u,v называются смежными, а ребро e=(u,v) называется ребром, инцидентным вершинам u и v.

Если V и E - конечные множества, то G называется конечным графом.

Рассмотрим графы G=(V,E) и G*=(V*,E*),и пусть ϕ:V→V*- биекция (взаимно однозначное отображение).

Определение. Если для любых вершин u и v графа G их образы ϕ(u) и ϕ(v) смежны в G* тогда и только тогда, когда u и v смежны в G, то эта биекция называется изоморфизмом графа G на граф G*. Если такой изоморфизм существует, то граф G изоморфен графу

G*.

Пример 7.1.

Изоморфные графы

Неизоморфные графы

26

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

Определение. Если ребро e инцидентно вершинами u и v, то такие вершины называются граничными точками ребра e.

Определение. Если u и v - граничные точки ребра e и u=v, то e называется петлей (в этом случае u смежна сама с собой).

Определение. Если вершины u и v инцидентны ребрам e1 и e2, то ребра e1 и e2 называются параллельными ребрами.

Определение. Ребра e1 и e2 называются смежными, если они имеют, по крайней мере, одну общую граничную точку.

Замечание. Смежность является отношением между двумя подобными элементами (между вершинами или между ребрами), а инцидентность есть отражение между разнородными элементами.

Определение. Число ребер, инцидентных вершине v (петля учитывается дважды), называется степенью вершины v и обозначается δ(v). Вершина v изолирована, если δ(v)=0.

Определение. Граф называется вырожденным (пустым) если все его вершины являются изолированными.

Теорема. В конечном графе число вершин нечетной степени четно.

Доказательство. Рассмотрим конечный граф G=(V,E). ПустьV и E число вершин и ребер соответственно. Учитывая, что появление каждого нового ребра добавляет по единице к степеням двух вершин (или в случае петли два к степени одной вершины), имеем

∑δ(v) = 2 E .

v V

Если V0 и V1 - множества вершин, имеющих четные и нечетные степени соответственно, то очевидно ∑δ(v) четно, как конечная

v V0

сумма четных чисел. Следовательно

∑δ(v) −∑δ(v) = ∑δ(V )

также обязательно четно. В сумме ∑δ(V ) слагаемыми являют-

v V1

ся нечетные степени вершин. Следовательно, количество

27

вершин с нечетной степенью должно быть четно.

Определение. Граф называется полным, если любые две его

вершины смежны. Полный граф с n вершинами имеет n ребер.

2

Определение. Рассмотрим граф G=(V,E). Граф G1=(V1,E1) называется подграфом G=(V,E) тогда и только тогда, когда

1.V1 V, E1 E

2.Если ребро e E1 инцидентно вершинам u и v V1, то ребро

e E, также инцидентно вершинам u,v V.

Маршруты, цепи, циклы

Определение. Конечная последовательность ребер e1, e2,…, en графа G=(V,E) (не обязательно различных) называется маршрутом длины n, если существует последовательность v0,v1,…,vn вершин (не обязательно различных) таких, что ei инцидентно

(vi−1, vi ),i =1, n. . Маршрут замкнут, если v0=vn (циклический мар-

шрут).

Определение. Маршрут называется цепью, если все его ребра различны и простой цепью, если все его вершины различны (в этом случае и все ребра различны)

Определение. Замкнутая цепь называется циклом и простым циклом, если никакие вершины в ней не повторяются.

Связность

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

Теорема. Граф G=(V,E) связен тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества V1 и V2 так, что обе граничные точки каждого ребра находятся в одном и том же подмножестве.

Доказательство. Пусть G несвязен. Выберем произвольную вершину v1 и пусть множество V1 состоит из вершины v1 вместе со всеми вершинами, которые могут быть соединены с v1 цепью. Т.к. G несвязен, то V1≠V. Поэтому дополнение V2=V-V1 не пусто. По построению множества V1 ни одно ребро не соединяет вершину из V1 ни с одной вершиной из V2 , т.е. получаем разбиение из формулировки.

28

Обратно, если такое разбиение существует, то произвольно выбираем вершины v1 V1 и v2 V2. Цепь, соединяющая v1 и v2, обязательно должно содержать, по крайней мере, одно ребро, имеющее граничные точки в обоих множествах V1 и V2. А т.к. такого ребра нет, то граф G несвязен.

Если в произвольном графе G вершина vi связана с вершиной vj, а vj связана с vl, то vi связана с vl. Отношение связности является отношением эквивалентности (рефлексивно, симметрично, транзитивно). Следовательно, существует такое разложение множества вершин

V = i Vi

на попарно непересекающиеся подмножества, что все вершины в каждом Vi связаны, а вершины из различных Vi не связаны. Т.о. имеем

G == i G(Vi )

разложение графа на непересекающиеся связные подграфы G(Vi), которые называются компонентами связности графа G.

Деревья и леса

Граф называется деревом, если он связен и не имеет циклов. Граф, не имеющий циклов и состоящий из k компонентов, называется лесом из k деревьев.

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

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

Если все вершины графа G принадлежат дереву T, то говорят, что дерево покрывает граф G (является его остовом или каркасом).

Теорема. Каждое дерево с n вершинами имеет в точности n-1

29

ребро.

Доказательство. Удаление одного произвольного ребра разбивает дерево на два компонента, т.е. превращает его в лес из двух деревьев. Удаление второго ребра превращает дерево в лес из 3-х деревьев, и т.д. Удаление n-1 ребра превращает дерево в лес из n деревьев, каждое из которых является изолированной вершиной.

Лекция 8. Ориентированные графы: основные понятия; ориентированные маршруты, пути, контуры; сильная связность; деревья. Метрические характеристики графа.

Основные понятия

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

Определение. Ориентированным графом (или орграфом) называется пара G=<V,E>, где V - непустое множество, а E V2=V×V.

Элементы множества V называются вершинами графа, а элементы множества E - дугами.

Определение. Если дуга e=<u,v> E, то говорят, что вершина u смежна с v, а дуга e отрицательно инцидентна вершине v и положительно инцидентна вершине u.

Определение изоморфизма ориентированных графов идентично определению изоморфизма неориентированных графов.

Определение. Если дуга e=<u,v> отрицательно инцидентна вершине v и положительно инцидентна вершине u, то u и v называются начальной и конечной вершинами дуги e соответственно.

Определение. Если u и v начальная и конечная вершины дуги e=<u,v> и u=v, то e называется петлей (в этом случае u смежна сама с собой).

Определение. Если e1= <u,v> и e2=<u,v>, т.е. u и v являются начальной и конечной вершинами дуг e1 и e2, то e1 и e2 называются строго параллельными.

Определение. Если e1= <u,v>, а e2=<v,u>, т.е. вершина u является начальной вершиной дуги e1 и конечной вершиной дуги e2, а v

30

-наоборот, то такие дуги называются не строго параллельными. Определение. Дуга e1 смежна с дугой e2, если конечная вершина

e1 совпадает с начальной вершиной e2.

Определение. Число дуг, положительно инцидентных вершине v, называется положительной степенью вершины v и обозначается через δ+(v), а отрицательно инцидентных вершине v называется отрицательной степенью вершины v и обозначается через δ--(v).

Учитывая, что каждая дуга положительно инцидентна одной вершине и отрицательно инцидентна также одной вершине, получаем (в случае петли одной и той же)

∑δ+ (v) = ∑δ− (v) = E ,

v V v V

где E - число дуг графа.

Если δ (v)= δ + (v)+ δ − (v) - степень вершины, то для орграфа также справедлива

Теорема. В орграфе число вершин нечетной степени четно. Определение. Вершина v называется изолированной, если

δ(v)=0.

Определение. Орграф называется пустым, если все его вершины являются изолированными.

Определение. Рассмотрим граф G=<V,E>. Граф G1=<V1,E1> называется подграфом G тогда и только тогда, когда

1.V1 V, E1 E.

2. Если дуга e E1 положительно инцидентна вершине v V1 и отрицательно инцидентна вершине u V1, то и дуга e E также положительно инцидентна вершине v V и отрицательно инцидентна вершине u V.

Ориентированные маршруты, пути, контуры

Определение. Ориентированным маршрутом (ормаршрутом) длины n называется последовательность (не обязательно различная) дуг e1,…, en таких, что для соответствующей последовательности n+1 вершин v0,v1,…,vn выполняется условие

ei =< vi−1, vi >, i =1, n , т.е. вершины vi-1 и vi являются соответст-

венно начальной и конечной вершинами дуги ei. Ормаршрут замкнут, если v0=vn (циклический ормаршрут).

Определение. Ормаршрут, в котором нет повторяющихся дуг, называется путем и простым путем, если все его вершины различ-

31

ны.

Определение. Замкнутый путь называется контуром. Замкнутый простой путь называется простым контуром.

Сильная связность

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

Определение. Орграф называется сильно k - связным, если для каждой пары различных вершин u и v существует по крайней мере k путей из u в v, и из v в u, которые не имеют общих вершин (а следовательно и дуг) за исключением конечно u и v.

Деревья

Определение. Орграф является ориентированным деревом, растущим из корня v0, если

1)он образует дерево в неориентированном смысле;

2)единственная цепь между v0 и любой другой вершиной v является путем из v0 в v.

Метрические характеристики графа

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

1)d(u,v)≥0,

2)d(u,v)=0 тогда и только тогда, когда u=v,

3)d(u,v)=d(v,u),

4)d(u,v)+d(v,w) ≥ d(u,w).

Определение. Эксцентриситетом фиксированной вершины и

называется величина l(u) = max d (u,v) .

v V

Определение. Диаметром графа G=(V,E) называется величина

d (G) = max l(u) .

u V

Определение. Вершина v называется периферийной, если l(v)=d(G).

Определение. Радиусом графа G=(V,E) называется величина

r(G) = min l(u) .

u V

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

32

l(v)=r(G). Множество всех центральных вершин графа называется его центром.

Лекция 9. Матричное представление графов: матрица инциденций, матрица смежности вершин. Список смежности.

Матрица инциденций

Пусть G=(V,E) - граф, имеющий n вершин и m ребер: V={v1,…,vn}, E={e1,…, e m}. Графу G можно поставить в соответствие матрицу инциденций A размером n×m, строки и столбцы которой соответствуют вершинам и ребрам графа соответственно. При этом

Т.к. каждое ребро инцидентно двум вершинам, то в каждом столбце матрицы инциденций ровно по две единицы. Исключение составляет петля. Каждый столбец, соответствующий петле содержит одну двойку.

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

33

где Ai - матрица инциденций, соответствующая компоненту i графа.

Теорема 9.1. Ранг матрицы инциденций p - компонентного графа с n вершинами равен (n-p) при условии, что арифметические операции производятся по модулю 2.

Доказательство. Операции сложения строк и перестановки столбцов не влияют на ранг матрицы. Рассмотрим подматрицу Ai. Переставляя столбцы, получим в левом верхнем углу на главной диагонали единицу. Прибавляя эту строку (по mod 2) к любой строке, которая имеет ненулевой элемент в первом столбце, получим, что все элементы первого столбца, исключая первый, равны нулю. Вторая строка должна иметь ненулевой элемент, который перестановкой столбцов помещаем на место (2,2) и с помощью сложения все остальные элементы 2-го столбца обнуляем и т.д. Прибавляя к последней строке все остальные, обнуляем ее (в каждом столбце ровно 2 единицы).

Получаем матрицу с единицами на диагонали, за исключением последнего элемента. Ее ранг равен ni-1. Поэтому

p

rangA = ∑(ni −1) = n − p .

i =1

Замечание. Если G=<V,E> - орграф, то его матрица инциденций определяется следующим образом:

0, если дуга ej не инцидентна вершине vi ;

1, если дуга ej положительно инцидентна вершине vi ; aij = −1, если дуга ej отрицательно инцидентна вершине vi ;

2, если дуга ej - петля в вершине vi .

Матрица смежности вершин

Определение. Матрицей смежности вершин (или просто матрицей смежности) называется матрица B размерности V × V , эле-

34

мент bij которой равен числу ребер, инцидентных одновременно вершинам vi и vj (в случае орграфа направленных от вершины vi к вершине vj).

Теорема 9.2. Матрица Bn дает число ориентированных маршрутов длины n между любыми двумя вершинами ориентированного графа.

Доказательство. Рассмотрим граф G=<V,E>. Пусть V = m. Если bik - число дуг, соединяющих вершину vi с vk, а bkj - число дуг, соединяющих vk с vj, то bik есть число различных ориентированных маршрутов длины 2, соединяющих vi с vj и проходящих через vk. Тогда

m

∑bik bkj = bij(2) k=1

есть число всех ориентированных маршрутов длины 2 между vi и

vj. Пусть теорема верна для Bn−1 . Покажем, что она верна для

Bn = Bn−1 B .

Если bij(n-1) - число всех ормаршрутов длины n-1, соединяющих vi с vk, а bkj - число дуг, соединяющих vk с vj, то bij(n-1) bkj - число всех ормаршрутов от vi к vj, проходящих через vk. Тогда

m

∑bik(n−1)bkj =bij(n) k =1

число всех ормаршрутов длины n от vi к vj.

Замечание 1. Если при некотором N, Bn =0 для всех n≥ N, то в

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

Замечание 2. Теорема верна и для неориентированных графов.

Список смежности

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

Более экономичным является хранение списка смежности. Определение. Списком смежности вершины v V называется

множество u(v) ={w : (v; w) E} (для орграфов v; w E ).

35

Пример 9.2. Граф и его список смежности.

36

Лекция 10. Построение покрывающих деревьев. Алгоритм Краскала.

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

Задача. В небольшой деревушке некоторые из жителей имеют каждодневные встречи друг с другом. Может ли в этой деревне распространиться какой-либо слух?

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

Построение покрывающих деревьев

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

Рассмотрим алгоритм построения покрывающего дерева, предложенный Дж. Краскалом в 1957 г.

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

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

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

Впроцессе работы алгоритма ребра, включенные в дерево, со-

37

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

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

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

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

Алгоритм Краскала построения покрывающего дерева. Начальная установка. Все ребра исходного графа являются неок-

рашенными и ни один из букетов не сформирован.

Шаг 1. Выбрать любое ребро, не являющееся петлей. Окрасить это ребро в синий цвет и сформировать букет, включив в него концевые вершины выбранного ребра.

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

После указанного выбора возможны четыре различных случая:

А. Обе концевые вершины выбранного ребра принадлежат одному и тому же букету. В этом случае ребро окрашивается в оранжевый цвет и производится возврат к началу шага 2.

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

38