Grafos

Olá pessoal! Hoje falaremos um pouco sobre grafos. Eles são utilizados para solucionar vários tipos de problemas em diversas áreas como pesquisa sobre DNA, logística(para determinar a melhor rota entre cidades), genética(mapeando genes), em cidades para saber como o transito irá fluir e qual direção. Enfim, o uso dos grafos é vasto e importante, não iremos passar por todos os tipos de grafos mas iremos ver alguns tipos.

Um grafo é uma coleção de vértices e arcos enfim. Onde, G é um grafo, V é um conjunto de vértices (nodos), E é um conjunto de arcos (arestas ou links). G = (V, E)

Ex: (Não direcionado)

Imagem1naodirecionado

(Direcionado)

Imagem2direcionado

Os vértices(rotas) de um grafo podem ter um peso especifico, que seria o custo por passar naquele vértice especifico. Esses grafos são chamados de ponderados, pois possuem valores em seus vértices, indicando um respectivo peso para percorrermos o grafo. Podemos por exemplo verificar qual seria a melhor rota saindo de um ponto A até um ponto Z, passando pela rota de menor peso. Ou seja, menor peso pode significar menor custo ou menor tempo de viagem feito por um veiculo.

Abaixo temos um grafo ponderado com vértices e seus respectivos pesos.

grafoponderado

Grafo Ponderado (Vértices de A até H E diversas arestas com seus respectivos pesos)

Um grafo é uma coleção finita e não vazia de vértices e arcos (arestas). Um vértice é um objeto simples que pode ter nome e outros atributos e que representa uma entidade real ou abstrata. Um arco (aresta) é uma conexão entre dois vértices e representa algum relacionamento entre eles. O grau de um vértice é igual ao número de arcos que o conectam.

*Loop: é um arco associado ao par de vértices (vi,vi) – liga um vértice a ele mesmo.
*Arcos paralelos (ou múltiplos): são arcos associados a um mesmo par de vértices.
*Um arco é dito ser incidente aos vértices que ele conecta. Os vértices também são ditos incidentes ao arco e são chamados pontos finais do arco.
*Dois vértices são ditos adjacentes se eles são conectados por um mesmo arco.
*Dois arcos (não paralelos) são adjacentes se eles conectam o mesmo vértice.

Imagem3

A matéria de grafos é extensa, não é nosso objetivo passar por todas as definições e algoritmos de grafos, mas separei alguns links que são importantes para quem estuda ou quer se aprofundar no assunto.

Links:
http://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html
https://pt.wikipedia.org/wiki/Sete_pontes_de_K%C3%B6nigsberg
https://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante

Fonte:
https://pt.wikipedia.org/wiki/Teoria_dos_grafos
http://imasters.com.br/artigo/12512/outros/grafos-e-suas-aplicacoes/?trace=1519021197&source=single
http://tiagomadeira.com/2006/01/grafos-ponderados/

Comentários

comentários

Share this post

No comments

Add yours