Теория графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
?сточника Vi до всех остальных вершин графа, можно найти и сами кратчайшие (Vi, Vj) -маршруты. Действительно, пусть Vi, b1, b2, …, br, Vj - кратчайший (Vi, Vj) -маршрут. Тогда по строке Д(n-1) вершина br = Vk2 находится из соотношения
?? (Vi, Vj) = ?? (Vi, Vк1) + ?к1j, вершина br-1 = Vк2 из
?? (Vi, Vк1) = ?? (Vi, Vк2) + ?к2к1 и т.д.
В предыдущем примере кратчайший (1, 4)-маршрут определяется следующим образом: ?? (1, 4) = 3 = -1 + 4 = ?? (1, 5) + ?54, тогда br = 5; ?? (1, 5) = -1 = 4 - 5 = ?? (1, 3) + ?3,5, откуда br-2 = b2 = 3, br-3 = b1 = 2. Таким образом, кратчайший (1,4)-маршрут задается последовательностью вершин (1, 2, 3, 5, 4).
Алгоритм Дейкстры является более эффективным, чем алгоритм Форда-Беллмана, но используется только для взвешенных графов, в которых веса всех дуг неотрицательны.
Алгоритм Дейкстры:
-источник
Т1 = {2, 3, 4, 5, 6}
Д(1) = {0, 1, ?, ?, ?, ?}
-источник
Т2 = {3, 4, 5, 6}
Д(2) = {0, 1, 6, 3, ?, ?}
Д(1) = {d1(1), d2(1), d3(1), d4(1), d5(1), d6(1)}
d1(1) = 0, dj(1) = ?ij.
Д(2) = {d1(2), d2(2), d3(2), d4(2), d5(2), d6(2)}
dj(2) = min {dj(1), dk(1) + ?kj}, k = 1, 2, …, n
d2(2) = min {d2(1), dk(1) + ?k2} = min {1, 0 + 1} = 1
d3(2) = min {d3(1), dk(1) + ?k3} = min {?, 1 +5} = 6
d4(2) = min {d4(1), d2(1) + ?24} = min {?, 1 + 2} = 3
d5(2) = min {?, d6(1) + ?65} = {?, ?} = ?
d6(2) = min {?, ? + ?36} = ?
_______________________________
Д(3) = {d1(3), d2(3), d3(3), d4(3), d5(3), d6(3)}
T3 = {3, 5, 6} 4 - источник
Д(3) = {0, 1, 4, 3, 7, 8}
d3(3) = min {d3(2), d4(2) + ?43} = min {6, 3 + 1} = min {6, 4} = 4
d4(3) = min {3, d2(2) + ?24} = min {3, 1 + 2} = 3
d5(3) = min {?, d6(2) + ?65} = {?, d4(2) + ?45} = min {?, 3 + 4} = 7
d6(3) = min {?, d2(2) + ?36} = min {?, 1 + 7} = 8
Д(4) = {d1(4), d2(4), d3(4), d4(4), d5(4), d6(4)}
T4 = {5, 6}
Д(4) = {0, 1, 4, 3, 7, 5}
d4(4) = min {d4(3), d2(3) + ?23} = min {3, 1 + 5} = 3
d5(4) = min {d5(3), d6(3) + ?65} = 3
d6(4) = min {d6(3), d3(3) + ?36} = min {8, 4 + 1} = 5
T5 = {5}
Д(5) = {d1(5), d2(5), d3(5), d4(5), d5(5), d6(5)}
Д(5) = {0, 1, 4, 3, 6, 5}
d4(5) = min {d4(4), d2(4) + ?24} = min {3, 1 + 2} = 3
d5(5) = min {d5(4), d6(4) + ?65} = min {7, 5 + 1} = 6
d6(5) = min {d6(4), d3(4) + ?36} = min {5, 4 + 1} = 5
?? (1, 1) = 0
?? (1, 2) = 1
?? (1, 3) = 4
?? (1, 4) = 3
?? (1, 5) = 6
?? (1, 6) = 5
Минимальный путь из V1 до V7
-источник Т1 = {2, 3, 4, 5, 6, 7}
Д(1) = {0, ?, 5, 4, 2, 2, 9}
-источник Т2 = {2, 3, 4, 6, 7}
Д(2) = {0, ?, 4, 4, 2, 2, 8}
d2(2) = min {d2(1), d5(1) + ?52} = min {?, 2 + ?} = ?
d3(2) = min {d3(1), d5(1) + ?53} = min {5, 2 +2} = 4
d4(2) = min {d4(1), d5(1) + ?54} = min {4, 2 + 2} = 4
d5(2) = min {d5(1), d5(1) + ?56} = min {2, 2 + 0} = 2
d6(2) = min { d6(1), d5(1) + ?56} = min {2, 2 + 1} = 2
d7(2) = min { d7(1), d5(1) + ?57} = min {9, 2 + 6} = 8
-источник Т3 = {2, 3, 4, 7}
Д(3) = {0, 7, 4, 3, 2, 2, 8}
d2(3) = min {d2(2), d6(2) + ?62} = min {?, 2 + 5} = 7
d3(3) = min {d3(2), d6(2) + ?63} = min {4, 2 + ?} = 4
d4(3) = min {d4(2), d6(2) + ?64} = min {4, 2 + 1} = 3
d5(3) = min {d5(2), d6(2) + ?65} = min {2, 2 + 1} = 2
d6(3) = min {d6(2), d6(2) + ?66} = min {2, 2 + 0} = 2
d7(3) = min {d7(2), d6(2) + ?67} = min {8, 2 + ?} = 8
-источник Т4 = {2, 3, 7}
Д(4) = {0, 5, 4, 3, 2, 2, 8}
d2(4) = min {d2(3), d4(3) + ?42} = min {7, 3 + 2} = 5
d3(4) = min {d3(3), d4(3) + ?43} = min {4, 3 + 1} = 4
d4(4) = min {d4(3), d4(3) + ?44} = min {3, 3 + 0} = 3
d5(4) = min {d5(3), d4(3) + ?45} = min {2, 3 + 1} = 2
d6(4) = min {d6(3), d4(3) + ?46} = min {2, 3 + ?} = 2
d7(4) = min {d7(3), d4(3) + ?47} = min {8, 3 + ?} = 8
-источник Т5 = {2, 7}
Д(5) = {0, 5, 4, 3, 2, 2, 7}
d2(5) = min {d2(4), d3(4) + ?32} = min {5, 4 + ?} = 5
d3(5) = min {d3(4), d3(4) + ?33} = min {4, 4 + 0} = 4
d4(5) = min {d4(4), d3(4) + ?34} = min {3, 4 + 1} = 3
d5(5) = min {d5(4), d3(4) + ?35} = min {2, 4 + 1} = 2
d6(5) = min {d6(4), d3(4) + ?36} = min {2, 4 + 1} = 2
d7(5) = min {d7(4), d3(4) + ?37} = min {8, 4 + 3} = 7
-источник Т6 = {7}
Д(6) = {0, 5, 4, 3, 2, 2, 6}
d2(6) = min {d2(5), d2(5) + ?22} = min {5, 5 + 0} = 5
d3(6) = min {d3(5), d2(5) + ?23} = min {4, 5 + 1} = 4
d4(6) = min {d4(5), d2(5) + ?24} = min {3, 5 + 1} = 3
d5(6) = min {d5(5), d2(5) + ?25} = min {2, 5 + ?} = 2
d6(6) = min {d6(5), d2(5) + ?26} = min {2, 5 + 1} = 2
d7(6) = min {d7(5), d2(5) + ?27} = min {7, 5 + 1} = 6
?? (1, 1) = 0
?? (1, 2) = 5
?? (1, 3) = 4
?? (1, 4) = 3
?? (1, 5) = 2
?? (1, 6) = 2
?? (1, 7) = 6
4. Раскраска графов
Пусть G = - нефграф без петель.
Раскраской (вершин) графа G называется такое задание цветов вершинам G, что если (Vi, Vj)-дуга, то вершины Vi, Vj имеют различные цвета. Хроматическим числом Х (G) графа G называется минимальное число цветов, требующиеся для раскраски G (рис. )
Пример. Так как в полном графе Gn любые две различные вершины связаны ребром, то Х (Gn) = n.
Многие практические задачи сводятся к построению раскрасок графов.
Пример 1. Рассмотрим задачу составления расписания. Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно. Построим граф G, вершины которого биективно соответствуют лекциям и две вершины смежны тогда и только тогда, когда соответствующие им лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам одного цвета, могут читаться одновременно. Напротив, любое допустимое расписание определяет раскраску графа G. Оптимальные расписания соответствуют раскраскам с минимальным числом цветов, а число часов, необходимое для прочтения всех лекций, равно Х (G).
Пример 2. Рассмотрим граф G, вершины которого - страны, а ребра соединяют страны, имеющие общую границу. Число Х (G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет.
Пример. Проводится монтаж аппаратуры. Чтобы не перепутать проводники, необходимо их окрасить таким образом, чтобы два проводника, идущие к одной плате, имели разные цвета. В этом случае вершинами являются платы, а ребрами - проводники.
Неорграф G называется бихроматическим, если Х (G) = 2. Неорграф G = называется двудольным, если множество всех ребер графа G образует разрез графа G, т.е. для некоторого разбиения множества вершин {V1, V2} концы любого ребра принадлежат разным частям разбиения.
Примером служит задача Три дома, три колодца.
Рассмотрим простой алгоритм построения раскраски, который во многих случаях приводит к раскраскам, близким к минимальным.
. Прои?/p>