Um circuito de Euler é um circuito que passa uma única vez em cada aresta do grafo.
Um grafo diz-se euleriano se admite um circuito de Euler.
Um caminho de Euler ou um caminho euleriano é um caminho que passa uma única vez em cada aresta do grafo.
Um grafo é euleriano se e só se é conexo e todos os seus vértices são de grau par.
Um grafo admite um caminho euleriano se e só se é conexo e no máximo 2 dos seus vértices têm grau ímpar. Tal caminho terá início num dos vértices de grau ímpar e termina no outro vértice de grau ímpar.
Ao processo que consiste em transformar um grafo que não é euleriano num grafo de Euler, duplicando arestas, chama-se eulerizar um grafo.
Sem comentários:
Enviar um comentário