1-Modelos de Grafos

1-Modelos de Grafos

1. Euler

   • Problema do Carteiro Chinês
     • Trilhos Eulerianos
     • Circuitos Eulerianos
   • Eulerizar um grafo, consiste em acrescentar-lhe arestas,(entre vértices que já tenham pelo menos uma aresta) por forma a tornar possível encontrar um circuito euleriano. Regra: Para se adicionar arestas de forma correta é preciso que o número de repetições de arestas seja igual ao número de arestas acrescentadas A melhor eulerização é aquela que acrescenta um menor número de arestas.

2. Hamilton

   • Caixeiro Viajante
     • Algoritmo dos mínimos sucessivos
     • Algoritmo peso das arestas

3. Árvores

   • Propriedades das árvores: 1. Se um grafo é uma árvore há um e um só caminho entre dois quaisquer vértices. O recíproco também é verdadeiro. 2. Numa árvore cada aresta é uma ponte. O recíproco também é verdadeiro (se o grafo for conexo). 3. Uma árvore com n vértices tem n – 1 arestas. 4. Um grafo conexo com n vértices e n -1 arestas é uma árvore.
     • Algoritmo de Kruskal
       • 1.°Passo) Encontrar a aresta com menor peso (se houver mais do que uma, escolhemos ao acaso) e "marcá-la" a cor; 2.°Passo) Encontrar a aresta seguinte com menor peso (se houver mais do que uma, escolhemos ao acaso) e "marcá-la" a cor; 3º Passo) Encontrar a aresta seguinte com menor peso que não feche um ciclo e marcá-la a cor (uma vez mais, se houver mais do que uma escolhemos ao acaso). Se a aresta a escolher fechar um ciclo, não consideramos essa aresta;

4. Caminhos Críticos

   • O caminho crítico é a série de tarefas (ou mesmo uma tarefa única) que determina a data de conclusão calculada do projeto. Ou seja, quando se conclui a última tarefa do caminho crítico, conclui-se o projeto.