Grafos Eulerianos

Caminho euleriano – É um caminho que passa uma única vez em cada aresta de um grafo.

Circuito euleriano – É um circuito que passa uma única vez em cada aresta de um grafo.

Um grafo diz-se euleriano se possuir um circuito euleriano.

Teorema de Euler – Um grafo é euleriano se e só se for conexo e todos os seus vértices forem de grau par.

Teorema dos caminho de Euler – Um grafo admite um caminho euleriano se e só se for conexo e, no máximo, dois dos seus vértices tiverem grau ímpar.

  • Algoritmo para encontrar um circuito euleriano
  1. Definimos o vértice de partida;
  2. Escolhemos um caminho seguindo por arestas não percorridas até regressarmos ao vértice de partida;
  3. Se todas as arestas tiverem sido percorridas, encontrámos o circuito pretendido, senão, existe algures um vértice com arestas não percorridas. Seleccionamos esse vértice como novo ponto de partida e repetimos o passo anterior;
  4. Juntam-se todos os circuitos encontrados, de modo a obtermos um circuito euleriano.

Eulerizar um grafo significa acrescentar arestas, por duplicação de arestas existentes, de modo que um grafo não-euleriano se transforme num grafo euleriano.

Um processo de eulerização que mantenha dois vértices com grau ímpar chama-se semieulerização.

~ por goncasrato em 02/21/2010.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s

 
%d bloggers like this: