Венгерский алгоритм: различия между версиями

Алгоритм хранит в памяти потенциал <math>y\ </math> и ориентацию (задание направления) каждого жёсткого ребра, обладающую тем свойством, что рёбра, направленные от <math>T\ </math> к <math>S\ </math> образуют паросочетание, которое мы обозначим <math>M\ </math>. Ориентированный граф, состоящий из жёстких рёбер с заданной ориентацией, мы обозначаем <math>\mathbf{\overrightarrow{G_y}}</math>. Таким образом, в любой момент есть три типа рёбер: