Teoria Dos Grafos

EORIA DOS GRAFOS

- A matriz de adjacência de um grafo G=(V,E) é de ordem |V|x|V|

-Grafo não-dirigido e simples a soma dos elementos da matriz é igual

a 2x|E|

- Se o digrafo for simples, a soma dos elementos da matriz

de adjacência deve ser igual a |E|

- Se o grafo for não-dirigido, a soma dos comprimentos das listas

de adjacência é 2x |E|

- Complexidade espacial Lista de Adjacência é O(|V|+|E|) e a de matriz

de incidência é O(|V|x|E|)

Para um grafo a representação por lista de incidência consiste em um

vetor de |E| itens(um ora cada aresta/arco) e um vetor de

|V| itens um pra cada vertice.

- Matriz de incidência é uma matriz esparça por natureza, a de

adjacência não.

- A implementação de listas de adjacência via arranjos aprensenta

vantagem em termos de tempo de acesso.

- Grafos densos são mais adequados para Matriz de Adnjacência e

grafos esparsos são mais adequados para Lista de Adjacência.

A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, 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.

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 digrafo. Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial.