Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Prof. Lorí Viali, Dr. viali@mat.pucrs.br 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) foiAstrô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 n kC k2 k-n1n 1k n − = ∑ = 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: Departamentode 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 9 8 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 9 8 8 5 9 A B CD 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
Compartilhar