Как связаны задачи Гамильтонов путь, и Обладает ли матрица связностью единиц.
Иными словами, можно ли представить задачу Гамильтонов путь в виде матрицы (возможно матрицы смежности)??
Идеальным было бы условие, что если в графе есть гамильтонов путь, то матрица обладает свойством связности единиц. (возможно необходимо ограничить степень каждой вершины тремя, т.е. брать кубический граф...)

p.s. Вообще нужно свести задачу Гамильтонов путь (почему-то в кубическом графе) к Задаче Разбиение на подматрицы со свойством связности (Дана (0,1) матрица M x N, нужно определить, обладает ли она свойством связности единиц?(т.е. существует такая перестановка столбцов, что в каждой строке единицы идут подряд)).
Если использовать метод сужения, то если положить n=m=m1, и А - матрица смежности некоего графа... Но дальше все упирается в Гамильтонов путь...

Ну, положим, причем тут кубический граф - понятно. Речь, очевидно, идет о NP-полноте. Так вот, задача "Гамильтонов путь" - NP-полная. Более того, она NP-полна даже на подмножестве кубических графов (к такой задаче сводится другая NP-полная задача о выполнимости формул. Все это есть в замечательной книжке "с ослом от Гойя": Кормен, Лейзерсон, Ривест. Алгоритмы. Построение и анализ). С другой стороны, если Вы сведете задачу "Гамильтонов путь" к задаче связности единиц в некой матрице, то получите и её NP-полноту. Отмечу лишь, что речь идет не просто о проверке можно/нельзя, а о минимизации количества "блоков единиц" (что то такое). Содержательные ссылки можно найти с помощью Google.