Estrutura de dados (grafos)

TRABALHO DE ESTRUTURA DE DADOS

Grafos

Definição para Grafo:

Um Grafo é uma forma de representar relacionamentos que existem entre pares de objetos. Isto é um conjunto de objetos, chamados vértices, juntamente com uma coleção entre pares de vértices. A propósito, esta noção de “grafos” não deve ser confundida com diagrama de barras de funções plots.
Visto de forma abstrata, um grafo (G) é simplesmente um conjunto (V) de vértices e uma coleção (E) de pares de vértices de (V), chamados de arestas. Assim um grafo é uma forma de representar conexões ou relações entre pares de objetos de algum conjunto (V). Alguns livros usam uma terminologia diferente para grafos e referem-se ao que se chama de vértices, como nodos; e ao que se chama de arestas, como arcos. Serão utilizados aqui o termo “vértices” e “arestas”.
As arestas em um grafo podem ser dirigidas ou não- dirigidas. Uma aresta (u,v) é dita dirigida de (u) para (v) se o par (u,v)for ordenado,com (u) precedendo (v).Uma aresta (u,v) é dita não-dirigida se o par (u,v) não for ordenado.

Os grafos são visualizados tipicamente desenhando-se os vértices como ovais ou retângulos e as arestas como segmentos ou curvas conectando pares de ovais ou retângulos. A seguir são apresentados alguns exemplos de grafos dirigidos e não-dirigidos.

Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais econômico. Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos.

Grafos podem ser utilizados também em redes PERT no âmbito do planejamento de projetos. Neste caso, a cada aresta está associado o custo de execução, e as tarefas precedentes de uma outra serão suas afluentes.

Outro exemplo é o