🗊Презентация Потоки в сетях

Категория: Математика
Нажмите для полного просмотра!
Потоки в сетях, слайд №1Потоки в сетях, слайд №2Потоки в сетях, слайд №3Потоки в сетях, слайд №4Потоки в сетях, слайд №5Потоки в сетях, слайд №6Потоки в сетях, слайд №7Потоки в сетях, слайд №8Потоки в сетях, слайд №9Потоки в сетях, слайд №10Потоки в сетях, слайд №11Потоки в сетях, слайд №12Потоки в сетях, слайд №13Потоки в сетях, слайд №14Потоки в сетях, слайд №15Потоки в сетях, слайд №16Потоки в сетях, слайд №17Потоки в сетях, слайд №18Потоки в сетях, слайд №19Потоки в сетях, слайд №20Потоки в сетях, слайд №21Потоки в сетях, слайд №22Потоки в сетях, слайд №23Потоки в сетях, слайд №24Потоки в сетях, слайд №25
Скачать

Содержание ▲

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

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

Слайд 1


ПОТОКИ В СЕТЯХ
Описание слайда:
ПОТОКИ В СЕТЯХ

Слайд 2


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

Слайд 3


Потоком в сети G = (Х,U) от входа s к выходу t называется неотрицательная функция U, определенная на множестве дуг сети со следующими свойствами: (10.4) (10.5)
Описание слайда:
Потоком в сети G = (Х,U) от входа s к выходу t называется неотрицательная функция U, определенная на множестве дуг сети со следующими свойствами: (10.4) (10.5)

Слайд 4


Условие (10.4) является уравнением сохранения потока, согласно которому поток, втекающий в вершину, равен потоку, вытекающему из нее, за исключением вершин s и t (источник и сток). Ограничение (10.5) указывает, что пропускные способности дуг ограничены для каждой дуги графа G. Задача состоит в нахождении такого множества потоков по дугам, чтобы (10.6) при ограничениях (10.4) и (10.5).
Описание слайда:
Условие (10.4) является уравнением сохранения потока, согласно которому поток, втекающий в вершину, равен потоку, вытекающему из нее, за исключением вершин s и t (источник и сток). Ограничение (10.5) указывает, что пропускные способности дуг ограничены для каждой дуги графа G. Задача состоит в нахождении такого множества потоков по дугам, чтобы (10.6) при ограничениях (10.4) и (10.5).

Слайд 5


Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Величина максимального потока из s в t равна значению минимального разреза отделяющего источник s от стока t. Разрез отделяет s от t, если ,а . Величиной такого разреза называется сумма пропускных способностей всех дуг из G, начальные вершины которых лежат в Хо, а конечные — в , т.е. (10.7)
Описание слайда:
Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Величина максимального потока из s в t равна значению минимального разреза отделяющего источник s от стока t. Разрез отделяет s от t, если ,а . Величиной такого разреза называется сумма пропускных способностей всех дуг из G, начальные вершины которых лежат в Хо, а конечные — в , т.е. (10.7)

Слайд 6


Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Минимальный разрез( ) — это разрез с наименьшим значением суммы пропускных способностей дуг. Если вершины неографа G = (X,U) разделены на два множества Хо и , где и является дополнением Хо относительно X, то множество ребер графа G, одни концевые вершины которых лежат в Хо, а другие — в Хо, определяют разрез этого неографа G. Обозначают разрезы в графах R = (Х0, ).
Описание слайда:
Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Минимальный разрез( ) — это разрез с наименьшим значением суммы пропускных способностей дуг. Если вершины неографа G = (X,U) разделены на два множества Хо и , где и является дополнением Хо относительно X, то множество ребер графа G, одни концевые вершины которых лежат в Хо, а другие — в Хо, определяют разрез этого неографа G. Обозначают разрезы в графах R = (Х0, ).

Слайд 7


Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Рис. 10.32 Разрез , состоящий из дуг орграфа определяется как объединение
Описание слайда:
Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Рис. 10.32 Разрез , состоящий из дуг орграфа определяется как объединение

Слайд 8


Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Разрезом орграфа G2 (рис. 10.33) является множество дуг U1 = (х5, х1), U2 = (x1, x4), U4 = (х3, х7) и U5 = (х2, х7), удаление которых разделяет множества вершин Хо = {х1,х2,х3} и ={х4,х5,х6,х7} (рис. 10.33). Рис. 10.33 Этот разрез образован множествами:
Описание слайда:
Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Разрезом орграфа G2 (рис. 10.33) является множество дуг U1 = (х5, х1), U2 = (x1, x4), U4 = (х3, х7) и U5 = (х2, х7), удаление которых разделяет множества вершин Хо = {х1,х2,х3} и ={х4,х5,х6,х7} (рис. 10.33). Рис. 10.33 Этот разрез образован множествами:

Слайд 9


Пример 10.2. Задача о максимальном потоке Построить максимальный поток для ориентированной сети с источником S и стоком t (рис. 10.34). Пропускные способности дуг указаны на дугах сети: Рис. 10.34
Описание слайда:
Пример 10.2. Задача о максимальном потоке Построить максимальный поток для ориентированной сети с источником S и стоком t (рис. 10.34). Пропускные способности дуг указаны на дугах сети: Рис. 10.34

Слайд 10


Пример 10.2. Задача о максимальном потоке Решение Составляем матрицу пропускных способностей дуг C = {cik} для графа G; нулевые значения пропускных способностей дуг в табл. 10.7 не записываем: (10.7)
Описание слайда:
Пример 10.2. Задача о максимальном потоке Решение Составляем матрицу пропускных способностей дуг C = {cik} для графа G; нулевые значения пропускных способностей дуг в табл. 10.7 не записываем: (10.7)

Слайд 11


Пример 10.2. Задача о максимальном потоке 2. Выбираем произвольно один из путей от вершины S к вершине t графа G (рис. 10.34). Пусть Р1 = {s, x1, x4, t} —первоначальный путь: Определяем пропускную способность выбранного пути Q1=min{10,5.13} = 5. В табл. 10.7 отмечаем чертой сверху значения пропускных способностей дуг, соответствующих указанному пути Р1. Вычитаем значение Q1 = 5 из отмеченных элементов (10, 5, 13). Нули, получаемые в результате вычислений, записываем в соответствующую строку или столбец.
Описание слайда:
Пример 10.2. Задача о максимальном потоке 2. Выбираем произвольно один из путей от вершины S к вершине t графа G (рис. 10.34). Пусть Р1 = {s, x1, x4, t} —первоначальный путь: Определяем пропускную способность выбранного пути Q1=min{10,5.13} = 5. В табл. 10.7 отмечаем чертой сверху значения пропускных способностей дуг, соответствующих указанному пути Р1. Вычитаем значение Q1 = 5 из отмеченных элементов (10, 5, 13). Нули, получаемые в результате вычислений, записываем в соответствующую строку или столбец.

Слайд 12


Пример 10.2. Задача о максимальном потоке (10.8) (10.8) 3. Выбираем следующий путь из S в t, т.е. Р2 = {s, x4, t} и определяем его пропускную способность: Q2 = min{4;8} = 4. В табл. 10.8 отмечаем значения пропускных способностей чертой над числами 4 и 8. Вычитаем значение Q2 = 4 из указанных элементов. Получаем новую табл. 10.9:
Описание слайда:
Пример 10.2. Задача о максимальном потоке (10.8) (10.8) 3. Выбираем следующий путь из S в t, т.е. Р2 = {s, x4, t} и определяем его пропускную способность: Q2 = min{4;8} = 4. В табл. 10.8 отмечаем значения пропускных способностей чертой над числами 4 и 8. Вычитаем значение Q2 = 4 из указанных элементов. Получаем новую табл. 10.9:

Слайд 13


Пример 10.2. Задача о максимальном потоке (10.9) 4. Выбираем новый путь из S в t, т.е. (10.10)
Описание слайда:
Пример 10.2. Задача о максимальном потоке (10.9) 4. Выбираем новый путь из S в t, т.е. (10.10)

Слайд 14


Пример 10.2. Задача о максимальном потоке Р3 = {s, x1, x3, x4, t} и определяем его минимальную пропускную способность: Q3=min{5,9,7,4} = 4. Вычитаем значение Q3 = 4 из элементов, отмеченных в табл. 10.9. Получаем табл. 10.10 в виде: 5. Выбираем путь Р4 = {s,x3, t} и определяем его пропускную способность: Q4=min{14,2} = 2. Вычитая Q4 = 2 из значений пропускаемых способностей (14,2), получаем табл. 10.11:
Описание слайда:
Пример 10.2. Задача о максимальном потоке Р3 = {s, x1, x3, x4, t} и определяем его минимальную пропускную способность: Q3=min{5,9,7,4} = 4. Вычитаем значение Q3 = 4 из элементов, отмеченных в табл. 10.9. Получаем табл. 10.10 в виде: 5. Выбираем путь Р4 = {s,x3, t} и определяем его пропускную способность: Q4=min{14,2} = 2. Вычитая Q4 = 2 из значений пропускаемых способностей (14,2), получаем табл. 10.11:

Слайд 15


Пример 10.2. Задача о максимальном потоке (10.11) 6. Укажем путь Р5 = {s, x2, t} и определим его пропускную способность: Q5 = min{3;3} =3. Вычитая Q5 из элементов пропускных способностей дуг рассматриваемого пути получаем таб. 10.11 в виде 10.12:
Описание слайда:
Пример 10.2. Задача о максимальном потоке (10.11) 6. Укажем путь Р5 = {s, x2, t} и определим его пропускную способность: Q5 = min{3;3} =3. Вычитая Q5 из элементов пропускных способностей дуг рассматриваемого пути получаем таб. 10.11 в виде 10.12:

Слайд 16


Пример 10.2. Задача о максимальном потоке (10.12) В столбце t имеются только нули. Следовательно, простроить новый путь невозможно. Вычитая из элементов табл. 10.1) значения пропускных способностей дуг, указанных в табл. 10.12, получаем таблицу со значениями Cjk, определяющими максимального возможный поток. Его величина равна П = Ql + Q2 + Q3 + Q4 + Q5; П = 5 + 4 + 4 + 2 + 3 = 18.
Описание слайда:
Пример 10.2. Задача о максимальном потоке (10.12) В столбце t имеются только нули. Следовательно, простроить новый путь невозможно. Вычитая из элементов табл. 10.1) значения пропускных способностей дуг, указанных в табл. 10.12, получаем таблицу со значениями Cjk, определяющими максимального возможный поток. Его величина равна П = Ql + Q2 + Q3 + Q4 + Q5; П = 5 + 4 + 4 + 2 + 3 = 18.

Слайд 17


Пример 10.2. Задача о максимальном потоке Построим итоговую матрицу: С6 = С - С5. (10.13) На основании итоговой матрицы строим максимальный поток сети:
Описание слайда:
Пример 10.2. Задача о максимальном потоке Построим итоговую матрицу: С6 = С - С5. (10.13) На основании итоговой матрицы строим максимальный поток сети:

Слайд 18


Пример 10.2. Задача о максимальном потоке Рис. 10.35 Построенный граф G удовлетворяют условию потока, т.е. соблюдается равновесие вершин (величина входящего и выходящего потоков равны). Величина минимального разреза дуг равна R = 18. Рассмотрим другой способ решения задачи, используя алгоритм построения максимального потока в сети методом увеличения потока вдоль пути, который состоит в следующем: Выбор начального потока. Обычно выбирают нулевое начальное значение потока. Построение увеличивающего пути от источника s к стоку t
Описание слайда:
Пример 10.2. Задача о максимальном потоке Рис. 10.35 Построенный граф G удовлетворяют условию потока, т.е. соблюдается равновесие вершин (величина входящего и выходящего потоков равны). Величина минимального разреза дуг равна R = 18. Рассмотрим другой способ решения задачи, используя алгоритм построения максимального потока в сети методом увеличения потока вдоль пути, который состоит в следующем: Выбор начального потока. Обычно выбирают нулевое начальное значение потока. Построение увеличивающего пути от источника s к стоку t

Слайд 19


Пример 10.2. Задача о максимальном потоке 3. Увеличение потока вдоль построенного пути на максимально возможную величину, полагая увеличение потока по увеличивающей дуге и уменьшение его по уменьшающей дуге. Увеличивающей дугой называется дуга, направление которой совпадает с направлением потока и величина потока по этой дуге меньше ее пропускной способности, т.е.
Описание слайда:
Пример 10.2. Задача о максимальном потоке 3. Увеличение потока вдоль построенного пути на максимально возможную величину, полагая увеличение потока по увеличивающей дуге и уменьшение его по уменьшающей дуге. Увеличивающей дугой называется дуга, направление которой совпадает с направлением потока и величина потока по этой дуге меньше ее пропускной способности, т.е.

Слайд 20


Пример 10.2. Задача о максимальном потоке Уменьшающей дугой называется дуга, направление которой противоположное направлению потока, а величина потока отлична от нуля: Уменьшающие и увеличивающие дуги называют допустимыми. Увеличивающим путем называется элементарный путь, все дуги которого являются допустимыми. Рассмотрим пример 10.2. Определить максимальный поток для сети (рис. 10.34).
Описание слайда:
Пример 10.2. Задача о максимальном потоке Уменьшающей дугой называется дуга, направление которой противоположное направлению потока, а величина потока отлична от нуля: Уменьшающие и увеличивающие дуги называют допустимыми. Увеличивающим путем называется элементарный путь, все дуги которого являются допустимыми. Рассмотрим пример 10.2. Определить максимальный поток для сети (рис. 10.34).

Слайд 21


Пример 10.2. Задача о максимальном потоке Рассмотрим пример 10.2. Определить максимальный поток для сети (рис. 10.34). Рис. 10.34
Описание слайда:
Пример 10.2. Задача о максимальном потоке Рассмотрим пример 10.2. Определить максимальный поток для сети (рис. 10.34). Рис. 10.34

Слайд 22


Пример 10.2. Задача о максимальном потоке Решение. Начальное значение потока полагаем равным нулю Vo = 0. Построим увеличивающие пути от S к стоку t: Pl = {s, x1, x4, t}, φ1 = min (10; 5; 13) = 5. Запишем значение φ1 = 5 в скобках на соответствующих дугах рассматриваемого пути. Для пути (рис. 10.36)
Описание слайда:
Пример 10.2. Задача о максимальном потоке Решение. Начальное значение потока полагаем равным нулю Vo = 0. Построим увеличивающие пути от S к стоку t: Pl = {s, x1, x4, t}, φ1 = min (10; 5; 13) = 5. Запишем значение φ1 = 5 в скобках на соответствующих дугах рассматриваемого пути. Для пути (рис. 10.36)

Слайд 23


Пример 10.2. Задача о максимальном потоке
Описание слайда:
Пример 10.2. Задача о максимальном потоке

Слайд 24


Пример 10.2. Задача о максимальном потоке Р2 = {s, х4, t}, φ2 = min (4; 13-5) = 4. Отметим на дугах пути Р2 величину φ2 = 4. Для пути Р3 = {s,x1, x3, x4, t}, φ3 = min (10-5; 9; 7; 13-9) = 4. Запишем величину φ3 = 4 на дугах пути Р3. Аналогично запишем пути Рi на дугах которых отметим соответствующие величины φi: Р4 = {s, х3, t}, φ4 = min (14; 2) = 2; P5 = {s, x2, t}, φ5 = min (6; 3) = 3.
Описание слайда:
Пример 10.2. Задача о максимальном потоке Р2 = {s, х4, t}, φ2 = min (4; 13-5) = 4. Отметим на дугах пути Р2 величину φ2 = 4. Для пути Р3 = {s,x1, x3, x4, t}, φ3 = min (10-5; 9; 7; 13-9) = 4. Запишем величину φ3 = 4 на дугах пути Р3. Аналогично запишем пути Рi на дугах которых отметим соответствующие величины φi: Р4 = {s, х3, t}, φ4 = min (14; 2) = 2; P5 = {s, x2, t}, φ5 = min (6; 3) = 3.

Слайд 25


Пример 10.2. Задача о максимальном потоке Увеличивающих путей больше нет. Построим максимальный поток Пmах заданной сети (Рис.10.36) Величина максимального потока равна сумме минимальных значений φi, i = 1,2,3,4,5 Пmах = 5 + 4 + 4 + 2 + 3 = 18. Значение минимального разреза Rmin = 18. Ответ: Пmах= Rmin = 18.
Описание слайда:
Пример 10.2. Задача о максимальном потоке Увеличивающих путей больше нет. Построим максимальный поток Пmах заданной сети (Рис.10.36) Величина максимального потока равна сумме минимальных значений φi, i = 1,2,3,4,5 Пmах = 5 + 4 + 4 + 2 + 3 = 18. Значение минимального разреза Rmin = 18. Ответ: Пmах= Rmin = 18.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию