Embed Size (px)
Citation preview
1
Prof. Lorí Viali, Dr.
http://www.pucrs.br/famat/viali/
Pesquisa Operacional II
Teoria dos Grafos
01
História
e
Aplicações
da Teoria
dos Grafos
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Com o artigo de Leonhard Euler (1707 –
1783) as As Sete Pontes de Königsberg,
publicado em 1736.
O Início
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Nasceu em Basel, Suíça. Teve aulas particulares
de matemática com Johann Bernoulli.
Em 1727 conseguiu um emprego na seção
médica da Universidade de St Petersburg, mas
no caos que seguiu a morte da imperatriz
Catherine I, conseguiu se mudar para o
departamento de matemática.
Casou, em 1733, e teve 13 filhos, dos quais
apenas 5 sobreviveram até a idade adulta.
Leonhard Euler (1707 – 1783)
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Em 1741 mudou-se para Berlin, onde ficou por
25 anos.
Publicou cerca de 500 livros e artigos em vida
e outros 400 foram publicados postumamente.
Inventou as notações i, π, e, sen, cos, f(x) entre
outras.
Ficou cego, mas tornou-se ainda mais
produtivo, dizia “agora eu tenho menos
distrações”.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
A cidade é cortada
pelo rio Pregel, que a
separa em duas áreas
principais e em duas
grandes ilhas. Existiam
sete pontes conectando
as várias áreas de terras.
As Sete Pontes de Königsberg
2
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Os residentes de Königsberg se perguntavam
se eles poderiam caminhar pelas várias áreas da
cidade cruzando cada uma das pontes uma e
semente uma vez.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Em 1736 Euler tratou do problema das
pontes de Königsberg.
Ele percebeu que não importa o quanto você
caminha em terra ou onde estão as pontes.
Somente importa quantas pontes existem
entre cada porção de terra e em que ordem
elas são cruzadas.
O Problema
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Com essas obervações o problema pode
ser redesenhado da seguinte forma:
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
A sacada de Euler foi perceber que se você
cruza para uma porção de terra, você
também deve voltar.
Assim, para que o caminho seja possível,
deve existir um número par de pontes
iniciando em cada porção de terra (Exceto
para os pontos inicial e final.
Condições para a Solução
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Königsberg foi
pesadamente bombardeada
durante a segunda Guerra.
A cidade foi tomada pelos
russos e renomeada
Kaliningrado.
Duas das sete pontes
foram destruídas.
Pergunta:
O problema épossível agora?
Postscript on Königsberg
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
A Conjectura das Quatro Cores foi
anunciada pela primeira vez em 1852 e
provada apenas em 1976. Ela é um
exemplo de um problema aparentemente
simples, mas de solução complexa. É o
primeiro teorema onde o computador foi
utilizado para prová-lo.
Mapa das Quatro Cores
3
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
A conjectura de que qualquer
mapa pode ser colorido utilizando
semente 4 cores apareceu, inicialmente
em uma carta de Augustus De Morgan (1806-
1871), primeiro professor de Matemática da
Universidade de Londres, para o seu amigo
William Rowan Hamilton (1805-1865).
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Ela foi sugerida a De Morgan
por um de seus alunos, Frederik
Guthrie (1833 – 1886), em 1852,
em nome de seu irmão mais velho Francis
Guthrie (1831 – 1899) (que mais tarde
tornou-se professor de matemática da
Universidade de Cape Town).
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Esquema original de De Morgan na carta
enviada a Hamilton sobre o mapa das quatro cores.
Um mapa de quatro cores representado como
um grafo.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IExemplo
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Um exemplo simples mostra que é
impossível sempre colorir um mapa com
apenas três cores.
Por quê não três Cores
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Foi provado em 1890 que qualquer mapa
pode ser colorido com no máximo 5 cores.
A parte difícil do problema foi mostrar que
não existe mapa suficientemente complicado
que precise de 5 cores.
Martin Gardner criou o mapa seguinte como
um problema para os seus leitores. Você pode
colorí-lo com semente 4 cores?
Por quê não Cinco Cores
4
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IO Mapa de Martin Gardner
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
O problema das 4 cores pode ser colocado em
termos de grafos.
Cada região do mapa torna-se um nodo, com
dois nodos sendo conectados por uma aresta
se e somente se elas são adjacentes no mapa.
O problema torna-se então: é possível colorir
os nodos com 4 cores de modo que cada aresta
nunca conecte dois nodos da mesma cor?
Em Termos de Grafos
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IExemplo de Grafo de um Mapa
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Em 1976 os matemáticos Kenneth Appel
(1932 – 2013) e Wolfgang Haken (1928 - )
anunciaram que tinham uma prova da conjectura.
A Prova
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Eles criaram um programa computacional
para verificar todos os possíveis exemplos de
mapas (1936 ao todo!).
Esse foi o primeiro teorema matemático que
foi provado com o auxílio do computador e
levantou muita controvérsia.
Um Resultado Controverso
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Um crítico disse:
“Uma boa prova matemática é como um
poema. Essa é um catálogo telefônico!”
Contudo, a prova é agora amplamente aceita
e os computadores são utilizados em muitas
áreas da matemática pura.
Um Resultado Não Elegante
5
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
O irlandês Sir William Rowan
Hamilton (1805 –1865) foi
Astrônomo, Físico e Matemático.
Ele fez importantes contribuições para a
Mecânica Clássica, Ótica e Álgebra. Na
Matemática ele é conhecido por inventar os
Quatérnios.
Ciclos em Poliédros
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Exemplo de um ciclo
Hamiltoniano em um dodecaedro.
Como todos os sólidos Platônicos o
dodecaedro é Hamiltoniano.
O grafo de Herschel é o
menor grafo poliédrico que
não apresenta um ciclo
Hamiltoniano.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Em 1853, Thomas Penyngton
Kirkman (1806 – 1895), começou
a trabalhar com problemas sobre
poliédros, iniciando com a prova
da fórmula de Euler. Ele estudou os
ciclos Hamiltonianos e apresentou um exemplo
de um poliédro sem um ciclo Hamiltoniano antes
do trabalho de Hamilton sobre o jogo Icosiano.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Em 1847, Gustav Kirchhoff
(1824 – 1887), utilizou a teoria
dos grafos para fazer a análise
de circuítos resistivos.
Circuitos Elétricos
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
A fórmula foi descoberta inicialmente por
Carl Wilhelm Borchardt (1817 – 1880), em 1860,
que a provou por meio de um determinante. Em
uma pequena nota, em 1889, Cayley estendeu a
fórmula em várias direções, considerando o grau
dos vértices. Embora ele tenha citado o artigo de
Borchardt a fórmula acabou levando o seu nome.
Fórmula de Cayley
6
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
A fórmula de Arthur Cayley
(1821 – 1895) mostra que para cada
inteiro positivo n, o número de
árvores com n vértices identificados é
nn-2. A fórmula é equivalente a contar
o número de árvores de um grafo
completo com vértices identificados
(sequência A000272 na OEIS).
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Para n = 2, tem-se 22-2 = 20 = 1. Para n = 3,
tem-se 33-2 = 31 = 3 e para n = 4, tem-se 44-2 =
42 = 16 árvores com quatro vértices.
Exemplo
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
James Joseph Sylvester (1814 –
1897) matemático inglês. Fez
contribuições para a teoria das matrizes,
dos números, das partições e da
combinatória. Ele representou partições
de números por nodos de um grafo.
Teoria dos Números
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Sylvester e Cayley foram os pioneiros da
utilização da teoria dos grafos na Química,
isto é, na representação de moléculas de
substâncias. Como exemplo, a figura
(próxima lâmina) apresenta o grafo de uma
molécula de açúcar (C12H22O11).
Grafos em Química
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IExemplo
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
George Pólya (1887 – 1985) foi um
matemático húngaro e professor de
matemática no ETH Zurique de 1914 a 1940 e
da Universidade de Stanford de 1940 a 1953.
Fez contribuições para a combinatória, a
teoria dos números, a probabilidade, a
heurística e a educação matemática.
Enumeração
7
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
O teorema da enumeração de
Pólya pode ser utilizado para calcular
o número de isomorfismos de um
grafo com um número fixo de
vértices ou a função geradora desses
grafos de acordo com o número de
arestas que eles possuem.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
O número de grafos rotulados e não
direcionados de n vértices é 2n(n-1)/2;
O número de grafos rotulados e
direcionados de n vértices é 2n(n-1);
O número de grafos conectados, rotulados
e não direcionados satisfaz a seguinte relação:
Exemplo
C2 k
nkC k2
k-n1n
1kn
−
=
∑
=
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Os valores de Cn são para n = 1, 2, 3, ...
1, 1, 4, 38, 728, 26 704, 1 866 256, ...
que é a sequência A001187 na OEIS.
https://oeis.org/A001187
Exemplos de Grafos
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IRede de Amigos
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IColaboração Científica
8
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IRede Sociais
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IRedes de Transportes
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IInternet
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IModelos Químicos
Aplicações
dos
Grafos
9
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Representar um problema como um grafo
pode:
fornecer um ponto de vista diferente;
torná-lo mais simples;
ser um recurso apropriado para resolver o
problema.
Representação por um grafo
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Um caixeiro viajante necessita visitar
várias cidades dentro de sua área de vendas.
As cidades estão conectadas (aos pares) por
rodovias. Como determinar uma viagem
circular (com volta ao ponto de partida) de
forma que cada cidade seja visitada apenas
uma vez?
Caixeiro Viajante
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
O problema foi
apresentado, inicialmente em
1800, pelo matemático irlandês
Hamilton e cresceu muito em
popularidade nos anos de 1950
e 1960. Iniciou com o jogo do
Icoságono.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IO jogo do icoságono
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IA versão para viagem
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Este era o poster de
uma versão do concurso
da Proctor & Gamble
em 1962. Existiam 33
cidades no problema.
10
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Diferentemente do Problema do Carteiro
Chinês, ninguém encontrou um algortimo
geral para resolver o PCV (Problema do
Caixeiro Viajante) ou o TSP (Travelling
Salesman Problem).
Um Problema Tentador!
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Encontrar a rota mais curta, dado um
determinado número de cidades, é um
problema NP-completo.
Encontrar um bom algoritmo está valendo
atualmente $1 milhão!
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Força Bruta – tentar todas as possíveis
rotas e encontrar a mais curta.
Limitação: utilizando o supercomputador
mais rápido existente o problema
envolvendo 33-cidades levaria 100 trilhões
de anos!
Métodos de solução
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Algoritmo Branch and Bound: dividir o
problema em pequenos grafos e tentar eliminar
arestas que não podem ser parte da solução.
O recorde obtido com este tipo de método
exato foi com 85900 cidades e levou 126 anos
de CPU para ser realizado em 2006.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Heurística: encontrar boas soluções que
tenham alta probabilidade de estarem
próximas da solução ideal. Por exemplo:
O algoritmo do vizinho mais próximo.
Permite que o vendedor escolha a cidade mais
próxima todas as vezes.
Encontrar qualquer rota e então rearanjar as arestas
para encontrar a mais curta.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Heurística: algoritmos podem encontrar a
solução para o PCV com milhões de cidades
em pouco tempo.
Limitação: estas soluções podem não ser a
melhor possível.
11
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Pessoas são surpreendente boas para
encontrar soluções aceitáves para o PCV
rapidamente.
Jogue o seguinte jogo online para ver o
quão bom você é!
http://www.tsp.gatech.edu/games/tspOnePlayer.html
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
O PCV tem muitas aplicações:
– Logística na distribuição de mercadorias;
– Furar placas de circuitos eletrônicos;
– Sequenciamento do Genoma;
– Programação de telescópios como Hubble;
– Elaborar itinerários de viagens;
– Cristalografia de raio-X.
Aplicações do PCV
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
A ECT mantém vários pontos de coleta
e o motorista tem que coletar passando por
todos os postos. Como modelar o problema?
Como encontrar a melhor rota?
Coleta de Correspondência
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Selecionar caminho de menor custo, para o
transporte de uma carga, entre duas cidades
quaisquer.
Caminho do Custo Mínimo
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Uma rede de computadores que interligue
um grande número de instituições
(ensino/pesquisa). Em algumas cidades há um
POP (Ponto de Presença). Havendo mais de uma
rota possível entre dois
POPs como determinar
qual a rota mais
apropriada?
Problema da RNP
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Três canibais e três missionários precisam
atravessar um rio. O barco tem capacidade para
duas pessoas. O número de canibais não pode
ser maior que o número de missionários em
qualquer margem. Como realizar a travessia?
Canibais e Missionários
12
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Projeto de redes de
computadores onde os vértices são
máquinas e as arestas são as
conexões entre duas máquinas
mais o custo. Qual a possibilidade
de comunicação a um custo
mínimo
Rede de Computadores
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
É possível conectar cada serviço a cada uma
das três casas sem haver cruzamento de
tubulações?
Casas e serviços
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Frequentemente temos um conjunto de
pontos e queremos encontrar a menor
coleção de arestas que os conecte. Por
exemplo:
– Estradas e linhas férreas conectando cidades;
– Cabos de telefone e Internet;
– Tubulações de gás;
– Conexões em circuítos eletrônicos.
Construindo o Menor Grafo
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Suponha que temos 4 cidades que devem ser
conectadas. Qual dos grafos abaixo é o menor?
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Se ficarmos restritos a estradas entre
cidades, então o primeiro grafo é o menor.
Mas existe uma solução melhor, que
consiste em utilizar um pouco de plástico
transparente e algumas bolhas de sabão …
Uma solução inesperada
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Assim a melhor solução é criar duas
cidades fantasmas!
Grafo de
Steiner
As bolhas sabem mais
13
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IComo elas fazem?
Atualmente não existe uma algoritmo
(rápido) para encontrar o menor grafo de
Steiner entre um dado número de pontos.
A natureza, por outro lado, é muito boa em
fazê-lo.
https://www.youtube.com/watch?v=52wVrtA5krY
https://www.youtube.com/watch?v=YdneSMKObls
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Suponha agora que as cidades e as estradas
são fixas e que conhecemos as distâncias
entre elas. O problema do carteiro chinês é
determinar a menor rota, que envolva cada
estrada ao menos uma vez, e retorne ao
ponto de partida.
O Carteiro Chinês
3
4
5
6
98 8
5
9
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
A solução consiste em verificar se o grafo é
Euleriano (isto é, com um número par de
arestas saindo de cada nodo), então cada
aresta pode ser visitada uma única vez e o
problema está resolvido.
A Solução
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Se o grafo não for Euleriano então é
preciso encontrar a menor distância entre
os nodos com um número ímpar de arestas
e acrescentar uma aresta extra para torná-
lo um grafo Euleriano.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
3
4
5
6
98 8
5
9
A
B C
D
EF
Exemplo
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
O Google vê a Internet como um grafo
gigante.
Cada página da rede é um nodo e duas
páginas estão conectadas por uma aresta se
existe um link entre elas.
A Internet para o Google
14
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Nota: as arestas no grafo do Google tem
uma direção.
O algoritmo que o Google utiliza para
classificar suas buscas é denomindo de
PageRank.
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Teorema: quanto mais links uma página tiver
apontando para ela mais importante ela será.
Lema: se uma página importante tem um link
para a tua página, isso vale mais do que se for
uma página qualquer.
Exemplo: se a Wikipedia tiver um link para a
tua página, isso vale mais do que um link da
página “Catando Coquinhos”.
O Page Rank
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte IExemplo
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Pessoas que entendem o PageRank podem
torná-lo bastane lucrativo.
Por exemplo, pode-se vender links de uma
página com alto Page Rank para aquelas que
querem aumentá-lo.
Algumas empresas utilizam algoritmos
semelhantes para classificar universidades em
realação ao Mercado de trabalho.
O PageRank e o lucro
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Cientistas estudaram o caminho do limo
crescendo em uma região similar a Tóquio.
Eles colocaram alimento para o limo onde
estavam as maiores cidades.
A rede de limo que se formou foi muito
semelhante a linha de trens de Tóquio.
Caminho do Limo
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Em alguns aspectos ela foi até melhor!
Conclusão: a natureza é mais inteligente
que os politicos.
15
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Grafos também são importantes para redes
sociais como o Facebook.
Pela análise das preferências dos amigos e das
páginas que você curte, a rede pode direcionar
sua publicidade de forma mais eficiente.
Redes Sociais
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
Empresas como a Amazon utilizam grafos
para fazer sugestões, aos seus clientes,
sobre compras futuras.
Em 2009 a empresa americana Netflix
ofereceu $1 milhão para quem melhorasse
o seu algoritmo de recomendação.
Recomendações
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
ALDOUS, Joan M., WILSON, Robin J. Graphs
and Applications. An Introductory Approach.
New York (NY): Springer, 2000.
WASSERMAN, Stanley, FAUST, Katherine. Social
Network Analysis. Cambridge University Press,
2008.
WILSON, Robin. Four Colours Suffice: How the
Map Problem Was Solved. Penguin Books,
2003.
Referências
Prof. Lorí Viali, Dr. – PUCRS – FAMAT: Departamento de Estatística
Curso: Engenharia de
Produção – Teoria dos
Grafos – Parte I
ESTRADA, Ernesto. University of Strathclyde.
www.estradalab.org.
Teorema das 4 cores: http://nrich.maths.org/6291
Site sobre o problema do caixeiro viajante:
http://www.tsp.gatech.edu/
Artigo do jornal New York Times sobre o prêmio
oferecido pela NetFlix: http://www.nytimes.com/
2008/11/23/magazine/23Netflix-t.html
