Uma Introdução Sucinta à Teoria dos Grafos

Livro digital

Título:
Uma Introdução Sucinta à Teoria dos Grafos

Autor:
Paulo Feofiloff, Yoshiharu Kohayakawa, Yoshiko Wakabayashi

Categoria:
Tecnologia > Dados

Doador:
Raffaello D. N.

Sinopse:
Se você já ouviu falar em teoria dos grafos mas sentiu que faltava um ponto de partida — ou se já tropeçou em problemas de caminho mínimo, coloração de mapas e emparelhamentos sem saber como formalizá-los — este livreto dos professores Feofiloff, Kohayakawa e Wakabayashi (IME-USP) é provavelmente a introdução mais enxuta e honesta que você vai encontrar. Em vez de prometer um panorama enciclopédico, o texto foca quatro temas que se desdobram naturalmente: conjuntos estáveis e cliques, coloração de vértices, emparelhamentos e coloração de arestas. Cada capítulo constrói o próximo. O livro começa pelos fundamentos — isomorfismo, vizinhanças, cortes, caminhos e circuitos, subgrafos, conexidade — e já no primeiro capítulo introduz grafos aleatórios, um tópico que poucas introduções abordam. Depois mergulha em delimitações superior e inferior para conjuntos estáveis máximos, passando pelo índice de estabilidade e pelo número cromático da maioria dos grafos (uma seção rara em textos introdutórios). Na segunda metade, emparelhamentos em grafos bipartidos e arbitrários, coloração de arestas com delimitação de Vizing, e um fechamento com considerações computacionais em cada etapa. O que faz este texto especial é a honestidade intelectual: cada definição vem acompanhada de exemplos concretos (grafo da dama, grafo do cavalo no xadrez), os exercícios são etiquetados por dificuldade — incluindo problemas em aberto com prefixo A — e há apêndices que salvam a vida como um dicionário de termos técnicos e o alfabeto grego. Você sai sabendo não só o que é um grafo, mas como pensar combinatoriamente sobre ele. Para estudantes de ciência da computação, matemática ou engenharia que querem a base sem rodeios.