Теория графов. Основные понятия и определения

1.Графом G=(V,E) (или G=(p,q))называется пара множеств, где V – непустое, конечное множество, состоящее из р элементов(вершин графа G), E – множество неупорядоченных пар элементов q(ребра).

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

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

Если Е – пустое множество, то граф G – пустой граф. Мультиграф – между двумя вершинами можно нарисовать 2 и более ребра.

Если имеются вершины V1 и V2 и ребро е образовано ими, то говорят, что ребро е инцедентно вершинам V1 и V2. V1 и V2 – смежные.

Степенью вершины называется число ребер инцидентных данной вершине(количество выходящих из нее ребер). Вершина, степень которой равна 1, называется висящей.

Вершина, степень которой равна 0, называется изолированной.

Последовательность ребер V0, V1… называется маршрутом. Если в маршруте не указаны ребра, то такой маршрут называется цепью. Если V0=Vn, то цепь называют циклом. Если в цепи не повторяются вершины, то такая цепь называется простой.

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

Если в связном графе имеется цикл, проходящий через все ребра графа, то граф называется Эйлеровым.

Связный граф, не имеющий циклов – дерево.

Способы задания графов

1.Матрица смежности вершин графа – квадратная матрица н порядка, где н – число вершин. Строки и столбцы матрицы соответствуют вершинам графа. Элементы р_ijравны числу дуг, направленных из и в жи. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0 либо 1. В случае не ориентированного графа ему вместе с ребром (X_i X_j) принадлежит ребро (X_i X_j).

2.Матрица смежности дуг – квадратная матрица м порядка, м – число дуг. Строки и столбцы матрицы соответствуют дугам графа. Элементы q­ij­ равны 1, если дуга у_i непосредственно предшествует дуге y_j и 0 в остальных случаях.

3.Матрица смежности ребер неориентированного графа – матрица м порядка, м – число ребер с элементами q_ij = 1, если ребра y­­_I y_j имеют общую вершину и 0 в остальных.

4.Матрица инцидентности орграфа – прямоугольная матрица, размерности Н х М, строки которой соответствуют вершинам, а столбцы дугам орграфа. Элементы r­_ij равны 1, если дуга y_j исходит из I вершины. Равны 0, если дуга не инцидентна итой вершине.

В случае неориентированного графа будет или 0.

1.

	Х1	Х2	Х3	Х4	Х5	Х6
Х1	0	1	0	0	0	0
Х2	0	0	0	1	0	0
Х3	1	1	0	1	0	0
Х4	0	0	0	0	0	1
Х5	1	0	1	0	0	1
Х6	0	0	0	0	0	0

2.

U1	0	0	0	0	0	1	0	0	0
U2	1	0	0	0	0	0	0	0	0
U3	0	0	0	1	1	0	1	0	0
U4	1	0	0	0	0	0	0	0	0
U5	0	0	0	0	0	1	0	0	0
U6	0	0	0	0	0	0	0	0	1
U7	0	0	0	0	0	0	0	0	1
U8	0	0	0	0	0	0	0	0	0
U9	0	0	0	0	0	0	0	0	0

3.

	U1	U2	U3	U4	U5	U6	U7	U8	U9
X1	1	-1	0	-1	0	0	0	0	0
X2	1	0	0	0	-1	1	0	0	0
X3	0	0	-1	1	1	0	1	0	0
X4	0	0	0	0	0	-1	-1	0	1
X5	0	1	1	0	0	0	0	1	0
X6	0	0	0	0	0	0	0	-1	-1

Остовные деревья минимального веса. Алгоритмы Прима и Крускала

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

Постановка задачи:

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

Алгоритм Прима

1.Выбирается подграф G₁ из множества G, вершинами которого являются вершины графа, имеющего одно ребро, выбранное из ребер графа G имеющих минимальный вес. На каждом последующем шаге уже построенному графу добавляется одно ребро.

К.Если подграф G_к-1 из множества G уже построен,… получается из G_к-1 добавлением ребра Л обладающего свойствами:

1.Л инцедентно какому-либо ребру G_к-1

2.При добавлении к Л G_{к-1 не обр цикла}

3.Л имеет минимальный вес среди ребер, удовлетворяющих условию 1 и 2.

Алгоритм Крускала

1.Выбирается подграф G₁ из множества G, вершинами которого являются вершины графа, имеющего одно ребро, выбранное из ребер графа G имеющих минимальный вес. На каждом последующем шаге уже построенному графу добавляется одно ребро.

К.Если подграф G_к-1 из множества G уже построен,… получается из G_к-1 добавлением ребра Л обладающего Свойства:

1.При добавлении Л G_к-1 не обр циклов

2. Л имеет мин вес среди ребер, удовлетворяющих условию 1.

Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дейкстры

Постановка задачи:

Пусть задан орграф G=(V,E) с заданными положительными длинами ребер. Найти длину кратчайшего пути(и сам путь), соединяющий 2 произвольные фиксированные вершины s(начало) и t(конец).

Алгоритм Дейкстры:

1.В начале алгоритма все вершины не окрашены. Каждой вершине В во время выполнения алгоритма ставиться в соответствие либо L(v) – длина кратчайшего пути включающего только окрашенные, L(v*) – временная метка, которая становиться равной L(v) в момент когда В окрашивается. Полагаем что L(s)=0, L(v*)…. Окрашиваем вершину s. Для каждой неокрашенной вершины и соседней с последней из окрашенных В пересчитываем L(u)=min(L*(u)L(v)+L(v,u)) , L(v,u) – длина дуги.

3(?).В момент, когда вершина t становиться окрашенной находим кратчайший путь, соединяющий s t , состоящий из окрашенных дуг.

s

c

d

t

a

b

3

2

4 7

2

3 2

3

L(s)=0 L(c)=3 L(a)=4 L(d)=6 L(b)=7

L*(a)=4 L*(d)=6 L*(b)=7 L*(t)=8 L*(t)=9

L*(b)=7 L*(d)=6

L*(c)=3

L(t)=8(s-c-d-t)

Алгоритм Флойда(расстояние между 2 точками)

Рассмотрим сеть, в каждой дуге которой (U,V) поставлено в соответствие действительное число L(u,v), называемое длиной дуги. В зависимости от конкретного приложения это число может быть мерой физического расстояния, времени, стоимости или иного параметра.

5

4

3

2

1

Длиной цепи называется сумма длин, взятая по всем дугам этой цепи.

L₀= здесь пишем расстояния из i в j

S₀= здесь пишем вершины (справочная)

Алгоритм Флойда

1.планируем,что вершины графа G – числа(1,2,…н). Обозначим через L₀ матрицу, элементами которой L_ij=длина или бесконечность(1.1 например). Введем матрицу S₀ матрица н*н, где элементы S_ij=j. Пусть матрицы L_p S_p найдены. Выделим элементы p строки и столбца, назовем их базовой строкой и базовым столбцом соответственно.

2.построим матрицы L_p+1 S_p+1 по следующим правилам:

а)элементы базовой строки и столбца переписываем без изменений.

б) если элемент L_ij>L_ip+1+L_p

3.алгоритм заканчивает свою работу, когда построены матрицы L_n и S_n.

Замечание 1.Если итый элемент базоваого столбца равен бесконечности, то для ээтой строки шаг 2 выполнять не нужно.

Замечание 2.Если житый элемент равен бесконечности, то шаг 2 выполнять не нужно.