максимальный поток в графиках

Question

Основные определения:

Ограничение емкости: Для всех u, v V нам требуется f (u, v) <= c (u, v). </p>

Косая симметрия: Для всех u, v V нам требуется âf (u, v) = -f (v, u).

Сохранение потока: Длявсе u принадлежит V - {s, t}, нам требуется ((сумма (v принадлежит V)) f (u, v)) = 0

Пусть f1 и f2 - потоки в сети потоковG = (V, E).Сумма f1 + f2 определяется как (f1 + f2) (u, v) = f1 (u, v) + f2 (u, v) для всех (u, v), принадлежащих V. Из трех свойств потока следующиеудовлетворяются f1 + f2.

Ограничение емкости: может явно нарушаться.

Косая симметрия: Имеем: (f1 + f2) (u, v) = f1 (u, v)+ f2 (u, v) = -f1 (v, u) - f2 (v, u) = - (f1 (v, u) + f2 (v, u)) = - (f1 + f2) (v, u)

Мои вопросы ниже

1. Как нарушается ограничение производительности выше?

2. Что такое сохранение потока?и почему сумма сохранения потока равна нулю для вершин, не включая источник и бак в и?Просьба помочь с простым примером.

Спасибо!

Answer 1

1. пропускная способность действительно нарушена.посмотрите на следующий пример: f1(u,v) = f2(u,v) = c(u,v) > 0.Ограничение сохраняется для каждого f1, f2, поскольку они оба не больше c.Тем не менее, посмотрите на f1+f2: f1+f2(u,v) = f1(u,v) + f2(u,v) = 2*c(u,v), и поскольку для этого примера c(u,v) > 0, ясно f1+f2(u,v) > c(u,v), поэтому ограничение емкости не сохраняется.

2. сохранение потока в основном: для каждой вершины, кроме s, t: одинаковое количество потока входит в вершину и покидает вершину.Таким образом, каждый v в V \ {s, t} не «создает» какой-либо поток и не потребляет никакого потока: только s, t могут это делать.