Ensino Superior ⇒ Teoria dos Grafos Tópico resolvido

[Tassandro]

Considere um grid (quadriculado) N por N. Imagine que os quatros lados de cada um dos quadradinhos 1x1 é uma porta. Considere que uma pessoa que está inicialmente fora desses [tex3]N^2[/tex3] quadradinhos vai tentar fazer um caminho por eles de forma que ela passe por cada porta exatamente uma vez. Para qual(is) valor(es) de N isso é possível?
Para o caso em que N=1, por exemplo, o seguinte caminho é possível:

20200413_223636.jpg (25.42 KiB) Exibido 1313 vezes

[danmat]

Boa noite!

Podemos modelar esse problema da seguinte forma:

Considere cada quadradinho do grid [tex3]N^k[/tex3] um vértice de um grafo G. Nesse grafo, os vértices serão adjacentes da seguinte forma:

i. Vértices que representam quadradinhos do interior do grid: serão adjacentes se tiverem uma porta em comum.
ii. Vértices que representam quadradinhos na margem do grid: será duplamente adjacente a um outro vértice da margem, representado por duas das portas externas dos respectivos quadradinhos.

Portanto, cada porta interna representa uma aresta deste grafo G e cada 2 portas externas representa uma aresta também de G. Concluímos que o grau de cada vértice de G é

[tex3]d_G(v_i) = 4[/tex3]

Como o grau de todos seus vértices é par e G é conexo, então concluímos que G é euleriano. Portanto, há um circuito euleriano que compreende o percurso por todas as portas do grid para [tex3]N^k, k \in N[/tex3].

Observe o exemplo para [tex3]N^4[/tex3]: