Apresentação Grafos (1)

Prévia do material em texto

Grafos
Análise e Projeto de Algorítimos
Professor: Sidney Doria
Alunos: Lucival Santana e Juvenal dos Santos
O Que São Grafos ?
Formalmente, um grafo é uma colecção de vértices (V) e uma colecção de arcos (E) constituídos por pares de vértices.
O Que São Grafos ?
Podendo fazer uma analogia, os vértices podem ser pontos ou locais e os arcos também conhecido como arestas, podem ser relacionados aos caminhos que ligam esses pontos.
Aplicações
Ajudar máquinas de busca a localizar informação relevante na Web.
Descobrir os melhores casamentos entre posições disponíveis em empresas e pessoas que aplicaram para as posições de interesse.
Descobrir qual é o roteiro mais curto para visitar as principais cidades de uma região turística.
Aplicações
Linhas Aéreas 
Vantagens
Desvantagens
Conceitos Básicos
Grafo: Conjunto de vértices e arestas.
Vértices: Objeto simples que pode ter nome e outros atributos.
Arestas: Conexão entre dois vértices.
Conceitos Básicos
Notação: G = (V,A)
G: grafo
V: conjunto de vértices
A: conjunto de arestas
Grafos Direcionados
Um grafo direcionado G é um par (V,A), onde V é um conjunto finito de vértices e A é uma relação binária em V.
Uma aresta (u, v) sai do vértice u e entra no vértice v. O vértice v é adjacente ao vértice u.
Grafos Direcionados
Podem existir arestas de um vértice para ele mesmo, chamadas de self-loops.
Grafos Não Direcionados
Grau de um Vértice
Caminho entre Vértices
Ciclos
Componentes Conectados
Componentes Fortemente Conectados
Grafos Isomorfos
Subgrafos
Versão Direcionada de um Grafo Não Direcionado
Versão Não Direcionada de um Grafo Direcionado
Outras Classificações de Grafos
Grafos Completos
Árvores
Operadores do TAD Grafo
Obter Lista de Adjacentes
Matriz de Adjacência
Busca em Profundidade
Busca em Largura
Código de Demonstração
FIM!