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 antigaPrussia, hoje chamada Kaliningrado, na atual Rússia.
Haviam sete pontes interligando as partes da cidade que era cortadas por vertentes do rio Pregel formandouma 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 modelosimplificado 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 pontoinicial. 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 grafosentã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 Lane 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: http://www.uesc.br/colegiado_matematica/materialdidatico/disserta.pdf [continua]

Ler trabalho completo

Citar Este Trabalho

APA

(2012, 08). Resumo da história dos grafos. TrabalhosFeitos.com. Retirado 08, 2012, de http://www.trabalhosfeitos.com/ensaios/Resumo-Da-Hist%C3%B3ria-Dos-Grafos/334147.html

MLA

"Resumo da história dos grafos" TrabalhosFeitos.com. 08 2012. 2012. 08 2012 <http://www.trabalhosfeitos.com/ensaios/Resumo-Da-Hist%C3%B3ria-Dos-Grafos/334147.html>.

MLA 7

"Resumo da história dos grafos." TrabalhosFeitos.com. TrabalhosFeitos.com, 08 2012. Web. 08 2012. <http://www.trabalhosfeitos.com/ensaios/Resumo-Da-Hist%C3%B3ria-Dos-Grafos/334147.html>.

CHICAGO

"Resumo da história dos grafos." TrabalhosFeitos.com. 08, 2012. Acessado 08, 2012. http://www.trabalhosfeitos.com/ensaios/Resumo-Da-Hist%C3%B3ria-Dos-Grafos/334147.html.