Знаете ли вы алгоритм стягивания графа?

Question

[Ladence]

Стягивание. Под стягиванием мы подразумеваем операцию удаления ребра и отождествление его концевых вершин. Граф С является стягиваемым графом к графу , если Н можно получить из G последовательностью стягиваний.

Замыкание или отождествление. Говорят, что пара вершин v, и в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все ребра в графе G, инцидентные становятся инцидентными новой вершине.

Существует ли оптимальный алгоритм стягивания графа ? Ограничение на #вершин графа <= 20 , так что структура данных не важна . Однако , как я понял , матрица смежностей тут непригодна по простой причине - количество вершин становится меньше , и придется постоянно "играться" с памятью.

Answer 1

[exenza]

Вы смотрели на алгоритм поиска минимального разреза Каргера, он основан на стягивании. Какая у вас задача? Хотите скукожить граф до 20 вершин?

Comments

[Ladence]

я пишу программу , которая на основании теоремы Понтрягина - Куратовского проверяет граф на планарность. Там нужно проверить все подграфы на гомеоморфность К5 и К3,3 , именно для этой задачи мне нужен алгоритм стягивания

[Ladence]

exenza и я не понял вопроса : "Хотите скукожить граф до 20 вершин?" . Ограничение на количество вершин входного графа <= 20.