28
Grafos Histórico, exemplos e problemas

Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Embed Size (px)

Citation preview

Page 1: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Grafos

Histórico, exemplos e problemas

Page 2: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Pontes de KönigsbergKönigsberg, Prússia (atual Калинингра$ д), Rússia

Page 3: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Pontes de KönigsbergÉ possível cruzar cada ponte uma única vez e

voltar ao ponto de partida?

Page 4: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Pontes de KönigsbergÉ possível cruzar cada ponte uma única vez e

voltar ao ponto de partida?

Page 5: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Pontes de KönigsbergNinguém conseguia uma solução. Alguns

achavam que era impossível.

Page 6: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Leonhard Euler (“Óiler”)• Um dos matemáticos mais

produtivos da história– 13 filhos– mais de 800 artigos publicados

• séries – Cálculo• equações diferenciais – Cálculo e

Cálculo Numérico

– Ficou cego e continuou escrevendo artigos por mais 17 anos até sua morte

Page 7: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

– Resolvido em 1736 por Leonhard Euler

– Necessário um modelo para representar o problema

– Abstração de detalhes irrelevantes:• Área de cada ilha• Formato de cada ilha• Tipo da ponte, etc.

Pontes de Königsberg

Page 8: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Pontes de Königsberg• Euler demonstrou que o problema das pontes de

Königsberg não tem solução• Ele usou um modelo simplificado das ligaçõesentre as regiões• Euler usou um raciocínio muito simples. Transformou os

caminhos em retas e suas intersecções em pontos criando possivelmente o primeiro grafo da história.

Page 9: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Pontes de Königsberg

• Então percebeu que só seria possível atravessar o caminho inteiro passando uma única vez em cada ponte se houvesse no máximo dois pontos de onde saia um número ímpar de caminhos.

• A razão de tal coisa é: de cada ponto deve haver um número par de caminhos, pois será preciso um caminho para "entrar" e outro para "sair".

• Os dois pontos com caminhos ímpares referem-se ao início e ao final do percurso, pois estes não precisam de um para entrar e um para sair, respectivamente

Page 10: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Pontes de Königsberg• Euler estabeleceu um teorema que diz em que

condições é possível percorrer cada linha exatamente uma vez e voltar ao ponto inicial– Foi o primeiro teorema da Teoria dos Grafos

Page 11: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Pontes de Königsberg

• Como os graus de todos os vértices são impares, é fácil verificar que este grafo não apresenta nem uma trilha, nem um ciclo euleriano, visto que ele não satisfaz o teorema de euler, nem tampouco é um grafo atravessável. Logo, a travessia proposta não é possível.

– Teorema de euler: Um multigrafo M é euleriano se e somente se M é conexo e cada vértice de M tem grau par.

– Teorema de grafo atravessável: Um multigrafo M é atravessável se e somente se M é conexo e tem exatamente dois vértices de grau impar. Consequentemente, qualquer trilha euleriana de M começa em um dos vértices de grau impar e termina no outro vértice de grau impar.

Page 12: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

• Euler mostrou que não existe o trajeto proposto utilizando o modelo em grafos

• Verifique nos grafos abaixo se o trajeto proposto é possível

Pontes de Königsberg

Page 13: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Mais história• Um século sem estudos em grafos

• Leis de Kirchoff (Kirchoff, 1847)

• Problema das 4 cores (De Morgan, 1852)

• Aplicações em Química orgânica (Cayley, 1857)

• Problema do ciclo Hamiltoniano (Hamilton 1859)

Page 14: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

• É possível conectar os 3 serviços às 3 casas sem haver cruzamento de tubulação?

água luz telefone

A teoria dos grafos mostra que não é possível

O problema das 3 casas

Page 15: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Mapas

• Quantas cores são necessárias?

Page 16: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Mapas

• Quantas cores são necessárias?

Page 17: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Questões sobre o caminho mínimo

• De forma a reduzir seus custos operacionais, uma empresa de transporte de cargas deseja oferecer aos motoristas de sua frota um mecanismo que os auxilie a selecionar o melhor caminho (o de menor distância) entre quaisquer duas cidades por ela servidas, de forma a que sejam minimizados os custos de transporte.

Page 18: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

• Estamos interessados em objetos e nas relações entre eles

• Quem são eles nos problemas apresentados?

• Como representar graficamente?

Modelagem com grafos

Page 19: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Modelagem com grafos

No problema das casas– Vértices são casas e serviços– Arestas são as tubulações entre casas e serviços

• No problema da coloração de mapas– Vértices são estados– Arestas relacionam estados vizinhos

• No problema do caminho mais curto– Vértices são as cidades– Arestas são as ligações entre as cidades

Page 20: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Três desenvolvimentos isolados despertaram o interesse pela área

• Formulação do problema das 4 cores (De Morgan 1852).

• Qual a quantidade mínima de cores para colorir um mapa de tal forma que países fronteiriços possuam cores diferentes?

• Apresenta-se um exemplo em que 3 cores não são suficientes. Uma prova de que 5 cores é suficiente foi formulada. Conjecturou-se então que 4 cores seriam suficientes. Esta questão ficou em aberto até 1976 quando Appel e Haken provaram para 4 cores.

Page 21: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Três desenvolvimentos isolados despertaram o interesse pela área

• Problema do ciclo Hamiltoniano (Hamilton 1859)

Existem n cidades. Cada par de cidades pode ser adjacente ou não arbitrariamente. Partindo de uma cidade qualquer, o problema consiste em determinar um trajeto que passe exatamente uma vez em cada cidade e retorne ao ponto de partida.

Page 22: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Três desenvolvimentos isolados despertaram o interesse pela área

• Teoria das árvores

     - Kirchoff (1847) - problemas de circuitos elétricos

     - Cayley (1857) - Química Orgânica

Page 23: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Então, o que é um grafo?• Informalmente, um conjunto de objetos e

ligações (relações) entre eles

• Alguns chamam de rede

• Muitas vezes representado graficamente (pontos e linhas)

• Os objetos são chamados de vértices e as

• ligações, de arestas

Page 24: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

O que são Grafos

• Diagrama - Corresponde a soma de pontos e linhas, onde os pontos apresentam alguma informação e as linhas indicam o relacionamento entre dois pontos quaisquer

• Ferramenta de modelagem• Abstração matemática que representa situações

reais através de um diagrama.

Page 25: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Grafo vs gráfico• Um grafo pode ser representado graficamente de

diversas maneiras

Page 26: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Grafo vs gráfico• O que importa são as relações que existem entre os

vértices

Page 27: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

– Importante ferramenta matemática com aplicação em diversas áreas do conhecimento • Genética, química, pesquisa operacional,

telecomunicações, engenharia elétrica, redes de computadores, conexão de vôos aéreos, restrições de precedência, fluxo de programas, dentre outros

– Utilizados na definição e/ou resolução de problemas

Porque estudar Grafos ?

Page 28: Grafos Histórico, exemplos e problemas. Pontes de Königsberg Königsberg, Prússia (atual Калинингра́д), Rússia

Porque estudar Grafos

– Em computação: estudar grafos é mais uma forma de solucionar problemas computáveis

– Os estudos teóricos em grafos, buscam o desenvolvimento de algoritmos mais eficientes.