Выдержка из книги
Евстигнеев В.А.
Применение теории графов в программировании
Граф сводим по Хехту и Ульману тогда и только тогда, когда он имеет единственный носитель. Предположим, что граф сводим, но его носитель не единствен. He имеет места ни одно из включений Е, Е2 и ЕгаЕ1 в силу максимальности носителя. Таким образом, Ег - Et не пусто. Она не можег быть прямой дугой, так как все прямые дуги входят в EI, и не может быть поперечной по той же причине; следовательно, ( v, w) - обратная дуга. Так как в D2 существует путь ц из s в v, то вместе с дугой ( v, w) образует контур, что невозможно. Кроме того, путь ц не содержит в ершины w, иначе также был бы контур. Значит, Ег - EI пусто, а отсюда следует единственность носителя для сводимого графа. Докажем, что его носитель не единствен. Из леммы 22 следует, что G содержит по крайней мере одну конструкцию вида, показанного на рис. 2.28. Обозначим эту конструкцию через, а через V, W, X, Y, Z - соответственно множества дуг путей из s в а, пз а в Ь, из а в с, из Ъ в с и из с в Ь в какой-нибудь конструкции JF. Эти пять множеств не пересекаются, а V может быть пусто.
