29.Орграфы, турниры. Предки и потомки вершин. Алгоритм Фалкерсона разбиения орграфа на слои.

Орграфом  D  называется пара (V(D), A(D)), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D)  — конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами ). Дуга, у которой вершина υ является первым элементом, а вершина ω — вторым, называется дугой из υ в ω (υ, ω) (дуги (υ, ω) и (ω,υ) различны). Хотя графы и орграфы — различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги.  V(D) и A(D) называются соответственно множеством вершин и семейством дуг орграфа D.

Турниром называется орграф, в котором любые две вершины соединены ровно одной дугой.

Алгоритм Форда–Фалкерсона решает зад. нахождения макс. потока в транспортной сети.

Идея алгоритма закл. в след.. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех u, υ € V. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.