A teoria dos Grafos

Professora: Sonia Ortiz

Alunos:
Alessandra
Mara
Rosangela
Tiago

Rio de janeiro 2013
Introdução
Teoria de Grafos se originou de certa forma, de um desafio proposto pelos habitantes da cidade de Königsberg da antiga Prussia, hoje chamada Kaliningrado, na atual Rússia. O conceito abstrato de grafo e o estudo matemático de suas propriedades foi uma das muitas contribuições do matemático suíço Leonhard Euler (1707–1783). Um quebra-cabeça famoso na época era encontrar um passeio que visitasse todas as pontes da cidade de Konigsberg, passando uma única vez em cada ponte. Euler resumiu as propriedades essenciais do mapa por um diagrama de pontos ligados por linhas.
Apenas analisando esse diagrama abstrato, ele provou que o tal passeio era impossível. Este trabalho (publicado em 1736) é considerado o primeiro artigo da teoria de grafos.
E este foi o primeiro teorema da Teoria dos Grafos, ele provou que havia solução para o desafio.
Mais tarde, Ford e Fulkerson (1962) desenvolveram a teoria dos fluxos em redes, um dos mais importantes resultados da teoria dos grafos, e muitas outras aplicações da teoria dos grafos então vem sendo desenvolvidas na área de Pesquisa Operacional.
Grafos são estruturas muito usadas para representar a existência ou não de relações entre elementos de um dado conjunto. Assim, redes de comunicação, fluxos em rede de transporte, mapas geográficos e relações binárias em geral podem ser representadas por grafos, e nesse caso várias questões de interesse podem ser investigadas.
A Teoria de Grafos se deu por conta de jogo e quebra cabeças.

1-Metodologia

O trabalho será desenvolvido com a definição do conceito de grafos e suas variações as bases utilizadas serão, bibliográficas, livros, artigos e sites.
O uso destes materiais de pesquisa servem para fundamentar o tema, demonstração de exemplos práticos de grafos no cotidiano , e suas diversas aplicações.
.

2-Referencial Teórico

A teoria