Максимальный поток сети для нестандартного графа

[UserCity11]

Здравствуйте!
Получил задание найти максимальный поток сети. Однако граф мне показался странным: от стока t отходит ребро.
Подскажите, такое возможно в данной задаче? В учебнике пишут, что в сток по определению все ребра входят.
Может быть сток выше расположен? Самая верхняя вершина справа?
Спросить у преподователя нет возможности.
Очень прошу помочь.

[svv]

Да, такого не должно быть.
Но вот как это исправить — однозначно сказать нельзя. Может быть, считать стоком правую верхнюю вершину. А может быть, повернуть стрелочку в самом правом ребре, с единичкой, вниз. Это два самых правдоподобных варианта.

[Nemiroff]

Ну а в чём проблема. Найдите поток по тому, как нарисовано. Вам эти ребра никак не помогут и не помешают.

[Евгений Машеров]

Nemiroff в сообщении #1536675 писал(а):

Ну а в чём проблема. Найдите поток по тому, как нарисовано. Вам эти ребра никак не помогут и не помешают.

Если сток нарисован там, где надо, и стрелки правильные - то да, вершина, куда ведёт стрелка из стока, ни на что не повлияет. Но очень похоже, что есть ошибка, и неясно какая. Если сток на месте, а перепутано направление стрелки, то максимальный поток вырастет на единицу. А если все стрелки верные, а истинный сток - вершина выше той, которая помечена t, то максимальный сток будет на 2 меньше.
Так что лучше уточнить, ну, или делать все три варианта. Но если это "работа на заказ" - заказчик вряд ли поблагодарит за необходимость представлять три расчёта и, главное, объяснять, зачем он это сделал...

[svv]

Думаю, ответ Nemiroff самый юридически правильный: если из-за головотяпства парня, который рисовал граф, три ребра получились мёртвыми — это его проблемы.

[Евгений Машеров]

(Оффтоп)

(держа в руке кепку): "Фогмально пгавильно, а по существу издевательство!"