Проверка свойств графа
AnastasiyaRagozina opened this issue · 6 comments
Реалиизовать и визуализировать алгоритмы проверки
- эйлеровости графа
- гамильтоновости графа
- обязательно реализовать алгебраический метод.
Можете ли вы указать более подробное описание алгебраического метода нахождения гамильтонова цикла, в слайдах не очень понятно написано, а самостоятельно описание алгоритма я не нашел
https://www.google.ru/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=hamiltonian+path+algorithm+matrix
Вообще не совсем, в статье составляется система из E+2V+1 уравнений и решается с помощью базиса Гребнера и алгоритма Buchberger’s из пакета Maple.
Там еще написано, что можно посчитать определитель матрицы VxV и проверить слагаемые, являются ли они гамильтоновыми циклами. Не понятно, чем это лучше просто перебора, и там и там V! вариантов надо проверить.
Лучше оно потому, что матрицы известно как эффективно перемножать для больших графов.
Вообще, надо будет поэкспериментрировать с этим.