Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafo é abstração que permite codificar relacionamentos entre
pares de…
Grafo é abstração que permite codificar relacionamentos entre
pares de objetos como pontos(vértices) e linhas(arestas).
Notação: G = (Vértices,Arestas)
Vértice
Uma Vértice pode ser considerada "fonte"(onde só saem arestas) ou "sumidouoro"(onde só entram arestas).
-
O Grau de uma Vértice é definido pelo número de Aresta conectadas a ela.
Arestas
-
Uma aresta é a 'ponte' entre dois vértices, ela não existe sozinha.
Hamiltoniano
Ciclo hamiltoniano é quando o caminho percorrer todo o grafo, passando somente uma vez em cada vértice.(Saída e retorno a mesma aresta).
Circuito hamiltoniano é o caminho que permite percorrer um grafo passando por todos os seus vértices somente uma vez em cada.
Grafo hamiltoniano é quando existe um ciclo que contenha todos os vértices(aparecendo uma vez cada).
Método de percorrer um grafo, escolhendo o menor caminho.
Exaustivo
Consiste em fazer uma lista de todos os ciclos Hamiltonianos do grafo, calcular o peso de cada um e escolher um de peso mínimo
Este método é, em geral, impossível de implementar já que o número de operações é da ordem de (n−1)! para Kn.
Guloso
Consiste em sempre escolher a vértice mais próxima, e a partir dela, repetir o processo, até retorna ao vértice de inicial.
Esse método é muito mais rápido que o de exaustão, embora não produza, em geral, a solução ótima.
-
Euleriano
-
Caminho
Percorre todas as arestas de um grafo apenas uma vez, mas sem exigir que seja um ciclo.
-
Coloração em Grafos
Atribuição de cores aos vértices, de modo vértices adjacentes tenham cores distintas.