Рассмотрим график G, который является DAG. Докажите, что в графе G ', который получается путем реверсирования всех ребер G, источник (s)/sink (s) в G стал бы потоком (s)/источником (s) соответственно.Источник и раковина в DAG
Я вижу это четко, но я не могу дать официальное доказательство этого. Выручи меня. : ')
К definition вершина с индексом 0 называется источником и вершиной с выдержкой 0 называется раковина.
Реверсивные ребра, не зависящие от нормы, имеют разную площадь для каждой вершины. Это означает, что если вершина v в G имеет не зависящую от d1 и не превосходящую d2, то v в G 'имеет не зависящий d2 и outdegree d1.
Vertex v источник в G < => v имеет неопределенность 0 в G < => v имеет предел 0 в G '< => v находится в G'.