aula3 4 5

Teoria de Grafos
Aula 3
Rosário Ribeiro [e-mail] Universidade Federal de Goiás

1

Exemplo
• Em (1) o passeio inicia pelo vértice 1, avançando na sequência 1-6-4-3-2-6-4-3
• Um passeio é aberto quando o vértice inicial é diferente do vértice final e fechado caso contrário.
• Em (2) tem-se o passeio fechado1-5-3-4-2-3-1 2

Cadeia ou Trilha
• Uma cadeia ou trilha é um passeio sem repetição de arestas. • Em (1) cadeia aberta:
5-a8-1-a7-4-a3-3-a4-2-a5-6-a1-1
• Em (2) cadeia fechada:
5-1-3-4-1-6-2-5
• OBS: a cadeia da figura (1) é aberta apesar de possuir uma subcadeia fechada (1-4-3-2-6-1)

3

Caminho
• Um caminho é uma cadeia sem repetição de vértices. • Um caminho entre os vértices “a” e “b” será denotado por a-b, por Pa-b ou por Pi.
• Em um grafo não ponderado, o comprimento de um caminho é o número de arestas desse caminho. • Em um grafo ponderado, o comprimento de um caminho é a soma dos pesos das arestas desse caminho.

4

Conceitos

5

Ciclo
• Em um grafo G, um ciclo é um caminho fechado. • Quando um grafo G é orientado, alguns autores denominam circuito a sequência de arcos distintos que repete somente o primeiro e último nó visitados.

6

Ciclo Euleriano
• Percurso passando por todas as arestas uma única vez e retornando ao ponto inicial: – este percurso (ciclo) só existe se o grau dos vértices for par. Onde, o grau de um vértice é o número de arestas incidentes.
A
B

D

A – grau 3
B – grau 5
C – grau 3
D – grau 3

C

7

Caminho Euleriano
• Um vértice com um número ímpar de arcos tem de ser o primeiro ou o último da trajetória. Isto é, podem haver, no máximo, dois vértices com um número ímpar de arcos ligados a eles.
• No caso das pontes de Königsberg, existem quatro vértices com um número ímpar de arcos, logo, não tem solução. 8

Caminho Hamiltoniano
• Trata-se de um caminho em G, passando por todos os vértices, os visita somente uma vez

9

Ciclos eulerianos e hamiltonianos Ciclos eulerianos e hamiltonianos

10

Corda
• É uma aresta