Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.

Пусть дан граф Gс множ (N,U)-связный. Каждому ребру поставлено в согласовании неотрицательное число cij, которое именуется весом ребра. Графы такового типа именуются взвешаными сетями.

Нужно отыскать малое по весу остовное дерево.В этом случае под весом понимают сумму весов его рёбер.

Аксиома. Пусть G(N,U)-связный взвешаный Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. граф, взвешаны рёбра с матрицей весов cij. D1(N1,U1),D2(N2,U2),…,Dk(Nk,Uk)-остовный лес.

N=∪Ni Ni≠Æ Ni∩Nj=Æ i≠j

(p,l)-ребро начального графа такое, что pЄN1, l∉N1. Посреди схожих рёбер (p,l) имеет малый вес. Тогда посреди всех остовных деревьев D, включавших {Di Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.} в качестве остовного леса, найдётся дерево малого веса, содержащее ребро (p,l).

Подтверждение. Представим неприятное: описаное в аксиоме остовное дерево Т не содержит ребро (p,l). Добавим в дерево Т ребро (p,l). При всем этом новый граф Т’ имеет в точности 1 цикл с ребром (p,l Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.). В этом цикле непременно найдётся ребро (α,β) такое, что αЄD1, β∉D1. Вероятны 2 варианта:

1.Вес ребра (p,l) совпадает с весом ребра (α,β). В данном случае выбрасываем ребро (α,β) тогда и новый граф Т’’ совпадает с деревом, описанным в условии аксиомы.

2. Если ребро (α,β)> веса ребра (p,l). Cα,β>cp,l. Тогда начальное дерево Т Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. не является наименьшим по весу. Противоречие получено. Аксиома подтверждена.

Метод Краскала-алгоритм решения задачки по наименьшим остовных деревьев.

1.Посреди все рёбер графа G находим ребро малого веса, удаляем его из графа и заносим его в строящееся остовное дерево.

2.Если в строющемся дереве n-1 вершин, где n-колич вершин остовного дерева, то Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. среднее ребро выстроено. Конец работы метода. По другому перебегаем на шаг 3.

3. Посреди всех рёбер графа G таких, что добавление хоть какого из их в строющееся дерево не приводит к возникновению цикла. Избираем ребро малого веса. Удаляем его из цикла и заносим его в дерево. Перебегаем на шаг 2.

Метод Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. Прима.

1.Избираем произвольную верхушку i. Посреди всех рёбер, инцидентных этой верхушке, выбирается ребро малого веса, удаляется из графа и заносится в остовное дерево.

2. Если в дереве n-1 ребро, где n-количество вершин начального графа, то наилучшее дерево выстроено. Конец работы метода. По другому перебегаем на шаг 3.

3.Посреди всех Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. рёбер графа G, таких, что в каждой из их инцидентна в точности одной верхушке, вошедшей в строющееся дерево находим ребро малого веса, удаляем его из графа и заносим его в строющееся дерево. Перебегаем на шаг 2.

39. Задачка о наивысшем потоке и наименьшем разрезе. Метод Форда-Фалкерсона.

Задан вершинный орграф G=(N Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.,U). Взвешены дуги. Дуге (I,j) приписано неотрицательно число ci≥0, которое именуется пропускной способностью дуги. Граф, лежащий в базе орграфа G-связный.

Выделены 2 верхушки s и t. S-источник, t-сток. Такие орграфы-сети.

Потоком по сети G именуется огромное количество чисел xij таких, что:

1.0≤xij≤cij

2.Закон сохранения потока Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. в верхушке: ∀k≠s,t производится, что суммарный поток втекающей верхушки равен суммарному сгустку вытекающему из неё.

3.Закон сохранения потока в сети:поток, втекающий в сеть через верхушку s=сгустку вытекающему из сети через верхушку t.

Задачка заключается в том, что нужно максимилизировать величину потока из сети при ограничении 1,3.

Мысль Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. решения задачки о макс потоке последующая:поочередно отыскивать различные пути из s в t и для каждого такового пути макс поток вычислять.

Задачка о мини разрезе. Пусть У⊆Nи пусть SЭУ и t∉У.

Разрезом сети G(Y,Y) назыв множ таких рёбер (i,j) таких, что {iЄY, jЄY Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.} либо напротив: {iЄY, jЄY}

Пропускной способностью разреза назыв величина с (У,У)=∑сij

(i,j)Є(Y,Y)

Задачка о мин разрезе формулируется след образом: с(У,У) минилизировать -> min(Y,Y). Мин ищется по различным разрезам, выделяющие источник по стокам.

Метод Форда-Фолкерсона.

I шаг. Избираем некий Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. исходный поток. В качестве такового потока можно взять xij=0.Верхушка S получает метку(S,∞). Это означает, что мы пытаемся запихнуть в сеть нескончаемый по величине макс поток. Верхушка S при всем этом считается помеченной, но не просмотренной. Все другие верхушки не помечены.

II шаг. Избираем произвольную помеченную и не Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. просмотренную верхушку и пытаемся пометить из неё все смежные с ней верхушки. Представим, избранная верхушка k и пытаемся пометить смежну к ней верхушку i. Вероятны 2 варианта:

1.в начальном графе имеется дуга (k,i)

2.в начальном графе имеется дуга (i,k)

Разглядим 1-ый случай. Имеем 2 варианта:

1.Если cki>xki, то Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. по дуге (k,i) ток можно прирастить на величину ε^+(i)=min{cki-xki,ε(k)}

2.Если сki=xki, то дуга в данном случае дуга назыв насыщенной верхушку i пометить из верхушки k нельзя и поток по этой дуге прирастить нельзя. Разглядим II случай. Тут также 2 варианта:

1.xik>0, то поток по дуге Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. (i,k) можно уменьшить на величину ε^(-)(i)=min(xik,ε(k)). При всем этом, вообщем говоря, поток по сети возрастает.

2.Если xik=0, то верхушку i из верхушки k пометить нельзя. Независимо от того, удалось ли пометить все смежные с k верхушки, верхушка к считается помеченной и просмотренной. Процедура расстановки пометки длится Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. до того времени, пока не будет помечена верхушка Е. Если верхушку Е удаётся пометить, то перебегаем на след шаг. В неприятном случае текущий поток является макс и при всем этом определяется мин разрез.

III шаг. Начиная из верхушки t, по меткам определяем путь из s в t. Пусть Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. верхушка t имеет метку M(t)=(in,ε^+(t)), верхушка M(in)=(in-1,…), M(in-1)=(in-2,…) и тем будет определён полупуть (S=i1,i2,…,in,t), дуговые потоки для этого полупути изменяем на величину ε(t). В случае ориентации дуги из s в t, воток по дуге увеличиваем на величина ε(t), в Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. случае обратного-уменьшаем на величину ε(t). После чего все метки, кроме метки верхушки s, вытираются, все верхушки, не считая верхушки s числятся непомеченными, а верхушка s помеченной и не просмотренной. Возвращаемся на II шаг.

40. Аксиома Форда-Фалкерсона

Аксиома Форда-Фалкерсона.Величина макс потока в сети=пропускной возможности мин разреза Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала., отделяющего источник от стока.

Следствие. Решая задачку о макс потоке, мы решаем задачку о мин разрезе и напротив.

При решении этой пары задач, употребляется система меток: помечаются верхушки, метка верхушки i(M(i)) состоит из 2-ух частей:(M(i)=(k,ε^ (i))), k-указывает: из какой верхушки была помечена верхушка Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. i, если ε^+(i), то это показывает, что по дуге (k,i) можно прирастить поток на величину ε(i), если ε^-(i)-уменьшить поток на величину ε(i). В процессе работы метода, любая из вершин может находиться в одном из трёх состояний:

1.Верхушка не помечена

2.верхушка помечена и не просмотрена

3.верхушка помечена и Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала. просмотрена


zadachi-centrov-ili-pitomnikov-pitomniki-reshayut-neskolko-zadach.html
zadachi-chempionata-viyavlenie-silnejshej-lyubitelskoj-komandi-propaganda-zdorovogo-obraza-zhizni-povishenie-sportivnogo-masterstva-uchastnikov-turnira.html
zadachi-dat-roditelyam-ocenku-aktualnogo-sostoyaniya-rebenka-sprognozirovat-vozmozhnie-problemi-obucheniya-i-razvitiya-sposobstvovat-razvitiyu-otnoshenij-partnerstva-i-sotrudnichestva-s-detmi.html