introdução a grafos

Introdução histórica , definições , tipos e aplicações sobre Grafos
Introdução Histórica ao conceito de Grafos
O primeiro problema cuja solução envolveu conceitos do que viria a ser teoria dos grafos, denominado "problema das pontes de Königsberg", foi resolvido por Euler em
1736.
Euler chegou a conclusão de que era impossível encontrar essa sequência.
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 são desenvolvidas na área de Pesquisa Operacional.
O problema , baseado na cidade de Königsberg (território da Prússia até 1945, atual Kaliningrado), que é cortada pelo Rio Prególia, onde há duas grandes ilhas que, juntas, formam um complexo que na época continha sete pontes. Discutia-se nas ruas da cidade a possibilidade de atravessar todas as pontes sem repetir nenhuma. 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.
Euler usou um raciocínio muito simples. Transformou os caminhos em retas e suas intersecções em pontos, criando possivelmente o primeiro grafo da história. Então percebeu que só seria possível atravessar o caminho inteiro passando uma única vez em cada ponte se houvesse exatamente zero ou dois pontos de onde saísse um número ímpar de caminhos. A razão de tal coisa é que de cada ponto deve haver um número par de caminhos, pois será preciso um caminho para "entrar" e outro para "sair". Os dois pontos com caminhos ímpares referem-se ao início e ao final do percurso, pois estes não precisam de um para entrar e um para sair, respectivamente. Se não houver pontos com número ímpar de caminhos, pode-se (e deve-se) iniciar e terminar o trajeto no mesmo
Matemática Discreta – Universidade Carioca
Introdução histórica , definições , tipos e aplicações sobre Grafos ponto, podendo esse ser qualquer ponto do grafo.