Um caminho de Euler
Lembro-me de ser desafiado a um jogo de cérebro em que recebo a imagem de um gráfico com pontos e linhas conectadas e me dizem para descobrir uma maneira de desenhar a mesma figura sem levantar meu lápis e apenas desenhar cada lado uma vez. Não pude passar por cima de um lado que já havia desenhado. Eu mal sabia então que o que estava fazendo estava realmente relacionado ao tópico que estamos discutindo nesta vídeo-aula.
O que fiz foi desenhar um caminho de Euler , um caminho em um gráfico onde cada lado é percorrido exatamente uma vez. Um gráfico com um caminho de Euler é chamado de semi-Euleriano . Eu gostei muito do desafio e pensei pouco nas conexões matemáticas que ele tinha. Deixe-me mostrar o jogo cerebral que recebi.
 |
Para desenhar essa forma sem levantar meu lápis e passar por cada linha exatamente uma vez, tive que começar no ponto 1, ir para o ponto 3, depois 2, depois 4 e depois 3 novamente. Você vê como examinamos cada linha apenas uma vez? Essa é a característica definidora de um gráfico de Euler. Além disso, observe que acabamos em um local diferente.
Outra característica de um gráfico semi-Euleriano é que no máximo dois dos vértices serão de grau ímpar, o que significa que terão um número ímpar de arestas conectando-os a outros vértices. Todos os outros vértices serão pares. Neste gráfico, vemos que os vértices 1 e 3 são ímpares, enquanto 2 e 4 são pares.
Exemplo 1
Vejamos outro exemplo. Desta vez, veja se você consegue descobrir.
 |
Novamente, o que estamos tentando fazer é encontrar um caminho no gráfico de forma que cruzemos cada aresta exatamente uma vez. Lembre-se de que um caminho leva você de um ponto a outro. Você pode encontrar um neste gráfico?
Tente começar no ponto 2. Agora desça até o ponto 1. Depois, vá até o ponto 4, volte ao ponto 2, volte ao ponto 3 e, finalmente, ao ponto 4. Temos um caminho de Euler! Cruzamos cada borda exatamente uma vez. Então, isso significa que este gráfico é semi-Euleriano.
Existem outros caminhos de Euler neste gráfico? Sim, existem. Também podemos notar esses caminhos de Euler apenas escrevendo os nomes dos vértices que passamos. Portanto, outro caminho de Euler neste gráfico é 4, 3, 2, 4, 1, 2. Observe que, com todos esses caminhos, terminamos em um ponto diferente de onde começamos. Existem outras maneiras de desenhar essa forma usando um caminho de Euler? Não direi quais são, mas direi que há um total de 6 caminhos de Euler neste gráfico. O que torna cada caminho diferente é a ordem em que as bordas são desenhadas.
Um circuito de Euler
Se terminarmos no mesmo ponto em que começamos, teremos o que é chamado de circuito de Euler , um circuito em um gráfico onde cada aresta é percorrida exatamente uma vez e que começa e termina no mesmo ponto. Olhe para este gráfico e veja se você pode desenhá-lo sem levantar o lápis, passando por cada aresta apenas uma vez, e começando e terminando no mesmo ponto:
 |
Assim como com os caminhos de Euler, podemos ter vários circuitos de Euler em um gráfico. Este é um exemplo simples, e você já deve ver várias maneiras de desenhar essa forma usando um circuito de Euler. Como esse gráfico contém um circuito de Euler, chamamos esse gráfico de Euleriano . Um circuito de Euler que este gráfico possui é 2, 3, 4, 1, 2. Alternativamente, você também pode desenhar esta forma seguindo o circuito de Euler 1, 2, 3, 4, 1. Observe que nossos pontos inicial e final são os mesmo nesses circuitos. Terminamos onde começamos.
Além disso, para um gráfico Euleriano, todos os vértices são pares, o que significa que todos os vértices terão um número par de arestas conectando-os a outros. Observe nosso gráfico acima e verá que todos os nossos vértices possuem um número par de arestas.
Exemplo 2
Podemos ter circuitos de Euler simples e também circuitos de Euler mais complexos. Vejamos um. Veja se você consegue localizar o circuito de Euler desta vez.
 |
Desta vez, as arestas são rotuladas em vez dos vértices. Você pode desenhar este usando um circuito de Euler? Siga as bordas em ordem alfabética e você verá um circuito de Euler. Isso significa que este gráfico é euleriano. Você vê mais circuitos de Euler neste gráfico? Eu vejo pelo menos mais um.
Resumo da lição
Vamos revisar o que aprendemos. Um caminho de Euler é um caminho em um gráfico onde cada lado é percorrido exatamente uma vez. Um gráfico com um caminho de Euler é chamado de semi-Euleriano . No máximo, dois desses vértices em um gráfico semieuleriano serão ímpares. Todos os outros ficarão iguais. Um circuito de Euler é um circuito em um gráfico em que cada aresta é percorrida exatamente uma vez e começa e termina no mesmo ponto. Um gráfico com um circuito de Euler é chamado de Euleriano . Todos os vértices em um gráfico Euleriano serão pares. Você pode ter vários caminhos de Euler em um gráfico. Você também pode ter vários circuitos de Euler em um gráfico. A diferença entre cada caminho e circuito é a ordem em que as bordas são passadas.
Resultados de Aprendizagem
Após esta lição, você será capaz de:
- Defina o caminho de Euler e o circuito de Euler
- Explique o que são gráficos semi-Eulerianos e Eulerianos