Tipos de Grafos
Um grafo G = (V, A) é definido por um conjunto de vértices V e um conjunto de arestas A, as quais consistem em pares de vértices contidos em V. Há diversas propriedades fundamentais dos grafos que influenciam na escolha de estruturas de dados utilizadas para representá-los e os algoritmos para analisá-los. Vamos determinar quais são essas propriedades:
Indireto vs. Direto - Um grafo G = (V, A) é indireto se a aresta (x, y) pertencer a A e isso implicar que (y, x) também pertence. Se não, é tido como grafo direto. Ex: Ligações por estradas entre cidades são tipicamente indiretas, porque as estradas são de mão-dupla.
Valorado vs. Não-Valorado - Em grafos valorados, cada aresta (ou vértice) de G é assinalada com um valor numérico, ou peso. Uma aplicação típica são estradas, as quais são valoradas com a distância ou o tempo para percorrê-la. A diferença entre esses tipos é basicamente para encontrar o menor “caminho” entre dois vértices. Também conhecido como ponderado.
Simples vs. Não-Simples – Certos tipos de arestas complicam a tarefa de trabalhar com grafos. Um laço é uma aresta (x, x) envolvendo somente um vértice. Uma aresta (x, y) é múltipla se ocorre mais de uma vez no mesmo grafo. Um grafo que não possui nenhum desses tipos de aresta é chamado Grafo Simples.