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?
Pontes de Königsberg
É possível cruzar cada ponte uma única vez e
voltar ao ponto de partida?
Pontes de Königsberg
Ninguém conseguia uma solução. Alguns
achavam que era impossível.
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
Pontes de Königsberg
– 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
• Euler demonstrou que o problema das pontes de
Königsberg não tem solução
• Ele usou um modelo simplificado das ligações
entre 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.
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
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
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.
Pontes de Königsberg
• Euler mostrou que não existe o trajeto
proposto utilizando o modelo em grafos
• Verifique nos grafos abaixo se o trajeto proposto é
possível
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)
O problema das 3 casas
• É possível conectar os 3 serviços às 3
casas sem haver cruzamento de tubulação?
A teoria
dos grafos
mostra
que não é
possível
água
luz
telefone
Mapas
• Quantas cores são necessárias?
Mapas
• Quantas cores são necessárias?
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.
Modelagem com grafos
• Estamos interessados em objetos e nas
relações entre eles
• Quem são eles nos problemas
apresentados?
• Como representar graficamente?
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
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.
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.
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
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
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.
Grafo vs gráfico
• Um grafo pode ser representado graficamente de
diversas maneiras
Grafo vs gráfico
• O que importa são as relações que existem entre os
vértices
Porque estudar Grafos ?
– 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
– 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.