Para o caso em que N=1, por exemplo, o seguinte caminho é possível:
- 20200413_223636.jpg (25.42 KiB) Exibido 1085 vezes
Ensino Superior ⇒ Teoria dos Grafos Tópico resolvido
Moderador: [ Moderadores TTB ]
-
Tassandro 
- Mensagens: 1905
- Registrado em: Sáb 15 Fev, 2020 17:01
- Última visita: 03-10-23
- Localização: Teresina, PI.
Mai 2020
31
23:43
Teoria dos Grafos
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:
Para o caso em que N=1, por exemplo, o seguinte caminho é possível:
Dias de luta, dias de glória.
Jun 2020
01
20:59
Re: Teoria dos Grafos
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] :
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] :
- Anexos
-
- grafos.png (28.3 KiB) Exibido 1015 vezes
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 0 Respostas
- 181 Exibições
-
Última msg por Thiagosn1
-
- 0 Respostas
- 240 Exibições
-
Última msg por Lucastadeu14
-
- 1 Respostas
- 225 Exibições
-
Última msg por Idocrase
-
- 2 Respostas
- 550 Exibições
-
Última msg por Ornitologo
