Módulo_-_Grafos

Prévia do material em texto

Grafos
Escola de Ciência e Tecnologia
Grafos
1
Miguel Carvalho
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Problemas do Cotidiano
Redes Sociais
GPS
Para o correio. 
Para Viajantes. 
Disciplina:ESD2 2
Para Viajantes. 
Pesquisas Biológicas.
Distribuição de Tarefas.
Recomendações
Engarrafamento.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Um grafo é formado por conjunto de 
vértices (nó) e arestas. 
Teoria de GrafosTeoria de GrafosTeoria de GrafosTeoria de Grafos
Disciplina:ESD2 3
vértices (nó) e arestas. 
Nos computadores um Grafo é 
normalmente representado por sua 
matriz de adjacências.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Teoria de GrafosTeoria de GrafosTeoria de GrafosTeoria de Grafos
Conecta elementos. 
Representado por nó(vértices) e 
arestas.
Possui diversas aplicações reais.
Disciplina:ESD2
Possui diversas aplicações reais.
G(V,E).
Pode ser direcionado ou não 
direcionado.
Grafo Trivial
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Teoria de GrafosTeoria de Grafos-- GrafoGrafoTeoria de GrafosTeoria de Grafos-- GrafoGrafo
V3
Disciplina:ESD2
V1 V2
Grafo Trivial
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Teoria de GrafosTeoria de Grafos-- MultiMulti--GrafoGrafoTeoria de GrafosTeoria de Grafos-- MultiMulti--GrafoGrafo
V3
Disciplina:ESD2
V1 V2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Teoria dos GrafosTeoria dos Grafos-- LaçoLaçoTeoria dos GrafosTeoria dos Grafos-- LaçoLaço
V3
Disciplina:ESD2
V1 V2
V1
V3
V2
Laço
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
ConceitosConceitos-- Matriz de AdjacênciasMatriz de AdjacênciasConceitosConceitos-- Matriz de AdjacênciasMatriz de Adjacências
V3
Disciplina:ESD2
V1 V2 V3
V1 0 1 1
V2 1 0 0
V3 1 0 0
V1 V2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
ConceitosConceitos--CaminhoCaminhoConceitosConceitos--CaminhoCaminho
Disciplina:ESD2
Caminho - seqüência de vértices v1...vj
Diâmetro - maior caminho do grafo
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
ConceitosConceitos--CaminhoCaminhoConceitosConceitos--CaminhoCaminho
Disciplina:ESD2
Caminho - seqüência de vértices v1...vj
Diâmetro - maior caminho do grafo
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
ConceitosConceitos--CaminhoCaminhoConceitosConceitos--CaminhoCaminho
Disciplina:ESD2
Caminho - seqüência de vértices v1...vj
Diâmetro - maior caminho do grafo
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
ConceitosConceitos--CicloCicloConceitosConceitos--CicloCiclo
Disciplina:ESD2
Ciclo - seqüência de vértices v1...vj, tal que 
v1= vj. 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
ConceitosConceitos--CicloCicloConceitosConceitos--CicloCiclo
Disciplina:ESD2
Obs.:
*Acíclico –grafo que não possui ciclo*
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– Comprimento de um caminhoComprimento de um caminhoConceitos Conceitos –– Comprimento de um caminhoComprimento de um caminho
Disciplina:ESD2
Comprimento = 3
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
ConceitosConceitos--Grau de um nóGrau de um nóConceitosConceitos--Grau de um nóGrau de um nó
d=2
d=1
Disciplina:ESD2
Grau máximo = vértice com maior grau
d=1
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos -- TriângulosTriângulosConceitos Conceitos -- TriângulosTriângulos
Disciplina:ESD2
Ciclo de tamanho 3
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos -- CompletosCompletosConceitos Conceitos -- CompletosCompletos
K3
K2
Disciplina:ESD2
Possuem os vértices possuem todas as arestas 
possíveis
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos -- RegularRegularConceitos Conceitos -- RegularRegular
2-Regular
1-Regular
Disciplina:ESD2
Todos os vértices possuem o mesmo grau.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos -- PonderadoPonderadoConceitos Conceitos -- PonderadoPonderado
10
20
55
Disciplina:ESD2
As arestas possuem peso
40 50
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– Grafos DirecionadosGrafos DirecionadosConceitos Conceitos –– Grafos DirecionadosGrafos Direcionados
Sumidouro
Disciplina:ESD2
Fonte
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– SubgrafoSubgrafoConceitos Conceitos –– SubgrafoSubgrafo
Disciplina:ESD2
subgrafo
Clique – Subgrafo completo
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– IsomorfismoIsomorfismoConceitos Conceitos –– IsomorfismoIsomorfismo
a b f e
Disciplina:ESD2
dc hg
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– BipartidoBipartidoConceitos Conceitos –– BipartidoBipartido
Disciplina:ESD2
Um grafo é bipartido se somente se não possui ciclo 
impar.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– ConexoConexoConceitos Conceitos –– ConexoConexo
Disciplina:ESD2
Conexo – existe um caminho entre todos os pares de 
vértices.
Desconexo – grafo não conexo.
Biconexo - para qualquer dois vértices existe dois 
caminhos distintos entre eles.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– ÁrvoresÁrvoresConceitos Conceitos –– ÁrvoresÁrvores
�Grafo Conexo
�Acíclico
�V = E +1 
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– ConexoConexoConceitos Conceitos –– ConexoConexo
Disciplina:ESD2
Articulação – vértices que quando removido desconecta 
o grafo.
Ponte - aresta que quanto removida desconecta o 
Grafo. Em uma árvore todas as arestas são pontes.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– EulerianoEulerianoConceitos Conceitos –– EulerianoEuleriano
Disciplina:ESD2
Passa por cada arestas somente uma vez.
Um grafo é euleriando se somente se possuir todos os 
vértices com grau par
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– HamiltonianoHamiltonianoConceitos Conceitos –– HamiltonianoHamiltoniano
Disciplina:ESD2
Passa por cada vértice um única vez.
Hamiltoniano – condição necessária não possuir 
articulação.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– ColoraçãoColoraçãoConceitos Conceitos –– ColoraçãoColoração
Disciplina:ESD2
Coloração Própria de vértices.
Vértices adjacentes não podem possuir a mesma cor.
Em um grafo bipartido é possível colorir com duas 
cores.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– EmparelhamentoEmparelhamentoConceitos Conceitos –– EmparelhamentoEmparelhamento
Disciplina:ESD2
Arestas de Emparelhamento
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– EmparelhamentoEmparelhamentoConceitos Conceitos –– EmparelhamentoEmparelhamento
e1 e2 e3 e4 Trabalhadores
Disciplina:ESD2
Trabalhadores e Tarefas
t2t1 t4t3
Tarefas
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– PlanaridadePlanaridadeConceitos Conceitos –– PlanaridadePlanaridade
Disciplina:ESD2
Podem ser desenhados em um plano e uma esfera sem 
cruzamento de arestas.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Conceitos Conceitos –– BuscasBuscasConceitos Conceitos –– BuscasBuscas
A B
Disciplina:ESD2
Largura
Profundidade
Algoritmo de Dijkstra
*Algoritmo Guloso*
CD
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Onde estão?Onde estão?Onde estão?Onde estão?
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Onde estão?Onde estão?Onde estão?Onde estão?
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Onde estão?Onde estão?Onde estão?Onde estão?
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Onde estão?Onde estão?Onde estão?Onde estão?
Disciplina:ESD2
Saber quem está com você!!!
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Onde estão?Onde estão?Onde estão?Onde estão?
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICAOnde estão?Onde estão?Onde estão?Onde estão?
Disciplina:ESD2
Análise de Obesidade
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
Disciplina:ESD2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
Disciplina:ESD2
Web 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
IA
Disciplina:ESD2
IA
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise
Banco de 
NoSQL
Disciplina:ESD2
Banco de 
Dados