Fazendo a tarefa 8, encontrei duas dúvidas sobre definições... Não é muito óbvio pra mim, se for pra alguém, espero que possa me ajudar...
1-) Uma grade m-por-n é considerada uma grade de m linhas por n colunas com mxn vértices de modo que todas as arestas possíveis existem? Ou basta a "formação", sem o máximo de arestas, para que se diga que é uma grade? A tarefa 8 dá uma definição que me pareceu incluir todas as arestas, mas na tarefa 6 as tais grades não precisavam ter todas as arestas...
2-) Pela função GRAPHpathH, temos que são passados um grafo, v e w para descobrir se há caminho hamiltoniano de v a w. Mas seja um grafo com apenas um vértice e nenhuma aresta. Então G->V = 1 e, logo, G->V - 1 = 0. Se eu usasse v = w = 0, teria a chamada:
pathR (G, 0, 0, 0);
A função pathR veria então que v = w e que d = 0, retornando que existe um caminho hamiltoniano. Isso é certo??? Um grafo sem arestas pode conter um caminho hamiltoniano?
Obrigado!
1. De fato, talvez eu não tenha sido suficientemente claro.
Uma grade m por n é uma generalização natural de um grade
n por n. Só os vértices "vizinhos" acima, abaixo, à esquerda
e à direita são adjacentes. Eis um exemplo de um grade
3 por 4
o--o--o--o
| | | |
o--o--o--o
| | | |
o--o--o--o
Quer ser mais formal? Cada vértice é um par (i,j) sendo i extraído do conjunto {1..m} e j extraído do conjunto {1..n}. Dois vértices (i,j) e (p,q) são adjacentes se
i = p e |j-q| = 1
ou
|i-p| = 1 e j = q.
2. Um caminho é uma sequência de vértices tal que cada vértice (a partir do segundo) é adjacente ao anterior. Em particular, uma sequência com um só vértice é um caminho (e esse caminho é *simples*, pois não repete vértices).
Um caminho é hamiltoniano se for simples e passar por todos os vértices. Conclusão: um grafo com um só vértice tem um caminho hamiltoniano.
(Mas não confunda caminho com ciclo. Em particular, não confunda caminho hamiltoniano com ciclo hamiltoniano.)
Ok, obrigado! O problema mesmo do 1-) era eu não saber se a grade teria ou não todas as arestas, mas isso foi respondido na explicação. O exemplo foi bem claro... 
E a segunda dúvida também foi totalmente esclarecida.