Любое ребро, дна концевая вершина которого лежит в Г ], а другая в Тг, цолжно ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Кристофайдс Н.N. Теория графов Алгоритмический подход


Любое ребро, дна концевая вершина которого лежит в Г ], а другая в Тг, цолжно принадлежать фундаментальному раареэу, так как добавление любого такого ребра к ребрам иэ Т и Тг приводит я обра-аованию другого остова графа G и, следовательно, любое множество, не содержащее таких ребер, не будет разрезом.

(cкачать страницу)

Смотреть книгу на libgen

Любое ребро, дна концевая вершина которого лежит в Г ], а другая в Тг, цолжно принадлежать фундаментальному раареэу, так как добавление любого такого ребра к ребрам иэ Т и Тг приводит я обра-аованию другого остова графа G и, следовательно, любое множество, не содержащее таких ребер, не будет разрезом.