Стягивание. Под стягиванием мы подразумеваем операцию удаления ребра и отождествление его концевых вершин. Граф С является стягиваемым графом к графу , если Н можно получить из G последовательностью стягиваний.
Замыкание или отождествление. Говорят, что пара вершин v, и в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все ребра в графе G, инцидентные становятся инцидентными новой вершине.
Существует ли оптимальный алгоритм стягивания графа ? Ограничение на #вершин графа <= 20 , так что структура данных не важна . Однако , как я понял , матрица смежностей тут непригодна по простой причине - количество вершин становится меньше , и придется постоянно "играться" с памятью.
я пишу программу , которая на основании теоремы Понтрягина - Куратовского проверяет граф на планарность. Там нужно проверить все подграфы на гомеоморфность К5 и К3,3 , именно для этой задачи мне нужен алгоритм стягивания
