Лекция №14. Графы: кратчайшие пути и максимальные потоки. Предмет "Структуры и алгоритмы обработки данных"

  • Published on
    07-Jul-2015

  • View
    6.604

  • Download
    2

Embed Size (px)

Transcript

<ul><li> 1. . .. : : . , www.grebenshikov.ru </li></ul> <p> 2. 1 3. G = (V, E) w : E R. p = v0, v1, . . . , vk k . w(p) = w(vi1, vi)i=1 u v - : p min w(p) : u v , u v (u, v) = , u v - p, w(p) = (u, v)2 4. 3 5. p = v1, v2, . . . , vk - v1 vk G = (V, E) w : E R, pij =vi, vi+1, . . . , vj - p, vi vj i j (1 i j k). pij - vi vi.4 6. 5 7. () 6 8. : (Dijkstra) 7 9. 8 10. T (G) = (V ) + (V logV ) + (V (logV + deg()logV )) = ((V + E)logV )9 11. - - 10 12. : - (k) dij - i j, - {1, 2, . . . , k} 11 13. - (0) dij = wij (k)(k) (k1)(k1) dij = min(dij , dik + dkj), k 1 : d(n) 12 14. -13 15. : -T (G) =? 14 16. 15 17. - , - c(u, v) &gt; 0 - s t. (u, v) E c(u, v) =/ 0. - f : V V R, : f (u, v) c(u, v) : f (u, v) = f (v, u) : u V s, t f (u, v) = 0 vV16 18. 17 19. f |f | = sumvV f (s, v) : - , - .18 20. - FordFulkersonMethod(G, s, t) 1 f 0 2 while p 3do f p 4 return f19 21. :cf (u, v) = c(u, v) f (u, v) Gf (V, Ef ), Ef = (u, v) V V : cf (u, v) &gt; 020 22. 21 23. G = (V, E) f - p s t Gf : cf (p) = min cf (u, v) : (u, v) p :cf (p),(u, v) p, fp(u, v) =cf (p), (v, u) p,0, 22 24. - V = S T, s S, t T - c(S, T ) = 12 + 14 = 26 - f (S, T ) = 12 + (4) + 11 = 19 23 25. - . : f - G Gf . |f | = c(S, T ) (S, T ) G.24 26. - 25 27. - 26 28. - 27 29. -T (G) = (E) + O(Ef ) = O(Ef ) 28 30. -T (G) = (E) + (E|f |) = (E|f |) :29 31. - 30 32. David M. Mount, The Lecture notes: Design and Analysisof Computer Algorithms. [ ] / Dept. ofComputer Science, University of Maryland, 2004. - : http://www.cs.umd.edu/ mount/451/Lects/451lects.pdf. - .49-55, 118-125 ., ., ., . -: , 2- . - . : - , 2007. .663-794. 31 </p>

Recommended

View more >