Немного переформулируем задачу: у нас есть потоковый граф G с целочисленными пропускными способностями. Можем ли мы найти максимальный поток, в котором хотя бы для одного из ребер e значение f(e) равно нецелому числу?
В первый раз, когда я попробовал это, я как бы приукрасил это и подумал, что это нарушает теорему целостности и, следовательно, что это неверно, но после внимательного прочтения становится ясно, что это не нарушает никаких правил. Видимо это правда.
Я пытался нарисовать простой пример, чтобы получить визуализацию, но ничего не могу придумать. Может ли кто-нибудь показать мне пример графа потока, где это работает?