Orientador: Pedro José CatuognoDissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação CientíficaResumo: Nesse trabalho são explorados os conceitos iniciais, a história e algumas aplicações importantes da teoria de grafos. Clássicos, como o problema das sete pontes de Königsberg, o problema carteiro chinês, o problema do caixeiro viajante e a coloração de mapas servem de contexto e de apoio para o desenvolvimento da teoria, onde importantes teoremas são apresentados e demonstrados. Também são apresentadas as heurísticas de melhoramento K-OPT, Algoritmos Genéticos e Colônia de Formigas. Com o intuito de servir como material de apoio à introdução do estudo dos grafos, traz algumas sugestões de apresentação do tema e do desenvolvimento das aulasAbstract: This work explores the following initial concepts, the history and some important applications of the graph theory. Classics, like the problem of The Seven Bridges of Königsberg, The Chinese Postman Problem, The Traveling Salesman Problem, and the coloring of maps, serve as surrounding context and as support for the development of the theory, where important theorems are presented and demonstrated. Also are presented the heuristics of K-OPT Improvement, Genetic Algorithms and Ant Colony Optimization. Aiming to serve as a material of support for the introduction of the study of graphs, bringing some suggestions of presentation of the theme and development of classesMestradoMatemática em Rede NacionalMestre