Гамильтонов путь и связность единиц

[positron]

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

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