Быстрый поиск

Определим граф как конечное множество вершин V и набор Е неупорядоченных и упорядоченных пар вершин и обозначим G=(V,E). Мощности множеств V и Е будем обозначать буквами N и М Неупорядоченная пара вершин называется ребром, а упорядоченная пара - дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины и и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться.

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

Матрица смежности - это двумерный массив размерности N*N. 1, вершина с номером i смежна с вершиной с номером j, 0, вершина с номером i не смежна с вершиной с номером j

Для хранения перечня ребер необходим двумерный массив R размерности М*2. Строка массива описывает ребро.

Достижимость

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

Простой путь - это путь, в котором каждая дуга используется не более одного раза.

Элементарный путь - это путь, в котором каждая вершина используется не более одного раза.

Если существует путь из вершины графа v в вершину i, то говорят, что i достижима из v.

Матрицу достижимости определим следующим образом:

1, если вершина i достижима из v и

R[v,u]=0, при недостижимости

Множество R(v) - это множество таких вершин графа G, каждая из которых может быть достигнута из вершины v. Обозначим через F(v) множество таких вершин графа G, которые достижимы из v с использованием путей длины 1. T2(v) - это Г(Г(у)), то есть с использованием путей длины 2 и так далее. В этом случае:

R(v)={v}UГ(v)UГ2(v)U...UГp(v).

При этом р - некоторое конечное значение, возможно, достаточно большое.

Пример (для рисунка). R(1)={1}U{2,5}U{1,6}U{2,5,4}U{1,6,7}={1,2,4,5,6,7}

Выполняя эти действия для каждой вершины графа, мы получаем матрицу достижимостей R.

Кратчайшие пути.

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

Дано. Ориентированный граф G=<V,E>, s - вершина источник; матрица смежности A (A:array[1..n,1..n] of integer); для любых u, v€V вес дуги неотрицательный (А[u,v]>=0). Результат. Массив кратчайших расстояний - D.

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

Пример

Его матрица смежности:

∞ 3 7 ∞ ∞ ∞

1 ∞ 2 ∞ ∞ 1

А= ∞ 1 ∞ 4 4 ∞

∞ ∞ ∞ ∞ 1 5

∞ ∞ 1 ∞ ∞ 3

∞ ∞ ∞ 2 ∞ ∞

В таблице приведена последовательность шагов (итераций) работы алгоритма. На первом шаге минимальное значение D достигается на второй вершине. Она исключается из множества Т, и улучшение оценки до оставшихся вершин (3,4,5,6) ищется не по всем вершинам, а только от второй.

№ итерации	D[1]	D[2]	D[31	D[4]	D[5]	D[6]	T
1	0	3	7	∞	∞	∞	[2,3,4,5,6]
2	0	3	5	∞	11	4	[3,4,5,6]
3	0	3	5	6	∞	4	[3,4,5]
4	0	3	5	6	9	4	[4,5]
5	0	3	5	6	7	4	[5]

Время работы алгоритма пропорционально N2.

Алгоритм Флойда (кратчайшие пути между всеми парами вершин).

Дано. Ориентированный граф G=<V,E>, s - вершина источник; матрица смежности A (A:array[1..n,1..n] of integer); для любых u, v€V вес дуги неотрицательный (А[u,v]>=0). Результат. Матрица D кратчайших расстояний между всеми парами вершин графа и кратчайшие пути.

Идея алгоритма. Обозначим через Dm[i,j] оценку кратчайшего пути из i в j с промежуточными вершинами из множества [1..m]. Тогда имеем: D0[i,j]:=A[i,j] и D(m+1)[i,j]=min{Dm[i,j],Dm[i,m+1]+Dm[m+1,j]}. Второе равенство требует пояснения. Пусть мы находим кратчайший путь из i в j с промежуточными вершинами из множества [1..(m+1)]. Если этот путь не содержит вершину (m+1), то D(m+1)[i,j]=Dm[i,j]. Если же он содержит эту вершину, то его можно разделить на две части от i до (m+1) до j. Время работы алгоритма пропорционально N3.

Глава 2 Система задач и упражнений.

Классификация задач.

Набор задач, разработанный нами и изложенный ниже можно систематизировать по следующим критериям:

По тематике.

По уровню сложности задачи.

Задачи высокого уровня сложности: это задачи олимпиадного уровня, требующие глубокого знания предмета, а также комплексного подхода к решению задачи (Пример для нашего набора задач, задача о роботах, задача о комнатах музея).

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7