2.3. Инкрементальные графы

Процесс нахождения в графе аугментальной цепи потока, когда поток по дугам задается вектором можно рассматривать как процесс нахождения цепи (от в инкрементальном, графе определяемом следующим образом:

где

причем пропускная способность дуги равна и

причем пропускная способность дуги равна

Процедура расстановки пометок в алгоритме, описанном в разд. 2.1, является теперь не чем иным, как методом построения

Рис. 11.3. (см. скан) (а) Граф потоки которого подчеркнуты, (б) Инкрементальный граф

достижимого множества в инкрементальном графе Если т. е. если вершина получила пометку, то в графе найдена цепь от Аугментальная цепь в графе является теперь цепью где дуги из в являются прямыми дугами, а дуги из в являются обратными дугами.

На рис. дан пример вектора в графе, где подчеркнутые числа задают потоки, а другие числа у дуг задают пропускные способности. На рис. изображен соответствующий инкрементальный граф