Дискретная математика

vk.com/club152685050 | vk.com/id446425943

4.Матрица инцидентности R:

deg xi 10

Замечание. Сумма элементов в строке равна степени соответствующей вершины.

Опр. Пусть дан граф G M , и пусть среди элементов множества Г встречаются пары (x,x) или некоторые пары (x,y) входят в Г несколько раз, тогда совокупность G задает мультиграф. При этом элементы (x,x) называются петлями при вершине x, а повторяющиеся пары (x,y) называются кратными ребрами.

k, (x, y) Г , к кратность ребра (x, y)

81

deg x 2 Г

deg x 2 Г , колличество петель

§2. Изоморфизм графов

x, y M1 соединены ребром тогда и только тогда, когда соединения ребром

вершины (х) , ( у) М2 .

Замечание. Количество вершин и количество ребер в изомерных графах одинаково; степени вершин х и (х) равны

Пример. Доказать, что графы изоморфны:

vk.com/club152685050 | vk.com/id446425943

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

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

Матрицы смежности из предыдущего примера:

последовательность вершин и соединяющих их ребер вида:

xi1, (xi1, xi2 ), xi2 , (xi2 , xi3 ),...(xin 1, xin ),...(xin 1, xin ), xin - маршрут из xi1 в xin .

2)Маршрут называют замкнутым, если первая и последняя вершины маршрута совпадают.

3)Цепь – это незамкнутый маршрут, все ребра которого различны.

4)Цикл – это замкнутый маршрут, все ребра которого различны.

5)Цепь называют простой, если все ее вершины различны.

6)Цикл называют простым, если все его вершины различны.

7)Длиной маршрута называют число его ребер.

Пример.

x4 x3 x5 x6 x3 x2 не простая цепь x4 x3 x2 x1 простая цепь

x4 x3 x5 x6 x3 x4 не простой цикл x4 x5 x6 x3 x4 простой цикл

83

vk.com/club152685050 | vk.com/id446425943

Лемма. Из всякого незамкнутого маршрута можно выделить простую цепь с теми же начальной и конечной вершинами.

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

см. “Конспект лекций по дискретной математике” Смирновой Е.Л.

Опр. Две вершины x и y графа G M , называется соединенными, если либо эти вершины совпадают, либо их можно соединить цепью, т.е. на множестве вершин М графа G задано бинарное отношение -отношение соединенности.

(x, y) : x, y M , x и y соединенны е вершины

Нетрудно убедиться, что отношение соединенности является отношением эквивалентности (доказать самостоятельно)

Замечание. Не надо путать понятие “смежности” и “соединенности”

x1 и x3 не смежные вершины, но соединенные.

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

Т.к. отношение соединенности вершин графа является отношением эквивалентности, то оно задает разбиение графа G на непересекающейся подграфы, которые называются компонентами связанности графа G.

G G1 G2 ... Gk ; Gi G j Ø , i j

Пример. Граф G не является связным графом:

3 компоненты связанности:

84

vk.com/club152685050 | vk.com/id446425943

G1 x1 ,

G2 x2 , x3 , x4 , x2 , x3 , x3 , x4

G3 x5 , x6 , x5 , x6

Замечание. Связный граф состоит из одной компонента связанности.

Пусть S- матрица смежности графа G, S n s n-я степенная матрица G .

Теорема (Свойства степени матрицы смежности)

Элемент s (jin) матрицы S n равен количеству всех маршрутов длины n из

1

4) Теорема справедлива для любого натурального числа n.

ч.т.д.

Опр. Матрицей связности (соединенности) графа G M , называется

§4. Деревья и их свойства

Опр. Деревом называется связный граф без циклов.

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

- тривиальное дерево

86

vk.com/club152685050 | vk.com/id446425943

M , Г количество вершин и ребер.

Теорема (о свойствах деревьев).

Следующие утверждения равносильны:

1)Граф G=<М,Г> - дерево.

2)Граф G=<М,Г> - связный граф, и число его ребер на единицу меньше числа вершин: Г М 1.

3)G –связный граф без циклов

4)Любые две вершины графа можно соединить единственной цепью.

Докажем равносильность утверждений 1) и 4), остальное очевидно:

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

б) 4) 1) . Пусть в графе G существует цикл, следовательно, найдутся две вершины цикла, соединенные различными цепями, что противоречит утверждению 4), следовательно, граф нее имеет циклов и связный, т.е G- дерево.

Ч.т.д.

Опр. 1) Расстоянием между вершинами графа х и у называется длина цепи, связывающей эти вершины d (x, y) .

2) Эксцентрисетом вершины х называется наибольшее расстояние между вершиной х и любой другой вершиной у (x) max( d (x, y)) .

3)Радиусом дерева G называется наименьший из эксцентриситетов всех вершин дерева r(G)=min(E(x)).

4)Вершина х, эксцентриситет, которой равен радиусу дерева, называется

центральной.

5)Центром дерева называется множество его центральных вершин.

87

vk.com/club152685050 | vk.com/id446425943

Утверждение. Каждое дерево имеет либо одну либо две смежные центральные вершины.

§5. Опорное дерево

Опр. Опорным деревом связного графа G=<М,Г> называется подграф G`=<М,Г1>, содержащий все вершины графа G и являющийся деревом.

Пример. Построить несколько неизоморфных опорных деревьев графа:

Существует два неизоморфных опорных дерева:

Теорема (о существовании опорного дерева).

Для любого опорного графа G существует опорное дерево.

Алгоритм построения опорного дерева.

1.Выделим в множестве М произвольную вершину xi1 получим одновершинное дерево, обозначим полученный граф G ' {xi1}, ø ; k=1 – количество вершин.

2.Если k=|М| то задача решена, и G` является опорным деревом. Если k<|M| переходим к шагу 3.

vk.com/club152685050 | vk.com/id446425943

Полученный таким образом подграф опять обозначим G ' ; очевидно что вершина - висячая и не создает циклов; т.е. G ' - дерево. Присваиваем k:=k+1 и переходим к шагу 2.

Т.к. число вершин графа конечно, то на n-ом шаге построим опорное

дерево.

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

Опр. Цикломатическим числом графа называют число ν(G)=|Г|-|M|+1

Теорема (о связи числа ребер связного графа и его опорного дерева)

Пусть дан граф G' М , Г . Опорное дерево графа G=<M,Г>равно

ν (G)= |Г|-|Г`|

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

Число вершин в G и G` одинаково; Т.к. G` - дерево, то

| Г ' | | M | 1 (G) | Г | (| M | 1) | Г | | Г ' |

ч.т.д.

Очевидно, что цикломатическое число дерева ν(G)=0.

Утверждение: Пусть G – лес, состоящий из p деревьев, тогда его цикломатическое число ν(G)=1- p

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

i 1

(G) | Г | | M | 1 | M | p | M | 1 1 p

ч.т.д.

§ 6. Минимальное опорное дерево (МОД)

Поставим каждой дуге графа в соответствие некоторого неотрицательное число.

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

89

vk.com/club152685050 | vk.com/id446425943

Задача. Построение МОД состоит в нахождение опорного дерева связного нагруженного графа с минимальной суммой длин ребер.

Алгоритм Прима-Краскала для построения МОД:

1.Выберем в G ребро наименьшей длины. Это ребро и инцидентные ему вершины обозначим как граф G`. k=|M|=2 - число вершин графа G`.

2.Если k=|M| - то построение МОД закончено.

3.Если k<M, то среди всех ребер графа G, не содержащихся в G`, находим ребро наименьшей длины, инцидентное одной из вершин графа G` и вершине, не содержащейся в G`. Присоединим это ребро и вершину к графу G`; присвоим k:=k+1 и переходим к п.2.

Т.к. количество вершин графа конечно, то за |M|-1 шаг МОД будет построено. Полученное таким образом дерево будем минимальным в смысле суммы длин (весов) всех его ребер.

Пример. Построить минимальное опорное дерево для графа:

Построение:

§7. Планарные графы

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

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

Опр. Эйлеровой характеристикой связного планарного графа G=<М,Г>

называют число W=|M|-|Г| + S

90