4 Grafos - Problemas, Algoritmos e Curiosidades

Prévia do material em texto

Formação Cientista de 
Dados
Grafos: problemas, algoritmos e curiosidades
Caminho de Custo Mínimo
A
B
D
E
C
F
5 4
5
6 6
8
7
7
4
6
Algoritmo de Dijkstra
• Edsger Dijkstra em 1956 e publicado em 1959
• Calcula o custo mínimo para todos os vértices
• Complexidade aumenta se:
• É obrigado a passar por alguns vértices
• É obrigado a evitar alguns vértices
Problema das Pontes de Königsberg
É possível passar nas 7 pontes uma única vez?
Caminho e Circuito Euleriano
Caminho Euleriano: grafo em que cada 
arresta é visitada uma única vez
Circuito Euleriano: caminho Euleriano 
que começa e termina no mesmo vértice.
Grafos Euleriano
TODOS OS VÉRTICES 
PRECISAM SER DE GRAU PAR
CONEXO
Caminho Euleriano
A
B
C
D
A
B D
Carteiro Chinês
• Se o caminho é euleriano, não há problema!
• Se não é, tem-se que buscar a menor repetição 
possível de vértices
Comunidades
• Conjuntos dentro de um grafo
• Detectado através de 
densidade e agrupamentos 
(Clusters)
• Podem ser sobrepostas ou 
não
• Perguntas e problemas:
• Como se criou?
• Esta crescendo ou 
diminuindo?
Cliques
• Tipo especial de 
comunidade
• Um sub-grafo onde cada 
par de nós esta conectado
• Grafos não orientados
“Small world 
phenomenon” e “six 
degree of separation”
By Daniel' (User:Dannie-walker) - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=8977072
Paradoxo da Amizade
• Em média, as pessoas tem 
menos amigos do que seus 
amigos tem
Construa uma ponte!
A
B
C
D
D
A
B
C
D