Caminhos e circuitos eulerianos – as sete pontes de Königsberg

O que mostra

Em 1736, Leonhard Euler perguntou se um passeio por Königsberg poderia atravessar cada uma das sete pontes exatamente uma vez. Ao transformar as porções de terra em vértices e as pontes em arestas, ele mostrou que a resposta depende apenas dos graus. Um grafo conexo tem um circuito euleriano quando todos os vértices têm grau par, e um caminho euleriano quando exatamente dois vértices têm grau ímpar; o caminho começa em um vértice ímpar e termina no outro. A simulação permite várias arestas entre os mesmos dois vértices, mas não laços, e o mapa de Königsberg é simplificado.

Como usar

Comece com Sete pontes de Königsberg e leia os graus e a conclusão. Mude o Modo para Percorrer à mão e toque nas arestas para tentar atravessar cada ponte uma vez. No modo Desenhar / mover, adicione ou ligue vértices até a conclusão mudar; depois escolha Fleury (evitar pontes) ou Hierholzer (encaixar circuitos) e pressione Passo ou Executar para ver o percurso sendo montado.

Parâmetros que você pode mudar

• Grafo inicial Sete pontes de Königsberg, Envelope (desenhar sem tirar o lápis), Dois triângulos com um vértice comum, Grafo completo de 5 vértices (K5), Página em branco – desenhe o seu
• Algoritmo Fleury (evitar pontes), Hierholzer (encaixar circuitos)
• Velocidade da animação 0,5–4 arestas/s

Perguntas para explorar

1. Por que é impossível atravessar cada uma das sete pontes de Königsberg exatamente uma vez?
2. Quantas pontes, no mínimo, você precisa acrescentar para obter um caminho euleriano, e onde?
3. Por que um caminho euleriano precisa começar em um vértice ímpar e terminar no outro?