Ochilov Bunyod cal024 Variant №36

Ochilov Bunyod

CAL024

Variant № 36

1.Edmonds va Kards algoritmi.

2.Matritsadan eng katta elementni olish algoritmi, misol keltiring.

3.Qoldiq tarmoqlar xaqida tushuncha.

1

Kompyuter fanida Edmonds-Karp algoritmi bir vaqtning o'zida tarmoq oqimining maksimal oqimini hisoblash uchun Ford-Fulkerson usullarini amalga oshirishdir. Algoritm birinchi marta 1970 yilda Efim Dinits tomonidan e'lon qilingan va bir-biridan mustaqil ravishda 1972 yilda Djek Edmond va Richard Karp tomonidan nashr etilgan. Dinitz algoritmi ish vaqtini qisqartiradigan qo'shimcha usullarni o'z ichiga oladi. {\ Displaystyle (| V || E | ^ {2})} {\ Displaystyle O (| V | ^ {2} | E |)} haqida

Algoritm Ford-Fulkerson algoritmi bilan bir xil, faqat ko'paytirish yo'lini topishda qidirish tartibi aniqlanadi. Yo'lni imkoniyati bor eng qisqa yo'l bilan topish kerak. Buni kenglikdagi birinchi qidirish orqali topish mumkin, bu erda har bir qirraga 1 kilogramm miqdorini qo'llaymiz. Ishlash vaqtlari oshib boradi va har bir ortib boruvchi yo'l har safar kamida bitta qirrasi to'yingan paytda (maksimal mumkin bo'lgan oqimi bor), to'yingan qirradan manbagacha ko'payish yo'li bo'ylab masofani aniqlash kerakligini ko'rsatadi. oxirgi marta to'yinganidan kattaroq bo'ling va uzunligi endi yo'q. Ushbu algoritmning yana bir xususiyati shundaki, eng qisqa o'sish yo'lining uzunligi monoton ravishda oshadi. Algoritmlarga kirishda dalillar mavjud. {\ Displaystyle O (| V || E | ^ {2})} O (| E |) E | V |

algorithm EdmondsKarp

input:

graph (graph[v] should be the list of edges coming out of vertex v in the

original graph and their corresponding constructed reverse edges

which are used for push-back flow.

Each edge should have a capacity, flow, source and sink as parameters,

as well as a pointer to the reverse edge.)

s (Source vertex)

t (Sink vertex)

output:

flow (Value of maximum flow)

flow := 0 (Initialize flow to zero)

repeat

q := queue()

q.push(s)

pred := array(graph.length)

while not empty(q)

cur := q.pull()

for Edge e in graph[cur]

if pred[e.t] = null and e.t ≠ s and e.cap > e.flow

pred[e.t] := e

q.push(e.t)

if not (pred[t] = null)

df := ∞

for (e := pred[t]; e ≠ null; e := pred[e.s])

df := min(df, e.cap - e.flow)

(And update edges by that amount)

for (e := pred[t]; e ≠ null; e := pred[e.s])

e.flow := e.flow + df

e.rev.flow := e.rev.flow - df

flow := flow + df

until pred[t] = null (i.e., until no augmenting path was found)

return flow

2

public class Bunyod {