Grafos: teoria, modelos, algoritmos

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. Hoje em dia, a teoria desenvolvida por ele está na base 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. Problemas de administração, de transportes, de comunicações e de relacionamento são estudados com o auxílio de grafos. Os desafios do futuro estão nas grandes redes sem escala, como a Internet, as redes de migração e, provavelmente, o maior de todos os desafios estará no estudo da mais complexa das redes: a rede neural dinâmica do cérebro humano. 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.