Mapa Mental - Algoritmos em Grafos

Prévia do material em texto

Tipos de Grafos Algoritmos de Árvore Geradora Mínima Grafo ponderado possui pesos associados às suas Algoritmos de Prim e Kruskal buscam sempre arestas ou arcos passo mais promissor a cada iteração Grafos podem ser simples, Esses algoritmos são classificados como direcionados (orientados) algoritmos guloso por sua estratégia ou não direcionados Árvore geradora mínima conecta todos Grafos regulares têm todos vértices com custo total mínimo vértices com mesmo Aplicações incluem redes de comunicação, grau planejamento e otimização Grafos podem ser conexos, desconexos, fontes ou sumidouros conforme estrutura Algoritmos Representação de Grafos Algoritmos de Caminho Mínimo em Matriz de adjacência é uma Algoritmo de Dijkstra encontra matriz N X N que representa caminho mais curto em grafos dirigidos conexões Grafos ou não Lista de adjacência armazena Dijkstra atualiza pesos mínimos para vértices adjacentes para cada nó cada vértice durante a execução Matriz booleana tem diagonal Peso final de um vértice representa a principal geralmente composta distância mínima do vértice inicial por zeros Algoritmos de caminho mínimo são Matriz pode ser booleana ou essenciais para redes e roteamento conter pesos, dependendo do grafo Complexidade e Verdades em Grafos Algoritmo para ciclo Euleriano tem complexidade linear em relação às arestas Nem todo grafo Euleriano é Hamiltoniano, Caminhos e Ciclos em Grafos pois visitam elementos diferentes Propriedades de Grafos Planar Grafos Hamiltonianos visitam todos Ciclo Hamiltoniano visita todos Grafos planares podem ser desenhados vértices uma única vez, não todas as vértices uma única vez, exceto sem arestas cruzadas no plano arestas inicial Fórmula de Euler relaciona vértices, Ciclo Euleriano visita todas as Compreender diferenças entre ciclos é arestas e faces em grafos planares fundamental para análise de grafos arestas exatamente uma vez no grafo Número de faces pode ser calculado a Nem todo grafo Euleriano é partir do número de vértices e arestas Hamiltoniano, e vice-versa, conceitos Grafos simples, conexos e planares distintos obedecem restrições específicas de Caminho Euleriano percorre todas as estrutura arestas, mas não necessariamente todos vértices