Grafos- Ariana e Laís

Eulerização de um grafo

Realizado por: Ariana Rocha nº1 - 11ºD. Laís Mesquita nº10 - 11ºE

ÍNDICE

Eulerização de grelhas não retangulares

Definição/ exemplo

Uma melhor eulerização

Sites utilizados

Eulerização de grafos-grelha

Agradecimento

DEFINIÇÃO/EXEMPLO

É um processo que consiste em transformar um grafo que não é de Euler num grafo de Euler, duplicando as arestas.

Exemplo:

Exercício: Eulerize o grafo representado na figura seguinte.

UMA MELHOR EULERIZAÇÃO

A melhor eulerização é sempre aquela que acrescenta o menor número de arestas. Podendo haver mais do que uma "melhor eulerização".

• No exercício anterior podemos ver que há mais do que uma forma de eulerizar um grafo.

• Para a eulerização de um grafo é necessário:

- A partir do grafo dado, acrescentar arestas, por duplicação, às já existentes, até que se obtenha um grafo conexo e com vértices de grau par;-As arestas acrescentadas devem ter uma cor diferente às do grafo original; -E verificar se é possível indicar um circuito de Euler.

Exemplo:

Considere o grafo representado. G e D são vértices de grau ímpar. Quais das seguintes eulerizações são uma "melhor eulerização".

Dica: Não é possível eulerizar o grafo com menos de três arestas.

Exercício

Eulerize o grafo representado na figura.

EULERIZAÇÃO DE GRAFOS- GRELHA

Grelha = rede retangular

Explicação:

Se percorrermos um circuito de Euler com um lápis. Veremos que contorna o retângulo ao adicionar arestas de acordo com certas regras. Quando um vértice de grau ímpar é alcançado, ele é conectado ao próximo por uma aresta adicionada. Se for de grau par, a viagem continua até um vértice de grau par ou ímpar.

. Qualquer rede viária retangular pode ser representada por uma grelha.

Exemplo: Eulerizar uma grelha retangular

Exercício: Eulerize a grelha ao lado

EULERIZAÇÃO DE GRELHAS NÃO RETANGULARES

Existem 8 vértices de grau ímpar. Para não percorrermos a mesma aresta, temos que as duplicar. Com esse procedimento, ao acrescentar uma nova aresta a dois vértices de grau ímpar, ambos ficam com grau par.

Nesse processo temos que: - Localizar todos os vértices de grau ímpar; - Formar pares de vértices de grau ímpar; -Procurar o comprimento do caminho menor entre cada par; - Se necessário, reorganizar os pares de modo que a soma do número de arestas que se acrescenta seja mínima.

Com a resolução do grafo, pode se afirmar que há um circuito euleriano. Se não se pretendesse terminar a viagem, podia-se ter deixado dois vértices de grau ímpar. A este processo chama-se semieulerização do grafo

Exercício: Encontre uma boa eulerização para o grafo

SITES UTILIZADOS

Manual pág.30 até pág.35

ESPERO QUE TENHAM GOSTADO!