O Corpo Fala (Ricardo Serravalle Guimarães) 101

Estrutura de Dados
Apresentação 06 U5:
Fundamentos de Grafos
Prof. Carlos A. S. Rocha, MSc
E-mail:

Plano de Aula


TAD Grafo;






Características;
Estruturas de Dados para Implementação

Grafos Dirigidos;
Aplicações.

Grafos – Características

Grafos – Características




Um grafo G é representado por um conjunto de vértices V e uma coleção de pares de vértices de V chamados de arestas, denotados por A;
Um grafo é uma forma de representar conexões, ou relações, entre pares de objetos de algum conjunto V.

Grafos – Aplicações






Mapas: Sistemas de Informação Geográfica;
Transporte: conexões aéreas e de estradas;
Redes de Computadores: Internet, redes sociais, tabelas de roteamento;
Engenharia Elétrica: circuitos.

Grafos – Tipos




Um grafo possui suas arestas dirigidas
(ordenadas) ou não-dirigidas (sem ordenação); Uma aresta a dada pelos vértices (u,w) é dita dirigida se u precede w. Já a é não-dirigida se o par (u,w) não for ordenado. Grafos – Tipos






Grafo Não-dirigido: possui todas as suas arestas não-dirigidas;
Grafo Dirigido (Digrafo): possui todas as suas arestas dirigidas;
Grafo Misto: possui arestas não- dirigidas e arestas dirigidas.

Grafos – Exemplos


Grafo Não-dirigido:




Grafo Dirigido (Digrafo):





Rede elétrica e rede de encanamento de um prédio.
Rede elétrica e rede de encanamento de um prédio;
Rede de vôos de um aeroporto.

Grafo Misto:


Ruas de uma cidade.

Grafos – Exemplos

Grafos – Exemplos




Tabelas de roteamento: ?
Redes sociais: ?
Redes de computadores: ?

Grafos – Vértices e Arestas






Vértices Finais (pontos finais): vértices conectados por uma aresta. Em caso de uma aresta dirigida temos: origem e destino;
Vértices Adjacentes: representam pontos finais de uma mesma aresta;
Arestas Incidentes: um aresta incide a um vértice se o vértice for um dos pontos