Teoria dos Grafos Introdução - ppt carregar
Teoria dos Grafos Introdução
PublicouCamille Coval Alterado mais de 3 anos atrás
Apresentação em tema: "Teoria dos Grafos Introdução"— Transcrição da apresentação:
1 Teoria dos Grafos Introdução
Matemática Discreta – if670 Anjolina Grisi de Oliveira Ciência da Computação Colaboração: lnpa e ljacs Teoria dos Grafos Introdução
2 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 voos aéreos, restrições de precedência, fluxo de programas, dentre outros. Utilizados na definição e/ou resolução de problemas.
3 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.
4 O que são grafos? Tipicamente um grafo é representado como um conjunto não vazio de pontos ou vértices ligados por retas, que são chamadas de arestas; Ferramenta de modelagem; Abstração matemática que representa situações reais através de um diagrama.
5 Problemas solucionados com a teoria dos grafos
O rio Pregel divide o centro da cidade de Königsberg (Prússia no século XVII, atual Kaliningrado, Rússia) em quatro regiões. Essas regiões são ligadas por um complexo de sete (7) pontes, conforme mostra a figura; Discutia-se nas ruas da cidade a possibilidade de atravessar todas as pontes, voltando ao lugar de onde se saiu, sem repetir alguma. Havia-se tornado uma lenda popular a possibilidade da façanha quando Euler, em 1736, provou que não existia caminho que possibilitasse tais restrições.
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.
Euler generalizou o problema através de um modelo de grafos.
10 As 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
11 A teoria dos grafos mostra que não é possível!
12 Coloração de Mapas Quantas cores são necessárias para colorir o mapa do Brasil, sendo que estados adjacentes não podem ter a mesma cor?
13 Questões sobre o caminho mínimo
15 Modelagem com grafos Estamos interessados em objetos e nas relações entre eles; Quem são eles nos problemas apresentados? Como representar graficamente?
16 Modelagem com grafos No problema das casas
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.
18 Três desenvolvimentos isolados despertaram o interesse pela área
19 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