Методы построения гамильтоновых циклов в графе

Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G гамильтонов цикл. Критерии существования, данные выше, представляют теоретический интерес, но являются слишком общими и не пригодны для произвольных графов, встречающихся на практике. Алгебраические методы определения гамильтоновых циклов не могут быть применены с более чем несколькими десятками вершин, так как они требуют слишком большого времени работы и большой памяти компьютера. Более приемлемым является способ Робертса и Флореса, который не предъявляет чрезмерных требований к памяти компьютера, но время, в котором зависит экспоненциально от числа вершин в графе. Однако другой неявный метод перебора имеет для большинства типов графов очень небольшой показатель роста времени вычислений в зависимости от числа вершин. Он может быть использован для нахождения гамильтоновых циклов в очень больших графах.

 

Алгебраический метод построения гамильтоновых циклов

Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин» цепи x₁, x₂, …,x_k-1, x_k определяется как выражение вида x₂*x₃* …x_k-1, не содержащее две концевые вершины x₁ и x_k. «Модифицированная матрица смежности» B=[β(i,j)] — это (n×n)- матрица, в которой β(i,j) — x_j, если существует дуга из x_i в x_j и нуль в противном случае. Предположим теперь, что у нас есть матрица P_L = [p_L(i,j)], где p_L(i,j) — сумма внутренних произведений всех простых цепей длины L (L≥1) между вершинами x_i и x_j для x_i≠x_j. Положим p_L(i,i)=0 для всех i. Обычное алгебраическое произведение матриц определяется как

B*P_L=P’_L+1=[p’_L+1(s,t)]

т.е. p’_L+1(s,t) является суммой внутренних произведений всех цепей из x_s в x_t длины l+1. Так как все цепи из x_k в x_t, представленные внутренними произведениями из p_L(k,t), являются простыми, то среди цепей, получающихся из указанного выражения, не являются простыми лишь те, внутренние произведения которых в p_L(k,t) содержат вершину x_s. Таким образом, если из p’_L+1(s,t) исключить все слагаемые, содержащие x_s (а это можно сделать простой проверкой), то получим p_L+1(s,t). Матрица P_L+1=[p_L+1(s,t)], все диагональные элементы которой равны 0, является тогда матрицей всех простых цепей длины L+1.

Вычисляя затем B*P_L+1, находим P_L+2 и т.д., пока не будет построена матрица P_n-1, дающая все гамильтоновы цепи (имеющие длину n-1) между всеми парами вершин. Гамильтоновы циклы получаются тогда сразу из цепей в P_n-1 и тех дуг из G, которые соединяют начальную и конечную вершины каждой цепи. С другой стороны, гамильтоновы циклы даются членами внутреннего произведения вершин, стоящими в любой диагональной ячейке матрицы B*P_n-1 (все диагональные элементы этой матрицы одинаковые).

Очевидно, что в качестве начального значения матрицы P (т.е. P₁) следует взять матрицу смежности A графа, положив все ее диагональные элементы равными нулю.

Недостатки этого метода совершенно очевидны. В процессе умножения матриц (т.е. когда L увеличивается) каждый элемент матрицы P_L будет состоять из все большего числа членов вплоть до некоторого критического значения L, после которого число членов снова начнет уменьшаться. Это происходит вследствие того, что для малых значений L и для графов, обычно встречающихся на практике, число цепей длины L+1, как правило, больше, чем число цепей длины L, а для больших значений L имеет место обратная картина. Кроме того, так как длина каждого члена внутреннего произведения вершин увеличивается на единицу, когда L увеличивается на единицу, то объем памяти, необходимый для хранения матрицы P_L, растет очень быстро вплоть до максимума при некотором критическом значении L, после которого этот объем снова начинает уменьшаться.

 

 

Примеры решения задач

Задача 1.

Найти все гамильтоновы циклы в графе

 

Матрица смежности данного графа равна А=

 

модифицированная матрица смежности равна В=

	b		d
			d	e
	b			e
		c
a		c

Положим ≡А. Матрица получается равной

		d	b	b
e		d+e
e			b	b
	c			c