Основы теории графов.ppt

элементами конечного множества

множество вершин,  
N — конечное множество дуг, соединяющих вершины,
 T — отображение

из  N  в  M × M, которое сопоставляет каждой дуге упорядоченную пару вершин. Первая из них называется началом этой дуги, а вторая — концом дуги.

M ={A, B, C, D, E} 
N = {1, 2, 3, 4, 5},
T(1) = (D,A); T(2) = (D,B);
T(3) = (B,C); T(4) = (C,E); T(5) = (E,D);

ориентирована, ориентированным (орграфом), если ориентированы все его дуги, смешанным, если есть как

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

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

лишь показать, какие пары вершин соединены рёбрами, а какие — нет.

Граф

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

ВАЖНО: Форма линии и расположение вершин на рисунке произвольны.

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

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

мостах: в городе Кёнигсберге в начале XVIII века было семь

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

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

(к которым ведёт нечётное число рёбер) графа должно быть чётно.

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

Карта из статьи 28-летнего Эйлера в трудах Санкт-Петербургской Академии наук 

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

Созданная Эйлером теория графов нашла очень широкое применение: например, её используют при изучении транспортных и коммуникационных систем, в частности, для маршрутизации данных в Интернете.

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

Уильям

Роуэн Гамильтон

Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.

параметры (стоимость, расстояние, пропускная способность и т.п.).

Сеть автомобильных дорог

Определить маршруты прокладки кабелей вдоль существующих дорог, схема которых представлена

на графе, таким образом, чтобы общая длина была минимальной.

некоторое число w(j), называемое весом или длиной этой дуги.
Сумму весов дуг дерева называют весом дерева.

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

Рассмотрим два метода: алгоритм Прима и алгоритм Краскала

Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом

Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э.Дейкстрой в 1959 году.

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

Вводим эти вершины в множество V*={ V1,V6}.
Выбираем ребро минимального

веса, исходящее из вершин V*: (V1, V4)=3.
Добавляем V4 в V*: V*={V1, V4, V6}

Выбираем ребро минимального веса, смежное с вершинами V*: (V4, V5)=1;
добавляем вершину V5 в V*: V*={V1, V4, V5, V6}
Выбираем ребро минимального веса, смежное с вершинами V*: (V4, V2 ) = 3;
добавляем вершину V2 в V*: V*={V1, V2, V4, V5, V6}.
Выбираем ребро минимального веса, смежное с вершинами V*: (V2 ,V7) = 1; добавляем вершину V7 в V*: V*={V1, V2, V4, V5, V6, V7}.
Выбираем ребро минимального веса, смежное с вершинами V*: (V2, V3 ) = 2; добавляем вершину V3 в V*: V*={V1, V2, V3, V4, V5, V6, V7}.
Неохваченных вершин не осталось.
Длина остовного дерева: L= 1+3+1+3+1+2 = 11

1957 г.
Алгоритм состоит из двух фаз.


Джозеф Краскал
На подготовительной фазе

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

1.
Вводим вершины в множество V*={ V1,V6}
Находим ребро веса

1: (V2, V7) = 1.
Вводим вершины в множество V*={ V1,V2,V6,V7}
Находим ребро веса 1: (V4, V5) = 1.
Вводим вершины в множество V*={ V1,V2, V4,V5, V6,V7}
Ребер веса 1 больше нет.
Теперь вводим ребра веса 2, так, чтобы не образовать циклы, но повышать связность графа.
Вводим в дерево ребро веса 2: (V3, V7) = 2.
Вводим вершины в множество V*={ V1,V2, V3, V4,V5, V6,V7}
Ребер веса 2 (не образующих циклов с существующими) больше нет.
Теперь вводим ребра веса 3, так, чтобы не образовать циклы, но повышать связность графа.
Находим ребро веса 3: (V1, V4) = 3.
Находим ребро веса 3: (V4, V7) = 3.
Все вершины включены в дерево. Граф связный.
Вес дерева L = 1+1+1+2+3+3 = 11.

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

собой большой массив векторов. Мы должны использовать его и рассчитать оптимальный маршрут.

Существует несколько методов поиска кратчайших путей в графе:
алгоритм Дейкстры (поиск кратчайших путей от заданной вершины);
алгоритм Флойда (поиска длин всех кратчайших путей в графе);
алгоритм Данцига.

задачи. Предложен в 1959 г. голландским математиком Дейкстрой (1930-2002), известным,

в частности, своей борьбой против безбрежного использования в программировании оператора go to. Эта борьба привела к существенному улучшению стиля программирования.

Эдсгер Вибе Дейкстра

Главная идея, лежащая в основе алгоритма Дейкстры Предположим, что нам известны m вершин, ближайших к вершине S (близость любой вершины X к вершине S определяется длиной кратчайшего пути, ведущего из S в X). Пусть также известны сами кратчайшие пути, соединяющие вершину S с выделенными m вершинами). Нужно ввести правило, как может быть определена (m+1)-я ближайшая к S вершина.

вершин.
Построим для каждой неокрашенной вершины Y пути, непосредственно соединяющие с

помощью дуг (х, у) каждую окрашенную вершину Х с Y.
Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины S в вершину Y.
Какая же из неокрашенных вершин является (m+1)-й ближайшей к S вершиной?
Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины S в (m+1)-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т. е. вершины, входящие в число m вершин, ближайших к вершине S.
Итак, если известны m ближайших к s вершин, то и (m+1)-я ближайшая к S вершина может быть найдена.
Начиная с m = 0, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины S к вершине T.

равное длине кратчайшего пути из вершины S в вершину X

и включающем только окрашенные вершины.
Положиv d(s)=0 и d(x)=∞ для всех остальных вершин графа.
Окрашиваем вершину S и полагаем Y=S, где Y – последняя окрашенная вершина.
Для каждой неокрашенной вершины X пересчитывается величина d(x) по следующей формуле:
d(x) = min {d(x); d(y)+ ay,x}
5) Если d(x)=∞ для всех неокрашенных вершин, то алгоритм заканчивается т. к. отсутствуют пути из вершины S в неокрашенные вершины. Иначе окрашивается та вершина, для которой величина d(x) является минимальной.
Окрашивается и дуга, ведущая в эту вершину, и полагаем Y=X.
6) Если Y=T, кратчайший путь из S в T найден. Иначе переходим к шагу 2.

остальных.

Первый шаг. Минимальную метку имеет вершина 1.
Её соседями являются

вершины 2, 3 и 6.

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

вершин. Это вершина 2 с меткой 7.
Пытаемся уменьшить метки соседей

выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

«обработки» получим:
Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин. Это

будут вершины 6, 4 и 5, соответственно порядку.

отличии от алгоритма Дейкстры, который позволяет построить ориентированное дерево кратчайших

путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе.
Конечно эта задача может быть решена и многократным применением алгоритма Дейкстры (каждый раз последовательно выбираем вершину от первой до N-ной, пока не получим кратчайшие пути от всех вершин графа), однако реализация подобной процедуры требует значительных вычислительных затрат.

Роберт Флойд

через di,jm длину кратчайшего пути из вершины i в вершину j,

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

Если между вершинами i и j не существует ни одного пути указанного типа, то условно будем считать, что di,jm=∞.

Величина di,j0, представляет длину кратчайшего пути из вершины i в вершину j, не имеющего промежуточных вершин, т. е. длину кратчайшей дуги, соединяющей i с j (если такие дуги присутствуют в графе).

di,jm.
Если в исходном графе нам известна длина каждой дуги,

то мы можем сформировать матрицу D0, которая в алгоритме Флойда выступает в качестве исходной.
Вначале из этой матрицы вычисляется матрица D1. Затем по матрице D1 вычисляется матрица D2 и т. д. по формуле:
di,jm = min{ di,mm-1 + dm,jm-1; di,jm-1}
Процесс повторяется до тех пор, пока по матрице DN-1 не будет вычислена матрица DN.

из вершины i в вершину j короче, если будет проходить

через некоторую промежуточную вершину m.

Пусть есть три вершины – i, j,m – и расстояния между ними: dij, dim, dmj.
Если выполняется неравенство dim + dmj < dij, то целесообразно заменить путь i? j путём i ? m ? j

«Треугольный оператор»

матрицу D0, каждый элемент di,j0 которой есть длина кратчайшей дуги

между вершинами i и j. Если такой дуги нет, положить значение элемента di,j0 = ∞. Значения диагональных элементов di,i = 0.

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

пути, заполним так: sij = j
Алгоритм Флойда на примере

ведущую строку и ведущий столбец.
Для всех элементов dij матрицы Dm-1

рассматриваем возможность применения треугольного оператора. Если выполняется неравенство:
dim + dmj < dij (i≠j, j≠m, i≠m),
то делаем следующее:
а) в матрице Dm заменяем элемент dij матрицы Dm-1 суммой dim + dmj;
b) в матрице Sm меняем элемент sij матрицы Sm-1 на m;
c) полагаем m=m+1, повторяем основной этап, пока m < N

Основной этап

по матрицам Dn и Sn кратчайшего пути между узлами i

и j выполняется по следующим правилам:

Кратчайшее расстояние между узлами i и j равно элементу dij в матрице Dn.
Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn. Пусть sij = k, тогда имеем путь i ? j? k.
Если далее sik = k и skj = j, то считаем, что весь путь определён. В противном случае повторяем процедуру для путей от узла i к узлу k и от узла k к узлу j.

1


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

по разу в неизвестном порядке города 2, 3, …, n и вернуться

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

В терминах теории графов задача формулируется так: имеется полный ориентированный граф G = (M, N), каждой дуге (i, j) которого сопоставлен вес dij. Требуется найти в этом графе гамильтонов контур наименьшей стоимости.

разделить огромное число перебираемых вариантов на классы и получить оценки

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

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

Метод ветвей и границ ("поиск с возвратом", "backtracking")

такова:
Ветвление основано на следующем простом соображении: переезд из любого данного

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

Алгоритм Литтла для задачи коммивояжера (Литтла, Мурти, Суини и Кэрел)

его из всех элементов строки. Сделаем это и для столбцов,

не содержащих нуля. Получим матрицу стоимости, каждая строка и каждый столбец которой содержат хотя бы один нулевой элемент.
Для каждого нулевого элемента матрицы dij  рассчитаем коэффициент Гij, который равен сумме наименьшего элемента i строки (исключая элемент dij=0) и наименьшего элемента j столбца. Из всех коэффициентов  Гij выберем такой, который является максимальным Гkl = max{Гij}. В гамильтонов контур вносится соответствующая дуга (k,l).

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

элемента dlk (поскольку дуга (k,l) включена в контур, то обратный путь

из l в k недопустим).
Повторяем алгоритм c шага 1, пока порядок матрицы не станет равным двум.
Затем в текущий ориентированный граф вносим две недостающие дуги, определяющиеся однозначно матрицей прядка 2. Получаем гамильтонов контур.

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

граница равна сумме всех вычтенных элементов в строках и столбцах.

Итоговое значение нижней границы должно совпасть с длиной результирующего контура (пути).

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

30
Во всех столбцах есть нулевые элементы.
Приводить по столбцам не

нужно

Его стоимость 30.


Алгоритм Литтла (пример. Шаг 1)

Таким образом, мы получили

нижнюю оценку стоимости класса всех возможных туров.
То есть минимальный тур в данной задаче
не может стоить меньше, чем 30.

j) в матрице сумму минимальных элементов в i-й строке и

j-м столбце (не считая сам этот ноль).
Оценим каждый ноль в приведенной матрице:

max=12

если в тур не будет включен путь из i в

j (стоимостью 0), то придется доплатить как минимум k. Поэтому, можно разделить класс всех возможных туров на два: туры, содержащие ребро (i, j) и туры, не содержащие его. Для последних минимальная оценка увеличится на k.

Алгоритм Литтла (пример. Шаг 2)

это ребро (4, 5). Нижняя оценка стоимости класса туров, не

содержащих (4,5) увеличивается до 30+12=42.
Чтобы определить оценку для класса туров, содержащих дугу (4,5), удалим из матрицы строку 4 и столбец 5. Элемент d54 заменим ∞, чтобы не было замкнутого контура.

Алгоритм Литтла (пример. Шаг 3)

8 = 11

строке и столбцу
Алгоритм Литтла (пример. Шаг 2)
Дугу (4, 5) включаем

в путь

max=10

41+10=51.

Чтобы определить оценку для класса туров, содержащих дугу (1,2),

удалим из матрицы строку 1 и столбец 2. Элемент d21 заменим ∞, чтобы не было замкнутого контура.

Алгоритм Литтла (пример. Шаг 3)

(пример. Шаг 1,2)

Сумма констант приведения
равна 0 + 7 =

7

max=4

Оценим нулевые элементы

то нужно рассмотреть оба варианта.
Алгоритм Литтла (пример. Шаг 1,2)

и 3 столбец; d36= ∞


В каждой строке и столбце есть

0, поэтому сумма констант приведения равна 0

max=9

строку и 6 столбец
Путь: 1 ? 2 ? 4 ?

5 ? 6 ? 3 ? 1.
Длина пути: 48.

в ранее найденный путь длиной 48
Алгоритм Литтла (пример. Возврат к

слайду 56)

Сумма констант приведения =0

Удалим 2 строку и 4 столбец

5 ? 6 ? 3 ? 1.
Длина пути: 48.