Resumo da história dos grafos

Resumo da história da teoria dos 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 Leonhard Euler, 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.

Os grafos são usados na área de TI na criação de fluxogramas, redes de comunicação (como redes Lan e WLan) modelos de fluxo de dados, algoritmos de escalonamento, layout de circuitos, algoritmos de pesquisa e ordenação e modelos de máquinas de estado.

Bibliografia:

Link: graphs.ucpel.tche.br/luzzardi/Estruturas_Dados/Euler_Fred.ppt

Link: