Questão de Tecnologia da Informação

Para as questões 5, 6, 7 e 8, defina Gnxn como um grafo não dirigido 2D grid com 4- vizinhança da seguinte forma: • cada vértice é identificado com uma coordenada inteira 2D, de (1,1) até (n,n); • há n x n vértices, correspondendo a todos os valores de (1,1) até (n,n); • em cada vértice incidem até 4 arestas, a saber, para um vértice (i,j) (i,j) ↔ (i-1,j) (i,j) ↔ (i+1,j) (i,j) ↔ (i ,j-1) (i,j) ↔ (i ,j+1) onde as arestas não existem se alguma coordenada é < 1 ou > n. A Figura 1 (a seguir) mostra um exemplo para n = 5 4

Figura 1