Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах

Нажмите для полного просмотра!

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №2

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №3

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №4

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №5

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №6

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №7

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №8

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №9

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №10

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №11

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №12

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №13

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №14

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №15

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №16

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №17

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №18

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №19

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №20

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №21

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах, слайд №22

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах. Доклад-сообщение содержит 22 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах Лекция 7

Слайд 2

Описание слайда:

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ На взвешенном ориентированном графе G(X,U) требуется определить кратчайший путь из i-й вершины в j-ю.

Слайд 3

Описание слайда:

ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ

Слайд 4

$МЕТОД ПОТЕНЦИАЛОВ Шаг 1. Вершине присваивается потенциал P(s)=0. Шаг 2. Всем вершинам множества Х\ присвоить потенциал, равный ∞. Шаг 3. Каждой q-й вершине множества Х\ присваивается потенциал P(q): Шаг 4. Если потенциал хотя бы одной вершины изменился, то перейти к шагу 3, в противном случае – к шагу 5. Шаг 5. Конец алгоритма. Потенциал t-й вершины равен кратчайшему пути в нее из вершины .$

Описание слайда:

МЕТОД ПОТЕНЦИАЛОВ Шаг 1. Вершине присваивается потенциал P(s)=0. Шаг 2. Всем вершинам множества Х\ присвоить потенциал, равный ∞. Шаг 3. Каждой q-й вершине множества Х\ присваивается потенциал P(q): Шаг 4. Если потенциал хотя бы одной вершины изменился, то перейти к шагу 3, в противном случае – к шагу 5. Шаг 5. Конец алгоритма. Потенциал t-й вершины равен кратчайшему пути в нее из вершины .

Слайд 5

Описание слайда:

ПРИМЕР 1 Поиск длины кратчайшего пути из 1-й вершины в 4-ю.

Слайд 6

Описание слайда:

ДОСТОИНСТВА И НЕДОСТАТКИ Достоинства: Метод потенциалов гарантирует определение кратчайших путей из выбранной вершины во все остальные. Исключается необходимость перебора всех путей. Высокое быстродействие. Легкая программная реализация. Универсальность: метод применим к ориентированным и неориентированным графам. Недостатки: Вес каждой дуги должен быть положительным.

Слайд 7

Описание слайда:

РЕШИТЬ САМОСТОЯТЕЛЬНО Определить кратчайшие пути из 1-й вершины во все остальные.

Слайд 8

Описание слайда:

МАКСИМАЛЬНЫЕ ПОТОКИ НА ГРАФАХ Содержательная постановка задачи: требуется определить максимальный однородный поток на графе G(X,U) из вершины s в вершину t, если поток по каждой дуге графа (i,j) не может превышать ее пропускной способности r(i,j)

Слайд 9

Описание слайда:

Формальная постановка задачи о максимальном однородном потоке Обозначения: f(i,j) – поток по дуге , r(i,j) – пропускная способность дуги ; - вершина – источник; - вершина – сток.

Слайд 10

Описание слайда:

САМОСТОЯТЕЛЬНО Дайте иную формальную постановку задачи о максимальном потоке, в которой: эмиссионная способность источника ограничена; поглощающая способность стока ограничена; на графе имеется несколько источников и стоков.

Слайд 11

Описание слайда:

ЧАСТО ИСПОЛЬЗУЕМЫЙ АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА Шаг 1. Полученный граф G(X,U’) заменяется на G’(X,U’) такой, что: Шаг 2. Методом потенциалов ищется кратчайший путь L из Шаг 3. Если длина такого пути равна ∞, то перейти к шагу 9, в противном случае – к шагу 4. Шаг 4. На графе G(X,U) выбирается дуга (p,q), принадлежащая L, для которой справедливо:

Слайд 12

Описание слайда:

АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА (ПРОДОЛЖЕНИЕ) Шаг 5. На графе G(X,U) вес всех дуг, принадлежавших пути L, изменяется следующим образом: Шаг 6. Образовавшиеся дуги с нулевым весом на G(X,U) отбрасываются. Шаг 7. Вес r(p,q) добавить к ранее накопленной сумме S. Шаг 8. Перейти к шагу 1. Шаг 9. Конец алгоритма. Суммарный вес дуг, найденных на шаге 4 каждой итерации, равен максимальному потоку из источника в сток.

Слайд 13

Описание слайда:

ПРИМЕР 2 a) Граф G(X,U). b) Граф G’(X,U’), S=4. a) b) S=5. c) L=∞.

Слайд 14

Описание слайда:

САМОСТОЯТЕЛЬНО Сформулируйте достоинства приведенного выше алгоритма. Сформулируйте недостатки приведенного выше алгоритма.

Слайд 15

Описание слайда:

Пример 3

Слайд 16

Описание слайда:

САМОСТОЯТЕЛЬНО 1. Сформулировать достоинства и недостатки алгоритма поиска максимального потока. 2. Определить максимальный поток из источника в сток на графе G(X,U):

Слайд 17

Описание слайда:

МИНИМАЛЬНЫЕ РАЗРЕЗЫ НА ГРАФАХ Определения: 1. Разрезом на ориентированном графе G(X, U) называется подмножество дуг, удаление которых разрывает все пути из источника в сток. 2. Минимальным разрезом на взвешенном ориентированном графе G(X, U) называется разрез, суммарный вес дуг которого минимален. Варианты разрезов вверху выделены красным цветом

Слайд 18

Описание слайда:

Обозначения и определения Z(i,j) – булева переменная, равная единице, если дуга (i,j) принадлежит минимальному разрезу и равная нулю в противном случае. - множество дуг, принадлежащих d-у пути, ведущему из вершины-источника в вершину-сток .