sexta-feira, 11 de junho de 2010

Grafos Eulerianos


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:

AS CLASSES DE GINÁSTICA - o método de Hamilton

Três classes de ginástica de um clube decidem constituir uma associação que defenda os seus interesses. A assembleia será constituída por 2...