| Заслуженный участник |
 |
05/09/05
515
Украина, Киев
|
Известно, что нахождение Гамильтонова цикла в общем случае есть NP полная задача.
С другой стороны, если что-то становится известным о виде графа, то алгоритмическая сложность подобной задачи может зачительно уменьшиться. Например, для ряда типов графов известна зависимость количества существующих Гамильтоновых циклов от количества вершин графа. Примером этому может послужить следующая таблица с MatWorld -
mathworld.wolfram.com/HamiltonianCircuit.html:
graph Sloane sequence
antiprism graph, A124353 X, X, 32, 58, 112, 220, 450, 938, 1982, 4220, 9022, 19332, ...
complete graph A124355 0, 0, 2, 6, 24, 120, 720, 5040, 40320, 362880, ...
cycle graph A007395 X, X, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
hypercube graph A003042 0, 2, 12, 2688, 1813091520, ...
Möbius ladder A124356 X, X, X, 12, 10, 16, 14, 20, 18, 24, 22, 28, 26, 32, 30, ...
prism graph A124349 X, X, 6, 12, 10, 16, 14, 20, 18, 24, 22, 28, 26, 32,...
wheel graph A005843 X, X, X, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, ...
Более того, если известно, что два различных вида графов порждают для всех n изоморфные графы, то очевидно, содержимое вышеприведенной таблицы для таких графов совпадает и графы имеют одинаковые Гамильтоновы циклы, с точностью до изоморфизма. В этом смысле элементы приведенной таблицы являются инвариантами для изоморфных графов. Обратное вообще говоря неверно. То есть, если два типа графов порождают одинаковые таблицы (то есть функционал граф с n вершинами -> количество Гамильтоновых циклов), ещё не означает, что мы имеем дело с изоморфными семействами графов.
Интересно знает ли кто-то из форумчан, что все таки ознаает по отношению к топологическим свойствам графа или к другому типу свойств этот факт, что количество Гамильтоновых циклов одинаковое для нескольких типов графа? Скажем так, по отношению к чему количество Гамильтоновых циклов семейства графов является инвариантом? Под семейством графов, я здесь понимаю, счетное множество графов, где каждый элемент соотвествует не более чем одному положительному натуральному n (количество вершин графа).
На самом деле, всё это присказка, а вопрос в том, знает ли кто, что такое теория Козырева-Гринберга (так она называется на MathWorld)? Там же есть теорема Гринберга... Хотя нет теоремы Козырева, но фамилия Козырева на первом месте в названии теории...
Гамильтоновы циклы, теория Козырева-Гринберга и теорема Гринберга ссылаются друг на друга (почти как сепульки, сепуление и сепулькарий ссылаются друг на друга в рассказе Станислава Лема). Но яснее не становится итак, может кто подскажет, буду благодарен:
Где можно (лучше в Интернете) подробней почитать про теорию Козырева-Гринберга?
Где можно почитать о нахождении Гамильтоновых путей для специальных типов графа?
Роль Гамильтоновых циклов, их количества по отношению к свойствам графа?
Создает ли понятие фундаментальной группы графа отношение эквивалентности на графе?
Последний вопрос скорее по незнанию, чем по необходимости и желанию 
|
|
