grafos

CENTRO UNIVERSITÁRIO UNICARIOCA

Alexandre Ramos
Romulo Ferreira

DISCIPLINA: MATEMÁTICA DISCRETA
TURMA: 827
TEMA DO TRABALHO: GRAFOS

Rio de Janeiro
2014

1 INTRODUÇÃO HISTÓRICA AO CONCEITO DE GRAFOS
A teoria dos grafos nasceu de certa forma, de um desfio proposto pelos habitantes da cidade de Königsberg da antiga Prussia, hoje chamada Kaliningrado, na atual
Rússia.
Haviam sete pontes interligando as partes da cidade que era cortadas por vertentes do rio Pregel formando uma ilha na parte central.
O desafio consistia em fazer um passeio passando pelas sete pontes, porém uma vez sobre cada ponte.
O matemático suíço LeonhardEuler, em 1736, não só conseguiu elucidar o problema como acabou por criar uma teoria que se aplica a vários problemas deste tipo.
Ele usou um modelo simplificado das ligações entre as regiões e estabeleceu um teorema que diz em que condições são possíveis percorrer cada linha exatamente uma vez e voltar ao ponto inicial. E este foi o primeiro teorema da Teoria dos
Grafos.
Euler provou que não 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.

2 DEFINIÇÃO DE GRAFOS
Pensamos em um grafo como um conjunto de pontos num plano ou no espaço e um conjunto de segmentos ou linhas (possivelmente curvas), sendo que cada linha junta dois pontos ou um ponto para si próprio.
Um grafo G=(V,A) consiste em:



um conjunto finito de pontos V. Os elementos de V dizem-se os vértices de G. um conjunto finito A de pares não ordenados de V, que se dizem as arestas de G. Uma aresta a em A é um par não ordenado {v, w} de vértices v, w em V, que se dizem as extremidades de a. Duas arestas distintas podem ter as mesmas extremidades dizendo-se nesse caso arestas paralelas. Uma aresta com as duas