Где мы ишем факт того, что отстутвует другой путь из 4 в 5.

Т.е. не существует маршрута, например, 4 -> 3 -> 8 -> 5 ?

Понятно, что ноду только с одной входящей связью всегда можно схлопнуть с предыдущей.

Но тогда задача какая-то черезчур простая.

Что в ситуации, когда в нодах больше одной входящей связи но они относятся к непересекающимся-несвязанным подграфам (с терминологией у меня все плохо). Я так подумал, что их тоже нужно схлопывать.

ладно, пофиг, т.з. конечно замечательное " рёбра типа (4)->(5) как на картинке." )))

в любом случае, смысл сего действия мне не очень понятен

тогда вообще не понятна проблема

схлопываем все ноды, у которых только один входящий маршрут

сам алгоритм схлопывания вроде тревиальный, что тут обсуждать - не понятно

а так же 2 и 7

т.к. лично я бы подумал, что кольцо должно схлопнутся в 1-н элемент. Почему оно не должно схлопываться, мне не понятно

в 7-ом, я бы подумал, что элементы 7->4 7->6 так же должны схлопнутся (см. картинку N1)

В общем, правила схлопывания мне совершенно не понятны. А предметную область я не знаю.

Задача еще никуда не сдвинулась.

То майтон какие-то заумные задачи с формулировками и терминами из теор-мата, теор-вероятностей и пр. публикует. что я даже таких слов в жизни не слышал.
То "типа как на картинке." )))