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