Grafos

O primeiro resultado do que veio a ser a teoria dos grafos passou um século perdido em meio aos setenta grossos volumes da produção científica de Leonhard Euler. À época, o problema das pontes de Königsberg não passava de uma pequena brincadeira sem nenhum interesse prático. Hoje em dia a teoria desenvolvida por Euler está na bese das técnicas utilizadas para especificar rotas de atendimento para serviços a domicílio em cidades; além disso, algo da sua produção no campo da geometria está envolvido, através da teoria dos grafos, com os projetos de circuitos integrados, como os dos computadores. O século XIX viu as primeiras aplicações de grafos, quase ao mesmo tempo na eletricidade e na química. Hoje em dia eles continuam sendo aplicados a circuitos elétricos e eletrônicos e sua utilidade cresceu extraordinariamente no campo da química, auxiliando na definição de índices cujos valores possam ser associados, através das estruturas das moléculas - que são estruturas de grafo - às propriedades das substâncias correspondentes. Indo mais longe ainda, a bioquímica molecular vem utilizando algoritmos de grafos para estudos como os da estrutura do DNA e da composição das proteínas. O primeiro livro de grafos foi publicado há 70 anos: hoje, eles já são centenas. As revistas e os congressos especializados existem por todo o mundo e os trabalhos publicados se contam aos milhares, tanto com motivação teórica, como dentro das especialidades que utilizam em suas aplicações os poderosos recursos da teoria dos grafos. Todo esse potencial, no entanto, não se realiza sem um intenso trabalho, em vista da complexidade dos problemas, tanto do ponto de vista teórico como do computacional. A prova dos teoremas pode apresentar grandes dificuldades, como se observa ao se examinar a trajetória do problema das quatro cores, resolvido computacionalmente - mas ainda não analiticamente - após cerca de um século de tentativas. Em nossa visão, tudo isso é algo de apaixonante, capaz de motivar toda uma carreira profissional, tal como o fez com este autor. Não esperamos tanto dos que recorrerem a este livro - mas desejamos que nele encontrem utilidade, bem como algum caminho que lhes traga as respostas para seus problemas que envolvam grafos; e, também, que o considerem agradável de abrir. Ele se destina a um universo diversificado: até o momento, trata-se do único livro-texto publicado no Brasil sobre o assunto e, em vista disso, seu conteúdo envolve interesses de cursos de graduação e de pós-graduação, bem como de pesquisa teórica e aplicada. Esta diversidade traz como consequência que o seu leitor poderá encontrar nele, ao lado dos temas de seu interesse, outros que não atraiam sua atenção. Por este pequeno inconveniente, o autor apresenta suas desculpas.