Yo no soy la gráfica de la teoría del experto, pero he estado pensando acerca de este problema durante mucho tiempo.
Deje $G_n$ $n$- dimensional, el infinito, la unidad de los cuadrados de la cuadrícula gráfico, es decir, el grafo cuyos vértices son los puntos de $\mathbb{Z}^n$ y que tiene una arista entre cada par de vértices separados por una distancia Euclidiana de 1.
Sé que, para cualquier $d$$\mathbb{N}$, la $\mathbb{Z}^d$ es countably infinito, es decir, uno puede encontrar un bijection entre el$\mathbb{N}$$\mathbb{Z}^d$. Ese no es el tema aquí.
Mi pregunta es: ¿cuáles son las condiciones bajo las cuales la gráfica contiene un Hamiltoniano ray? En otras palabras, ¿bajo qué condiciones un camino que comienza en algún vértice de la gráfica y la visita cada vértice de $G_n$ exactamente una vez (por saltar de un vértice a un lado de vértice) existe?
Debido a la invariancia de $G$ por la traducción por parte de cualquier unidad de la base de vectores, podemos considerar, sin pérdida de generalidad, que tal un rayo comienza en el origen.
Es fácil ver que:
- en el $n=1$ caso, no ray existe: cualquier dirección que pusimos en marcha en el número de línea, no se puede doubleback para recoger los enteros se encuentran en el otro lado, desde el origen;
- en el $n=2$ de los casos, hay un número infinito de tales rayos: un ejemplo fácil es que algunos "plaza de la espiral", partiendo del origen.
Sin embargo, la respuesta de $n\geq3$ me escapa.
En un intento de resolver el $n=3$ de los casos, me puse a responder a una pregunta relacionada: si el subgrafo (vamos a llamar a $G_3'$) $G_3$ cuyas coordenadas son en $\{-1,0,1\}^3$ contiene un Hamiltoniano ray comenzando en el origen. No conocer nada mejor, me resolvieron el problema por fuerza bruta en Matlab (ver el código de abajo, en la que puede cambiar el punto de partida).
Resultado: $G_3'$ sí no contienen un Hamiltoniano ray comenzando en el origen.
Mi intuición me lleva a pensar que tal camino no existe en $G_n$ si y sólo si $n$ es incluso.
¿Qué TE parece? Es un resultado conocido?
Secuencia de comandos de Matlab:
tic
%clc
a=0.7;
% ---------------- vertex generation ------------------
N=3; % number of nodes along one edge
% generation of the coordinate vectors x, y, z
for k=1:3
temp=[];
for m=0:N-1
temp=[temp m*ones(1,N^(k-1))];
end
temp2=[];
for n=1:N^(3-k)
temp2=[temp2 temp];
end
switch k
case 1
x=temp2;
case 2
y=temp2;
case 3
z=temp2;
end
end
% ------------------ plotting and labelling the vertices -----------
fig = figure;
set(fig,'color',[1 1 1]);
ax = axes;
plot3(x,y,z,'o');
axis off
for k=1:N^3
text(x(k),y(k),z(k)+0.1,num2str([N^0 N^1 N^2] * [x(k) y(k) z(k)]'+1));
end
% ----------------- generating the edges and the adjacency matrix ------------------
edge_h = zeros(53,1);
edges = zeros(53,1);
% adjacency matrix
A=zeros(N^3,N^3);
n=0;
for i=1:N^3
vi = [N^0 N^1 N^2] * [x(i) y(i) z(i)]';
for j=1:N^3
vj = [N^0 N^1 N^2] * [x(j) y(j) z(j)]';
weight = sum(([x(j) y(j) z(j)]-[x(i) y(i) z(i)]).^2);
if (weight == 1) && isempty(find(edges(:,1) == vj + sqrt(-1)*vi)) % (vi,vj) is an edge
% update adjacency matrix
A(i,j)=1;
A(j,i)=1;
edge_h(n+1)=line([x(i) x(j)],[y(i) y(j)],[z(i) z(j)],'Color',a*[1 1 1],...
'Linestyle',':',...
'LineWidth', 2);
vi = [N^0 N^1 N^2] * [x(i) y(i) z(i)]';
vj = [N^0 N^1 N^2] * [x(j) y(j) z(j)]';
edges(n+1,1) = vi+sqrt(-1)*vj;
n = n + 1;
%pause(0.1)
end
end
end
toc
% ------- look for a Hamiltonian path starting by the given path -------
%path_init = [14 5 2]; % starting point
path_init = 10;%[2 1]; %[2 11]
path = path_init;
flag=0;
chemin=line(x(path),y(path),z(path),'Color',a*[1 1 1],'Linestyle',':','LineWidth', 2);
while numel(path)<N^3
[ path , flag ]=recursive_path_finding( path ,flag , A );
delete(chemin)
chemin=line(x(path),y(path),z(path),'Color',[1 0 0],'Linestyle','-','LineWidth', 2);
drawnow
%pause(0.1)
if numel(path) == numel(path_init)
disp('No Hamiltonian path for which the initial path considered is a subgraph.');
break
end
end
set(fig,'Name',['Path length: ' num2str(path)]);
recursive_path_finding.m función de:
function [ path1 , flag1 ]=recursive_path_finding( path0 , flag0 , A )
% NOTE: neighb(i) informs on the order of path0(i+1) as a neighbour of path0(i)
switch flag0
case 0 % path0(end) has just been added to path0. Find a neighbour of path0(end) that hasn't already been explored.
u = find(A(path0(end),:)==1); % Find all the neighbours of path0(end).
for k=1:length(u)
% Check that u(k) has not already been explored.
temp = find(path0==u(k));
if isempty( temp ) % Not yet explored: add it to the path and break the loop.
path1 = [path0 u(k)];
flag1 = 0;
break % A new candidate for the next step has been found, not need to carry on the loop interations.
end
end
if ~exist('path1') % All the neighbours of path(end) have been explored, so path0(end) is not a valid candidate. Backtrack.
path1 = path0;
flag1 = path0(end);
end
otherwise % path0(end) is not a valid candidate.
u = find(A(path0(end-1),:)==1); % Find all the neighbours of path0(end-1).
v = u(find(u>flag0)); % Discard all the neighbours of path0(end-1) listed before flag0 (inclusive).
for k = 1 : length(v) % Test all the neighbours of path0(end-1) listed AFTER the (previously tested) flag0.
% Check that v(k) has not already been explored.
temp = find(path0==v(k));
if isempty( temp ) % Not yet explored: add it to the path and break the loop.
path1 = [path0(1:end-1) v(k)];
flag1 = 0;
break % A new candidate has been found in place of path0(end), not need to carry on the loop interations.
end
end
if ~exist('path1') % All the neighbours of path(end-1) have been explored, so path0(end-1) is not a valid candidate. Backtrack.
path1 = path0(1:end-1);
flag1 = path0(end-1);
end
end
