Элементы теории графов

1.

Элементы теории графов
Граф – это множество точек, определенным образом соединенных между собой
линиями, необязательно прямыми.
Точки называются вершинами, а линии ребрами (дугами).
Граф G с множеством вершин V и множеством ребер E обозначается через <V; Z>.
Графом называется алгебраическая система G=<V;Z>, где V – элементы
носителя (вершины графа), а Z-двухместный предикатный символ Z ⊆ V2
(множество связей между вершинами).
рассматриваем только графы, содержащие конечное число вершин и
конечное число связей.

2.

Элементы теории графов
V – множество вершин
V {1,2,3,4,5,6,7};
Z {{1,2},{1,3},{1,4},{1,7},{2,5},{2,6},
{2,7},{3,4},{3,6},{4,5},{4,6},{5,7}};
Z– множество двухэлементных подмножеств {v,w} множества V ,
каждое из которых определяет ребро, соединяющее вершины v∈ V и
w∈ V.

3.

Псевдограф. Мультиграф.
Граф называется ПРОСТЫМ (линейным), если
любые две его вершины соединены не более
чем одним ребром и каждое ребро соединяет
различные вершины.
Граф, в которых те или иные пары
вершин соединены не одним ребром, а
несколькими (кратные, параллельные) или
существуют ребра, соединяющие какую-либо
вершину саму с собой («петля») называют
ПСЕВДОГРАФОМ.
Псевдограф без петель называется МУЛЬТИГРАФОМ
Вершина называется изолированной, если у нее нет петель
и из нее не выходит ни одного ребра.

4.

Подграф.
Удалим из графа вершину 1.
удалятся и четыре ребра:
{1,2}, {1,3}, {1,4}, {1,7}
Оставшиеся вершины и ребра
образуют ПОДГРАФ G′ графа G
V′ ⊆ V и Z′ ⊆ Z, где V и Z – множества вершин и ребер графа G;
V′ и Z′– множества вершин и ребер подграфа G′
Любой граф является подграфом самого себя.
Граф, не содержащий вершин, называется ПУСТЫМ графом.
Пустой граф является подграфом любого графа.
Непустой подграф называется СОБСТВЕННЫМ, если он не
совпадает с исходным графом G.
Граф G и пустой граф называются НЕСОБСТВЕННЫМИ
подграфами.

5.

Надграф.
Пусть дан граф G на n вершинах.
Добавим к ним одну вершину и соединим ее каким-либо
образом с вершинами графа G.
Новый граф с n + 1 вершинами
называется НАДГРАФОМ графа G.
По заданному графу подграф находится однозначно, то есть, удалив из
графа одну или несколько вершин, мы получим единственный подграф.
Обратная операция неоднозначна.

6.

Надграф.
Пример:
Пусть в простом графе имеется четыре вершины.
Определить количество надграфов, при добавлении к графу одной
вершины.
число надграфов N1 2n (при добавлении 1й вершины);
число надграфов N 2 2n 2n 1 22n 1
(при добавлении 2 хвершин);
N3 2n2n 12n 2 23n 3 , и т. д.

7.

Частичный граф.
Если в графе G все вершины оставить на своих местах
и удалить одно или несколько ребер, то получится
ЧАСТИЧНЫЙ граф.
Формально граф G′ называется частичным
графом графа G, если V′ = V и Z′ ⊆ Z
! всякий граф является частичным по отношению к самому себе
из графа удалим
{1,2}, {1,3}, {1,4}, {1,7}, {2,7}, {5,7}.
останется частичный граф
V′ = {1, 2, 3, 4, 5, 6, 7} = V;
Z′ = {{2,5}, {2,6}, {3,4}, {3,6}, {4.5}, {4,6}}⊂ Z.
Количество частичных графов = 2k, где k – число ребер заданного графа.
Граф, в котором нет ни одного ребра, называется НУЛЬ-ГРАФОМ

8.

Смежность. Инцидентность.
Две вершины v∈V и w∈V, где V – множество
вершин графа G, называются СМЕЖНЫМИ,
если они соединены ребром.
Два ребра называются СМЕЖНЫМИ, если они
имеют общую вершину
Если вершина является концом ребра, то вершина
и ребро называются ИНЦИДЕНТНЫМИ
Число ρ(v) ребер, инцидентных вершине v, называется
СТЕПЕНЬЮ этой вершины v.
Степень изолированной вершины равна нулю.
Степень изолированной вершины, содержащей одну
петлю, равна 2.
Вершина, степень которой равна 1, называется ВИСЯЧЕЙ.

9.

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

10.

Однородный граф.
Граф называется ОДНОРОДНЫМ,
если степени всех его вершин
равны между собой:
ρ(1) = ρ(2) = … = ρ(n),
где n – число вершин графа;
ρ(i) – степень i-й вершины графа ( i = 1, 2, … , n).
Примеры однородных графов
Сумма степеней всех вершин
однородного графа
Число ребер однородного графа
n, где
– степень вершины,
n – число вершин
n
K
2

11.

Полный граф.
Граф без петель называется
ПОЛНЫМ, если каждая пара его
вершин соединена одним
ребром.
Примеры полных графов
Степень любой вершины n 1, где
полного графа
– степень вершины,
n – число вершин
n n 1
K
2
n n 1
n!
2
K Cn
2! n 2 !
2
Число K ребер полного графа
каждой паре вершин
соответствует одно ребро

12.

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

13.

Двудольные графы.
Пусть множество V вершин графа G состоит из двух
непустых множеств V1 и V2 так, что
V V1 V2 и V1 V2
Если каждое ребро графа G соединяет некоторую вершину
множества V1 c какой-либо вершиной множества V2, то
такой граф называется ДВУДОЛЬНЫМ.
Пример
V = {1,2,3,4,5,6,7},
V1 ={1,2,3},
V2 = {4,5,6,7}.

14.

Двудольные графы.
Двудольный граф называется полным, если каждая вершина
множества V1 соединена с каждой вершиной множества V2.
Граф, в котором вершины, принадлежащие разным
подмножествам, попарно смежны является
ПОЛНЫМ ДВУДОЛЬНЫМ.
Полный двудольный граф имеет k ребер, где k = |V1| ·|V2|.
Степень любой вершины множества V1 полного двудольного
графа равна |V2|.
Степень каждой вершины множества V2 равна |V1|.

15.

Двудольные графы.
Дополнение полного двудольного графа есть несвязный граф,
состоящий из двух компонент – полного графа G1 и полного
графа G2.
Пусть n1 = |V1|; n2 = |V2|.
Тогда величины K1 и K2, определяющие число ребер
компонент G1 и G2, равны:
n1 n1 1
2
K1 Cn
1
2
n2 n2 1
2
K 2 Cn
2
2
Общее число K ребер дополнения полного двудольного графа
равно:
n12 n22 n1 n2
K K1 K 2
2

16.

Двудольные графы.
полный двудольный граф |V1| = |V2| = 3
K3,3
Пример
K1,1
K1,2
K3,2
K4,3
K1,5
По аналогии с двудольными можно говорить о трехдольных,
четырехдольных и, вообще, n-дольных графах.
Пример
В трехдольном графе множество вершин разбивается на три
подмножества, в каждом из которых нет смежных вершин.
Соединяться ребрами могут лишь те вершины, которые
принадлежат различным подмножествам (долям).

17.

Изоморфизм.
(isos (гр.) – равный, одинаковый, подобный, morphe (гр.)
– вид, форма) в общем случае – соответствие
(отношение) между объектами, выражающее
тождество их структуры.
Если вершинам vi и vj, соединенным ребром в графе G1,
соответствуют те же вершины, соединенные ребром в графе G2,
и если вершинам vi и vj , не соединенным ребром в графе G1,
соответствуют те же вершины, не соединенные ребром в
графе G2 ( i, j = 1, 2, …, n, где n – число вершин), то такие графы
называются изоморфными.
Пример
G1 и G2
изоморфны

18.

Изоморфизм.
Пример
Даны G1 и G2, которые имеют одинаковое число вершин и одинаковое
число вершин со степенью 0, 1, 2 и т. д. Следовательно графы могут быть
изоморфными.
Для того, чтобы установить изоморфизм G1 и G2, необходимо пронумеровать в них
вершины и проверить, выполняются ли условия. Если да, то графы изоморфны, если
нет, то в одном из графов необходимо сменить нумерацию вершин и снова
проверить.
Пример
G1
Максимальное количество проверок n!, где
n – число вершин графа.
G2
Nρ=1 (G1)= Nρ=1 (G2), Nρ=2 (G1)= Nρ=2 (G2),
Nρ=3 (G1)= Nρ=3 (G2).
8!
Вывод: графы не изоморфны.

19.

Ориентированные графы.
Пусть V – множество вершин графа. Его квадратом является
множество Z упорядоченных пар (v,w), где v,w ∈ V.
Каждой паре (v,w) соответствует ориентированное ребро в
виде линии, оканчивающейся стрелкой.
Ориентированные ребра принято называть дугами.
Началом дуги является вершина v∈V, концом – вершина w∈V.
Граф, содержащий только дуги, называется
ОРИЕНТИРОВАННЫМ ГРАФОМ или ОРГРАФОМ.
Пример
V = {1, 2, 3, 4, 5};
Z = {(1,2), (1,3), (2,3), (2,4), (3,4),
(4,2), (4,4), (4,5) }.

20.

Ориентированные графы.
Если заменить в орграфе все дуги ребрами, то получится
граф, который называется основанием орграфа.
Два орграфа изоморфны, если изоморфны их ОСНОВАНИЯ и
совпадают НАПРАВЛЕНИЯ всех соответствующих дуг.
Пример
Представленные графы не являются изоморфными, поскольку дуги,
соединяющие вершины 2 и 3, направлены в противоположные стороны

21.

Операции над графами.
Пример
a3
a1
G1 a1, a 2, a3 ; a1, a 2 a 2, a3
a2
G2 a1, a 2, a 4 ; a1, a 2 , a 4, a1
a1
a2
1. Объединение
G1 G2 V1 V2 ; Z1 Z2
a1
a4
a2
a3
a4
2. Пересечение
G1 G2 V1 V2 ; Z1 Z2 , если V1 V2
a1
a2
3. Кольцевая сумма
G1 G2 V1 V2 ; Z1 Z 2 ,
Z1 Z 2 Z1 \ Z 2 Z 2 \ Z1
a1
a4
a2
a3

22.

Операции над графами.
Пример
a3
a1
G1 a1, a 2, a3 ; a1, a 2 a 2, a3
a2
a1
G2 a1, a 2, a 4, a5 ; a1, a 4
a1, a 2 , a 4, a5 , a5, a1
a5
a4
4. Соединение
G1 G2 V1 V2 ; Z1 Z 2 a, b | a V1 , b V2 , a b
a1
a3
a5
a2
a4
a2

23.

Операции над графами.
Пример
c
a
G1 a, b, c ; b, c a, a , a, b
b
1
G2 1, 2,3 ; 1, 2 , 3, 2
2
3
5. Произведение
G1 G2 V1 V2 ; Z ,
a , b , a , b Z
1
1
2
2
a1 a2 и b1 , b2 Z 2
или
b b и a , a Z
1
1 2 1 2
(a,1)
(a,2)
(a,3)
(b,1)
(b,2)
(b,3)
(c,1)
(c,2)
(c,3)

24.

Операции над графами.
Пример
c
a
G1 a, b, c ; b, c a, a , a, b
b
1
G2 1, 2,3 ; 1, 2 , 3, 2
2
3
6. Композиция
G1 G2 V1 V2 ; Z ,
a , b , a , b Z
1
1
2
2
a1 , a2 Z1
или
a a и b , b Z
1 2 2
2
1
(a,1)
(a,3)
(a,2)
(b,1)
(b,3)
(b,2)
(c,1)
(c,2)
(c,3)

25.

Операции над графами.
Пример
G1 a, b, c ; b, c a, a , a, b
b
1
G2 1, 2,3 ; 1, 2 , 3, 2
2
a , b , a , b Z
1
1
2
3
G2 G1
6. Композиция
G1 G2 V1 V2 ; Z ,
c
a
(1,a)
(1,b)
(1,c)
2
a1 , a2 Z1
или
a a и b , b Z
1 2 2
2
1
(2,a)
(2,c)
(2,b)
(3,a)
(3,b)
(3,c)

26.

Матрица смежности.
С помощью матрицы смежности (аналог матрицы бинарного
отношения) может быть задана информация о структуре
графа .
G V ; Z , где V v1 , v2 ,..., vk
Матрица смежности AG Aij
k k
, где Aij количество vi , v j
Строкам и колонкам матрицы ставятся в соответствие
вершины, а на пересечениях строк и колонок записываются
числа, показывающие, сколько ребер соединяют
соответствующие вершины графа.

27.

Матрица смежности.
Пример
0
0
AG 0
0
0
1 0 0 0
0 1 0 0
0 0 1 0
0 1 1 0
0 0 0 0
Пример
0
3
1
AG
0
0
2
3
0
1
1
0
0
1
1
0
0
1
0
0
1
0
2
2
1
0
0
1
2
1
1
2
0
0
1
1
1

28.

Матрица смежности.
0
3
1
AG
0
0
2
1.
Тип графа :
простой граф ( 0 на гл. диагонали, остальные 0 и 1);
мультиграф ( 0 на гл. диагонали и остальные могут быть больше 1);
псевдограф (на гл. диагонали числа не равны 0 );
неограф (матрица смежности симметрична AG AG T ) .
3
0
1
1
0
0
1
1
0
0
1
0
0
1
0
2
2
1
0
0
1
2
1
1
2. Степень вершины (сложить все числа в соответствующей строке (или
колонке) и добавить к результату число, находящееся на пересечении
данной строки с главной диагональю).
3. Число всех ребер графа ( к сумме всех чисел матрицы (вместе с
диагональными), добавить сумму всех диагональных чисел и результат
разделить на два).
2
0
0
1
1
1

29.

Матрица смежности.
0
3
1
AG
0
0
2
3
0
1
1
0
0
1
1
0
0
1
0
0
1
0
2
2
1
0
0
1
2
1
1
2
0
0
1
1
1
4. Матрица смежности подграфа( в исходной матрице удалить i-ю строку и i-
й столбец).
0
1
AG 1
0
0
1 1 0 0
0 0 1 0
0 2 2 1
1 2 1 1
0 1 1 1
5. (теорема) Графы изоморфны, тогда и только тогда, когда их матрицы
смежности получаются друг из друга одновременными перестановками строк
и столбцов (т.е. одновременно с перестановкой i и j строк переставляются i и j
столбцы).

30.

Матрица инцидентности.
G V ; Z , где V v1 , v2 ,..., vk и Z z1 , z2 ,..., zm
Матрица инцидентности I G I ij
I ij
k m
, где
1, если z j исходит из вершины vi ;
1, если z j заходит в вершину vi ;
0, в противном случае.
Пример
1 1 0 0 0 0
I G 1 1 1 1 1 1
0 0 0 1 1 1
Мультиграфы изоморфны тогда и только тогда, когда их
матрицы инцидентности получаются друг из друга
некоторыми перестановками строк и столбцов.

31.

Маршруты, цепи, циклы.
Маршрутом длины n называется непустая последовательность n ребер.
Пример
Цепь – маршрут называется, если в нем нет повторяющихся ребер.
Число ребер, входящих в цепь – длина цепи или расстояние между вершинами.
Простая цепь – в ней нет повторяющихся вершин (лишь первая и последняя
вершины могут совпадать).

32.

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

33.

Маршруты, цепи, циклы.
Неограф без циклов называется ациклическим.
Минимальная из длин циклов неографа называется обхватом.
Пример
Обхват = 3
Маршрут в орграфе называется путем, если все его дуги различны.
Замкнутый маршрут в орграфе называется контуром.
Если в орграфе нет контуров, то он называется бесконтурным.
Ориентированный граф
Дуга
Путь
Контур
Неориентированный граф
Ребро
Цепь
Цикл
Вершина b называется достижимой из вершины a, если существует путь(цепь).

34.

Связные графы.
Связный неограф – две любые несовпадающие вершины соединены маршрутом.
Связный орграф – если соответствующий ему неограф является связным.
Сильно связный граф – для любых a и b вершин существует (a,b) и (b,a) маршрут.
Связный неограф является сильно связным.
Пример
Максимальный по включению
(сильно) связный подграф графа
называется его (сильной) связной
компонентой или
(сильной)компонентой связности.
Связный орграф
Не сильно связный
Любой граф представляется в виде объединения
непересекающихся связных (сильных) компонент.
Разложение графа на связные (сильные) компоненты
определяется однозначно.
Связный неограф
Несвязный граф

35.

Количество и существование маршрутов и циклов.
Вграфе G V ; Z , представленным матрицей смежности AG
i, j й элемент матрицы AGk G AG AG ... AG
k раз
естьчисло маршрутов длины k из vi вершины в v j .
Вграфе G V ; Z мощности n, представленным матрицей
смежности AG тогда и только тогда существует маршрут
из vi вершины в v j vi v j , когда i, j й элемент матрицы
AG AG2 ... AGn 1 не равен 0.
Вграфе G V ; Z мощности n, представленным матрицей
смежности AG тогда и только тогда существует цикл,
содержащий вершину в vi , когда i, i й элемент матрицы
AG AG2 ... AGn не равен 0.

36.

Количество и существование маршрутов и циклов.
Пример
Определить существование маршрута (1,3)
1. По матрице смежности видно, что маршрута длины 1 нет;
2. Элемент (1,3)=0,
маршрута длины 2 нет;
3. Элемент (1,3)=1, есть
1 маршрут длины 3.

37.

Вспомогательная матрица
B G bi , j E AG +A +...+A .
n 1
G
2
G
Матрица связности (неограф) или матрица достижимости (орграф)
1, если bi , j 0;
C G ci , j , где ci , j
0, если bi , j 0.
В графе тогда и только тогда существует
v , v маршрут i j , когда c 1.
i
j
ij
В матрице C содержится вся информация о существовании связей
между различными элементами графа посредством маршрутов.
Если G – связный неограф, то сij=1.

38.

Матрица контрдостижимости
QG qi , j , где
qi , j
1, вершина vi достижима из v j или i j ;
0, в противном случае.
QG C
T
G
Матрица сильных компонент
SG CG QG , где si , j ci , j qi , j
поэлементное произведение матриц .

39.

Элемент si , j 1, когда i j или
вершины vi и v j взаимно достижимы.
Сильная компонента, содержащая вершину vi ,
состоит из элементов v j , для которых sij 1.
Пример
Сильная компонента, содержащая
вершину 2, состоит из {1,2,3}

40. Числа графа

1. Цикломатическое число
2. Число внутренней устойчивости
3. Хроматическое число
4. Число внешней устойчивости
Цикломатическое число ʋ(G)
Пусть G X , Z , X n, Z m, то
G m n p,
где p – количество компонент связности.
Теорема. Цикломатическое число графа равно
наибольшему количеству независимых циклов.

41.

Цикломатическое число ʋ(G)
x2
Пример
n 7,
x1
x3
x6
x4
m 8,
p 2,
G 8 7 2 3.
x5
x7
1.
Связный граф G не имеет циклов тогда и только тогда, когда
v(G)=0. Такой граф есть дерево.
2.
Связный граф G имеет единственный цикл тогда и только
тогда, когда v(G)=1.
Цикломатическое число связного графа можно определить
как число ребер, которое нужно удалить, чтобы граф стал деревом.

42. Число внутренней устойчивости α(G)

Внутренне устойчивым подмножеством графа называется
подмножество вершин, не смежных между собой.
Пример
x1
x2
S2 x2 , x4 ,
S3 x1 , x5 ,
x3
x5
S1 x1 , x4 ,
S4 x2 , x5 ,
x4
S5 x3 .

43. Число внутренней устойчивости α(G)

Числом внутренней устойчивости графа
называется максимальная мощность внутренне
устойчивых подмножеств G max S .
i
i
Пример
x1
x2
S1 x1 , x4 , S2 x2 , x4 ,
S3 x1 , x5 , S4 x2 , x5 ,
x3
S5 x3 ,
x5
x4
G max Si 2.
i

44. Алгоритм вычисления числа внутренней устойчивости графа

Пусть задан G X , Z , X n, Z m.
1. По матрице инцидентности I G ik ,l n m
m
n
П G ik ,l xk x1 x2 x2 x3 x4 ... ;
l 1 k 1
F1
F2
2. Находятся все Si X Fi ;
3. Определяется G max Si .
i

45. Алгоритм вычисления числа внутренней устойчивости графа

Пример
4
1
0
I G
0
1
1 0 0
1 1 0
0 1 1
0 0 1
4
1. П G ik ,l xk x1 x4 x1 x2 x2 x3 x3 x4
l 1 k 1
упрощение для получения минимальной дизъюнктивной нормальной формы
x1 x1 x1 x4 x1 x2 x2 x4 x3 x3 x2 x3 x3 x4 x2 x4 x1 x2 x4 x3 x2 x4 x1 x3 x2 x4 ;
2. S1 X x1 , x3 x2 , x4 , S2 X x2 , x4 x1 , x3 ;
3. G max Si 2.
i

46. Хроматическое число графа γ(G)

Хроматическим числом графа называется минимальное
количество цветов, требующихся для раскраски вершин
графа, чтобы смежные вершины имели разные цвета.
Пример
x1
x2
G 3
x3
x5
x4

47. Алгоритм вычисления хроматического числа графа

Пусть задан G X , Z , X n, Z m,
S1 , S2 ,..., Sk внутренне устойчивые подмножества графа.
1. Формируем матрицу инцидентности внутренне
устойчивых подмножеств I G ik ,l n k
n
k
2. П G ik ,l Sl S1S 2 S 2 S3 S 4 ... ;
k 1 l 1
3. G min Di 2.
i
D1
D2

48. Алгоритм вычисления хроматического числа графа

Пример
S1 x2 , x4 ,
S2 x1 , x3
S1 S 2
0
1
I G
0
1
4
1 x1
0 x2
1 x3
0 x4
2
П G ik ,l Sl S 2 S1S 2 S1 S1S 2
k 1 l 1
G min Di 2.
i

49. Число внешней устойчивости β(G)

Внешне устойчивым подмножеством графа называется
подмножество вершин, не смежных между собой, но
смежных со всеми оставшимися вершинами графа.
Пример
x1
x2
M 3 x1 , x5 , M 4 x2 , x5 ,
x3
x5
M1 x1 , x4 , M 2 x2 , x4 ,
M 5 x3 .
x4

50.

Число внешней устойчивости β(G)
Числом внешней устойчивости графа называется
минимальная мощность внешне устойчивых подмножеств
G min M i .
i
Пример
x1
x2
M1 x1 , x4 ,
M 2 x2 , x4 ,
M 3 x1 , x5 ,
x3
M 4 x2 , x5 ,
x5
x4
M 5 x3 .
G min M i 1.
i

51.

Пример
Диаграмма направленности антенны передатчика
телевизионной станции имеет вид:
Необходимо охватить минимальным
количеством ТС местность и
определить места их установки.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
x2
x1
x3
x4
x5
x6
x7
x8
x9
x16
x10
x15
x14
x13
M1 x2 , x8 , x9 , x15 ,
x12
x11
M 2 x3 , x5 , x12 , x14 .

52.

Расстояния в графах.
Длина кратчайшего (аi , a j ) маршрута называется
расстоянием между вершинами аi и a j .
V a1 , a2 ,..., an , то R rij матрица расстояний, где rij ai , a j
Эксцентриситет вершины e a
max a, b | b V
Максимальный среди всех эксцентриситетов называется
диаметром графа d G max e a | a V
Вершина a называется периферийной, если e a d G .
Минимальный среди всех эксцентриситетов называется
радиусом графа r G min e a | a V
Вершина a называется центральной, если e a r G .

53.

Расстояния в графах.
Пример
Диаметр графа равен максимуму из чисел в последнем
столбце, а радиус - минимуму из них
Диаметр графа равен 3, радиус 2,
а центрами являются вершины v3, v4 и v6.

54.

Взвешенные графы.
Графы, вершины которых пронумерованы, еще называют
помеченными графами.
Графы, вершинам и (или) ребрам которых приписаны
некоторые веса, называют взвешенными графами.
Графы потоков сигналов или сигнальные графы - взвешенные
ориентированные графы для моделирования физических
систем.
Пример
матрица весов
0 10 12 30
10
0
10
10
12 0 10 20
WG
10 10 0
30 0
10 20 0

55.

Поиск маршрута.
Метод Шимбелла (позволяет находить кратчайшие или
максимальные пути между вершинами, состоящие из заданного
количества дуг).
a b b a a b b a
a 0 0 a a 0 0
Операция умножения двух величин a и b
при возведении матрицы в степень
соответствует их алгебраической сумме,
wij min(max) wi1 w1 j , wi 2 w2 j , wi 3 w3 j ,..., win wnj
(нули игнорируются)

56.

Поиск маршрута (Метод Шимбелла).
0
2
W
0
0
Пример
0
2
2
W
0
0
1 3 2 0
0 2 0 2
0 0 0 0
2 1 0 0
1 3 2
0 2 0
0 0 0
2 1 0
1 3 2 3
0 2 0 0
0
0 0 0
2 1 0 4
1
1
1
1
1
1
1
1
w AA2 min w AA
w AA
, w AB
wBA
, w AC
wCA
, wAD
wDA
4 3 0
3 5 4
0 0 0
0 4 0
min 0 0 , 1 2 , 3 0 , 2 0 min 0,3, 0, 0 3.
1
1
1
1
1
1
1
1
w AB2 min w AA
w AB
, w AB
wBB
, w AC
wCB
, w AD
wDB
min 0 1 , 1 0 , 3 0 , 2 2 min 0, 0, 0, 4 4.
Мин. маршрут А-А
из 2 дуг имеет вес 3,
А-B – 4, ит.д.

57.

Поиск маршрута (Метод Шимбелла ).
Пример
0
2
W
0
0
3
0
3
W
0
4
4 3 0 0
3 5 4 2
0 0 0 0
0 4 0 0
1 3 2
0 2 0
0 0 0
2 1 0
1 3 2 6
0 2 0 4
0 0 0 0
2 1 0 0
Мин. маршрут А-А из 3 дуг имеет вес 6,
А-B – 4, ит.д.
4 6 5
6 4 0
0 0 0
5 7 6

58.

Поиск маршрута.
Алгоритм Дейкстры для поиска кратчайшего пути (веса дуг должны быть
положительными)
1. Нахождение длины пути от вершины s к вершине t
Шаг 1. Присвоение вершинам начальных меток.
начальной вершине s присвоить d s 0* постоянная метка ;
вершинам xi G , xi s присвоить временную метку d xi ;
x" обозначение текущей вершины x '' s.
Шаг 2. Изменение меток.
Для каждой вершины xi с временной меткой, непосредственно
следующей за вершиной x '' , меняем ее метку в соответствии
со следующим правилом
d xi min d xi , d x '' w x" , xi .

59.

Алгоритм Дейкстры.
Шаг 3. Превращение метки из временной в постоянную :
из всех вершин с временными метками выбрать xi с
наименьшим значением метки
d xi* min d xi / xi G, d xi временная метка ;
x" xi* .
Шаг 4. Проверка на завершение этапа.
Если x" t , то d xi* длина кратчайшего пути от s к t.
В противном случае возврат к шагу 2.

60.

Алгоритм Дейкстры.
2. Построение пути от вершины s к вершине t
Шаг 5. Последовательный поиск дуг кратчайшего пути.
Среди вершин, непосредственно предшествующих вершине x"
находится вершина xi
d x" d xi w xi , x" ;
дуга xi , x" включается в искомый путьи x" xi .
начальной вершине s присвоить d s 0* постоянная метка ;
вершинам xi G , xi s присвоить временную метку d xi ;
x" обозначение текущей вершины x '' s.
Шаг 6. Проверка завершения этапа.
Если x" s, то путь найден.
В противном случае переход на шаг 5.

61.

Цикл Эйлера.
Одним из первых результатов в теории графов
явился критерий существования обхода графа без
повторений, полученный Леонардом Эйлером, при
решении задачи о Кенигсбергских мостах в 1736 г.
Леонард Эйлер
(1707 – 1783)
Бывший
Кенигсберг
(ныне
Калининград)
расположен на реке Прегель. В пределах города река
омывает два острова. С берегов на острова были
перекинуты мосты.
Старые мосты не сохранились, но осталась карта
города, где они изображены.
X1
X3
X2
X4
Кенигсбергцы
предлагали
приезжим следующую задачу:
пройти по всем мостам и
вернуться в начальный пункт,
причём
на
каждом
мосту
следовало побывать только один
раз.

62.

Цикл Эйлера.
Составим неориентированный мультиграф G,
представляющий задачу. Вершины X1, X4
соответствуют берегам реки, X2, X3 – островам, ребра
мультиграфа – мостам.
X1
X2
X3
X4
G
Следовательно, на языке
теории графов задача
формулируется следующим
образом:
Существует ли в мультиграфе
цикл, содержащий все ребра
данного мультиграфа?

63.

Цикл Эйлера.
Цикл, содержащий все ребра мультиграфа,
называется эйлеровым, и мультиграф, в котором
имеется эйлеров цикл, также называется эйлеровым.
Критерий Эйлера: Если в связанном
графе все степени вершин четные, то
граф является эйлеровым.
Степенью вершины ρ(xi) называется количество
инцидентных ей ребер.
X2
Например:
X1
X3
ρ(x1)=2
ρ(x2)=3
ρ(x3)=3

64.

Цикл Эйлера.
Критерий Эйлера для ориентированного графа:
Ориентированный граф является
эйлеровым тогда, и только тогда, когда
он связный, и для каждой его вершины
xi выполняется условие: ρ+(xi) = ρ–(xi).
Степень ρ –(xi) показывает для какого количества
дуг вершина xi является началом.
Степень ρ+(xi) показывает для какого количества
дуг вершина xi является концом.
Пример:
X1
X3
X2
ρ+(x1)=2
ρ– (x1)=0

65.

Алгоритм построения цикла Эйлера.
Пример
1. Строим из ребер графа циклы.
2. Объединяем циклы по
общей вершине.
X2
X1
X4
X3
C1={{X1,X2},{X3,X2},{ X3,X1}}
C2={{X3,X4},{X4,X5},{ X5,X3}}
X5
Аналогичным
образом формируются
циклы эйлера для
ориентированных
графов
C={{X1,X2},{X2,X3},{ X3,X4},{X4,X5},{X5,X3},{ X3,X1}}

66.

Алгоритм Флёри для построения цикла Эйлера.
Вход: эйлеров граф G.
Выход: список ребер графа G в той последовательности, в которой они
образуют эйлеров цикл.
1. Положить текущий граф равным G, а текущую вершину – равной
произвольной вершине v ∈ V(G).
2. Выбрать произвольное, с учетом ограничения ребро Z текущего графа,
инцидентное текущей вершине.
3. Назначить текущей вторую вершину, инцидентную Z.
4. Удалить Z из текущего графа и внести в список.
5. Если в текущем графе еще остались ребра, вернуться на шаг 2.
Ограничение: если степень текущей вершины в текущем графе больше 1,
нельзя выбирать ребро, удаление которого из текущего графа увеличит
число компонент связности в нем.
Пример
v1 → v5 → v2 → v6 → v5 → v4 → v6 → v3 → v2 → v1

67.

Цикл Гамильтона.
В 1859 г. сэр Уильям Гамильтон,
знаменитый ирландский математик,
предложил детскую головоломку, в которой
предлагалось совершить «кругосветное
путешествие» по 20 городам, расположенным
в различных частях земного шара.
Уильям Гамильтон
(1805 – 1865)
Каждый город соединялся дорогами с
тремя соседними так, что дорожная сеть
образовывала 30 ребер додекаэдра, в
вершинах которого находились города.
Задача состояла в отыскании такого пути,
проходящего через все вершины (города)
графа, чтобы посетить каждую вершину
однократно и вернуться в исходную.
Цикл
Гамильтона

68.

Условия существования цикла Гамильтона.
Гамильтонов путь (или гамильтонова цепь) — путь (цепь),
содержащий каждую вершину графа ровно один раз.
Гамильтонов путь, начальная и конечная вершины которого
совпадают, называется гамильтоновым циклом.
Гамильтонов граф — это граф, содержащий гамильтонову цепь или
гамильтонов цикл. Условие Оре (1960):
Если для любой пары несмежных вершин x, y выполнено
неравенство ρ(x) + ρ(y)≥ n
(где n - количество вершин в графе), то граф является
гамильтоновым.
Частный случай условия Оре сформирован в теореме Дирака в 1952г.
Теорема Дирака: Если в простом графе с n вершинами
(n 3) степень любой вершины больше, либо равна n/2, то
граф является гамильтоновым.
Критерия “гамильтоновости” графа, и эффективного алгоритма нахождения
гамильтонова цикла в произвольном графе, НЕТ.

69.

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

70.

Деревья.
1. Всякий граф имеет дерево;
2.
Если дерево содержит n вершин, то количество ребер
m=n-1;
3.
В дереве любые две вершины могут быть связаны
единственной цепью;
4.
Количество деревьев, которые можно построить на n
вершинах nn-2;
5.
Если в дереве соединить пару несмежных вершин, то
получим граф ровно с одним циклом.

71.

Деревья.
Пример
К4
4 дерева
4 дерева 4 дерева 4 дерева
44-2=16

72.

Деревья.
Остовом неографа G(X,Z) называется подграф G’(X’,Z’), X’=X и
G’(X’,Z’) – лес, который на любой компоненте связности
G(X,Z) образует дерево.

73.

Алгоритм поиска остова минимального веса.
Алгоритм Краскала
Вход: связанный взвешенный граф с
неотрицательными весами
Выход: список Т ребер остова минимального веса
1. Положить T ;
2. Выписать все ребра из G в список S по возрастанию веса;
2. Выбрать в S ребро e минимального веса и удалить из S ;
3. Если e не образует цикла с ребрами из T , добавить e в T ;
4. Повторить пока в S не будет n 1 ребер.
Пример
(a, d), (e, f ), (h, i), (a, e), (b, f ), (d, e), (e, g),
(a, b), (f , g), (f , h), (c, i), (f , i), (g, h), (c, f )

74.

Фундаментальные циклы.
Пусть G(X,Z), |X|=n, |Z|=m, G’(X,Z’) – остов графа, |Z’|=n-p.
Хордами графа называются ребра zi∈ Z\Z’.
Фундаментальным называется цикл, состоящий из
произвольной хорды zi графа и простой цепи,
принадлежащей остову графа, соединяющей вершины
хорды.
x1
z3
x4
x2
C1 z1 , z4 , z5 , z3 ;
z2 z
4
C2 z2 , z5 , z3 .
z1
z5
x3

75.

C ci , j
Матрица фундаментальных циклы.
В случае группировки хорд:
C C1 C2 ;
C1 E.
n 8, m 11, p 1
Пример
x2
z8
z5
z6
z1
x6
z11
x5
,
1, z j Ci ;
ci , j
0, z j Ci .
1 ... 0 c1, G 1 ... c1,m
C ... 1 ...
...
...
... ,
0 ... 1 c
...
c
G , G 1
G , m
x1
m n p m
x3
z9 x4
z7
z4
z2
z3
x7
z10
x8
Цикломатическое число G 11 8 1 4
1
0
C
0
0
0
1
0
0
0
0
1
0
01
00
00
10
1
1
1
0
0
1
1
1
0
1
1
0
0
0
0
1
0
0
1
0
1
0
.
1
0

76.

Разрезы графа.
Разрезом графа G(X,Z) по разбиению {X1,X2} (X1∩X2=∅),
называется множество К всех ребер, соединяющих
вершины из X1 с вершинами из X2.
Свойство: В связном графе любой разрез не пуст.
Разрез К неографа G(X,Z) называется простым или
коциклом, если любое K’≠∅, K’⊂K не является разрезом ни
по какому разбиению.
z1
K2
K1
z2
z4
z3
K1 z1 , z2 , z3 ;
K2 z2 , z4 .

77.

Разрезы графа.
Теоремы:
1. В конечном неографе G(X,Z) имеющем р компонент связности
множество ребер К тогда и только тогда является коциклом, когда
граф G(X,Z\К) имеет р+1 компоненту связности.
2. В связном неографе остовное дерево имеет минимум одно общее
ребро с любым из разрезов графа.
Фундаментальным разрезом графа G(X,Z) относительно
ветви zi остова называется множество Ki, содержащее эту
ветвь.
Мощность множества фундаментальных разрезов равно
корангу υ*(G)=n-p.

78.

Матрица фундаментальных разрезов.
В случае группировки хорд:
K K1 K 2 ;
Пример
K1 C2T , K 2 E.
n 8, m 11, p 1
x2
x3
z8
z5
z6
x1
z1
z7
x6
z11
x5
z9 x4
z4
z2
z3
x7
z10
x8
K ki , j
n p m
,
1, z j Ki ;
ki , j
0, z j Ki .
коранг * G 8 1 7
1
1
0
K 0
0
0
1
0 0 0 1 0 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0
1 1 1 0 0 1 0 0 0 0
1 1 0 0 0 0 1 0 0 0 .
0 0 1 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 1

79.

Планарные графы.
Укладкой графа называется такое его геометрическое
изображение, при котором ребра пересекаются только в
вершинах.
Если существует укладка графа на плоскости, граф называется
планарным, а его укладка – плоским графом.
Пример
G1 и G2 изоморфны.
G1 – плоский граф, а G2 - нет

80.

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

81.

Планарные графы.
Грань – максимальная область плоскости, любые две точки
которой можно соединить непрерывной линией, не
пересекающей граф (точки графа не принадлежат никакой
грани).
Граница грани F плоского графа G – подграф G, состоящий в
точности из всех вершин и ребер, «прилегающих» к F.
Пример
Граф содержит 4 грани, грань F4 - внешняя

82.

Планарные графы.
Теорема Эйлера. В плоском графе ребра граней образуют базу независимых циклов.
Для плоского графа справедливо:
n - m + f = 2, m, n, f – количество ребер, вершин и граней соответственно.
Операция разбиения ребра
• Ребро удаляется из графа;
• В граф добавляется новая вершина;
• В граф добавляется 2 новых ребра, инцидентных новой вершине и
вершинам удаленного ребра.
Графы называются гомеоморфными, если один можно получить из другого путём
применения конечного числа раз операции разбиения ребра.
Обратная процедура к разбиению ребра называется стягиванием ребра.
Теорема
Для того, чтобы граф был планарным необходимо и достаточно, чтобы он не
содержал в себе подграфов, гомеоморфных K3,3, K5.

83.

Алгоритм определения планарности графа
с использованием цикла Гамильтона.
1)Строим в графе цикл Гамильтона;
2)Строим граф так, чтоб цикл Гамильтона имел форму
выпуклого многоугольника, а ребра находились
внутри цикла.
3)Строим вспомогательный граф, вершинами которого
являются ребра, не вошедшие в цикл Гамильтона, а
ребрами являются пересекающиеся пары этих
ребёр.
4)На вершинах вспомогательного графа строим
максимально возможный связанный фрагмент без цикла.
5)Наносим оставшиеся ребра.
Делаем пометки 2 типов, чтобы
смежные вершины имели разные пометки (+,-).
Хв={z1,z2,z3,z4,z5}
Если ребра соединяют вершины с одинаковыми
Zв={ {z1,z2}, {z1,z3}, {z3,z4},
пометками, то граф не является планарным.
{z2,z5}, {z4,z5} }

84.

Гамма-алгоритм нахождения плоской укладки.
Для плоской укладки графа и попутной проверки, планарен ли он, удобно пользоваться
гамма-алгоритмом.
На вход подаются графы, обладающие следующими свойствами:
1. граф связный;
2. граф имеет хотя бы один цикл;
3. граф не имеет мостиков, т. е. ребер, после удаления которых граф распадается на две
компонеты связности.
Если нарушено свойство (1), то граф нужно укладывать отдельно по компонентам
связности.
Если нарушено свойство (2), то граф — дерево и нарисовать его плоскую укладку
тривиально.
Если нарушено свойство (3, то нужно разрезать мостики и провести отдельно плоскую
укладку каждой компоненты связности, а затем соединить их мостиками.
Вершины, которые одновременно принадлежат G′ и какому-то сегменту, назовем
контактными.
Если бы в каком-нибудь сегменте не было ни одной контактной вершины, то граф
до разрезания был бы несвязный; если бы была только одна, то граф имел бы мостик.
Если все контактные вершины сегмента S имеют номера вершин какой-то грани Γ,
то грань Γ вмещает этот сегмент (S⊂Γ).
Может быть имеется не одна такая грань, вмещающая сегмент S, множество
таких граней обозначим Γ(S), а их число |Γ(S)|.

85.

Гамма-алгоритм нахождения плоской укладки.
1. Выбираем любой простой цикл C исходного графа G; изобразим
его на плоскости в виде грани, которую примем за уже уложенную часть
G′; сформируем сегменты Si; если множество сегментов пусто, то
перейти к п. 3.
2. Пока множество сегментов непусто:
a. Для каждого сегмента S найти множество Γ(S). Если существует
сегмент S, для которого |Γ(S)| = 0, то граф не планарный.
b. Выбираем один из сегментов с минимальным числом, вмещающих
его граней.
c. Выбираем одну из подходящих граней для выбранного сегмента.
d.В данном сегменте выбираем цепь между двумя контактными
вершинами и укладываем ее в выбранной грани. Учтем изменения в
структуре сегментов и перейдем к п. a).
3. Построена плоская укладка G′ исходного графа G.

86.

Гамма-алгоритм нахождения плоской укладки.
Пример