Surgimento dos grafos

Podemos dizer, como Harary, que a teoria dos grafos foi redescoberta muitas vezes; ou, então, que problemas do interesse de diversas áreas foram estudados separadamente e mostraram características semelhantes. Importante, de qualquer modo, é observar que o período transcorrido entre a demonstração de Euler e a última década do século XIX - mais de 150 anos - viu, apenas, o surgimento de alguns poucos trabalhos. Assim é que, em 1847, Kirchhoff utilizou modelos de grafos no estudo de circuitos eléctricos e ao fazê-lo, criou a teoria das árvores, - uma classe de grafos, para caracterizar conjuntos de ciclos independentes. Dez anos mais tarde, Cayley seguiria a mesma trilha, embora tendo em mente outras aplicações, dentre as quais se destaca a enumeração dos isômeros dos hidrocarbonetos alifáticos saturados, em química orgânica. Enfim, Jordan (1869) se ocupou também das árvores, de um ponto de vista estritamente matemático.

Muitos eventos que provaram ser importantes são relacionados com problemas com pouca aplicação prática: Hamilton, em 1859, inventou um jogo que consistia na busca de um percurso fechado envolvendo todos os vértices de um dodecaedro regular, de tal modo que cada um deles fosse visitado uma única vez. É interessante, aliás, observar que os problemas de Hamilton e de Euler encontraram aplicação, respectivamente um e dois séculos mais tarde, no campo da pesquisa operacional. Kempe (1879) procurou, sem sucesso, demonstrar a "conjectura das quatro cores", apresentada por Guthrie a De Morgan, provavelmente em 1850. Este problema, um dos mais importantes já abordados pela teoria dos grafos, oferece interesse apenas teórico: trata-se de provar que todo mapa desenhado no plano e dividido em um número qualquer de regiões pode ser colorido com um máximo de quatro cores sem que duas regiões fronteiriças recebam a mesma cor. Taity (1880) divulgou também uma "prova", infelizmente baseada numa conjectura falsa e Heawood (1890) mostrou que a prova de Kempe estava errada, obtendo no processo uma prova válida para 5 cores; a prova para 4 cores somente foi obtida em 1976. A importância do problema reside nos desenvolvimentos teóricos trazidos pelas tentativas de resolvê-lo, as quais enriqueceram a teoria dos grafos em diversos recursos ao longo da primeira metade do século XX: exemplificando, Birkhoff (1912) definiu os polinómios cromáticos; Whitney (1931) criou a noção de grafo dual e Brooks (1941) enunciou um teorema fornecendo um limite para o número cromático de um grafo.

Outros eventos importantes podem ser citados: Menger (1926) demonstrou um importante teorema sobre o problema da desconexão de itinerários em grafos e Kuratowski (1930) encontrou uma condição necessária e suficiente para a planaridade de um grafo. Turán (1941) foi o pioneiro do ramo conhecido como teoria extremal de grafos e Tutte (1947) resolveu o problema da existência de uma cobertura minimal em um grafo. Vale a pena registrar que o termo grafo foi usado pela primeira vez por Sylvester em 1878 e que o primeiro livro específico sobre grafos foi publicado por Konig em 1936, uma época na qual, conforme Wilder, o assunto era considerado "um campo morto".

A partir de 1956, com a publicação dos trabalhos de Ford e Fulkerson (1956), Berge (1957) e Ore (1962), o interesse pela teoria dos grafos começou a aumentar, crescendo rapidamente no mundo todo: conforme cita Harary, em 1969 foi publicada por J. Turner. A imensa maioria dos livros sobre grafos foi publicada depois de 1970, em grande parte sob a influência das obras de Berge e Harary. O desenvolvimento dos computadores levou à publicação de várias obras dedicadas aos algoritmos de grafos, abrindo assim possibilidades crescentes de utilização aplicada da teoria.

Referência: www.mat.uc.pt/~mcag/FEA2003/Teoria_de_Grafos.doc