Caminho Euleriano

Caminho Euleriano
Lema 1- Dado um grafo não orientado conexo G = (V, E) com todos os vértices de grau par, então qualquer par de vértices u, v ∈ G faz parte de um ciclo sem arestas repetidas

Teorema 1: Um grafo não orientado conexo G ´e um grafo euleriano se e somente se todo vértice de G tem grau par

------------------------------------------------------
Entrada: Um grafo conectado G cujos vértices têm grau par
Saída: Um circuito euleriano
Algoritmo: Circuito Euleriano Inicie em qualquer vértice v Construa um percurso fechado T em G Enquanto existirem arestas de G fora do percurso T Escolha qualquer vértice w em T, que seja incidente a uma aresta fora do percurso Iniciando em w, construa um percurso fechado D de arestas fora do percurso T Faça a união do percurso D em T no ponto w Retorne T

-----------------------------------------------------------------

2) Grafo hamiltoniano
Um caminho hamiltoniano (ciclo hamiltoniano) é um caminho (ciclo) que usa cada vértice do grafo exatamente uma vez (exceto o primeiro vértice que ´e visitado duas vezes)
Um grafo que contém um ciclo hamiltoniano é chamado de grafo hamiltoniano.
Propriedades
Teorema de Ore
Uma condição suficiente (mas não necessária) para que um grafoG = (V, E) seja hamiltoniano é que a soma dos graus de cada par de vértices não adjacentes seja no mínimo |V|.
Teorema de Dirac
Uma condição suficiente (mas não necessária) para que um grafoG = (V, E) possua um ciclo hamiltoniano, é que o grau de cada vértice em G seja pelo menos igual a |V|/2,

3) Caminho Mínimo

O algoritmo de Dijkstra

• Seja G(V,A) um grafo orientado e s um vértice de G:
• Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da busca) e infinito às demais estimativas;
• Atribua um valor qualquer aos precedentes (o precedente de um vértice t é o vértice que precede t no caminho de custo mínimo de s para t);
• Enquanto houver vértice aberto: – seja