Grafos e tabelas de dispersão

ANALISE E DESENVOLVIMENTO DE SISTEMAS

GRAFOS, TABELAS DE DISPERSÃO

Bento Gonçalves
2011

GRAFOS, TABELAS DE DISPERSÃO
VOLUME UNICO

Trabalho final da disciplina de
Estrutura de dados, curso de
Analise e desenvolvimento de sistemas, grau B

2011

GRAFOS

Grafo é uma estrutura G(V,A) onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas. Geometricamente marcam-se pontos distintos em um plano para representar os vértices, e uma linha ligando os pontos para representar as arestas.
Os grafos são geralmente representados graficamente da seguinte maneira: é desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco conectando suas extremidades.
Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, grafo orientado ou dígrafo.
Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial ou "o ponto".
Note que essa representação gráfica (o layout) não deve ser confundida com o grafo em si (a estrutura abstrata, não gráfica). Diferentes layouts podem corresponder ao mesmo grafo. O que importa é quais vértices estão conectados entre si por quantas arestas.

Grafos simples
Quando todos os vértices do caminho são distintos, sua sequencia recebe o nome de caminho simples ou elementar, ou seja, é um grafo não direcionado, sem laços e que existe no máximo uma aresta entre quaisquer dois vértices (sem arestas paralelas).
Grafo completo
É um grafo não direcionado no qual todos os pares de vértices são adjacentes, é o grafo simples em que, para cada vértice do grafo, existe uma aresta conectando este vértice a cada um dos demais. Ou seja, todos os vértices do grafo possuem mesmo grau. O grafo