TYYY

Escola Secundária de D. Pedro V
Matemática Aplicada às Ciências Sociais
Texto de Apoio nº ……….

Ano: ………. Turma: ………….

Data: ……. /……. /…….

Assunto: Eulerização / Semieulerização
Nos problemas de grafos até agora estudados o objectivo é percorrer todas as arestas de um grafo de uma só vez repetindo o menor número de arestas.
1. Se o grafo for euleriano, isto é, admitir um circuito de euler, então é possível percorrer todas as arestas de uma só vez sem repetir qualquer aresta do grafo, começando e terminando no mesmo vértice.
Uma condição necessária e suficiente para que um grafo seja euleriano é ser conexo e todos os seus vértices serem de grau par (Teorema de Euler);
Exemplo:
O grafo é conexo e todos os seus vértices são

B

C

A

de grau par, logo é um grafo euleriano (admite
G
um circuito de euler). Assim, é possível percorrer todas as arestas do grafo de uma só vez

sem

repetir

qualquer

aresta,

F

E

começando e terminando no mesmo vértice.
Percurso possível: A B C D E C G F E G B F A
2. Se o grafo admitir um caminho de euler, então também é possível percorrer todas as arestas de uma só vez sem repetir qualquer aresta, começando num vértice de grau ímpar e terminando noutro vértice de grau impar.
Uma condição necessária e suficiente para que um grafo admita um caminho de euler é ser conexo e no máximo dois dos seus vértices serem de grau ímpar (Teorema do caminho de euler) – esse percurso começa num dos vértices de grau ímpar e termina no outro. Exemplo:
O grafo é conexo e tem apenas dois vértices de grau ímpar – B e C – logo admite um caminho de euler. Assim, é possível percorrer todas as arestas do grafo de uma só vez sem repetir qualquer aresta, começando num vértice de grau ímpar e terminando no outro.
Percurso possível: B A D E C D B C

D

3. Se o grafo não admitir circuitos de euler (não é euleriano) nem admitir caminhos de euler então não é possível percorrer todas as arestas do