Introducción a la teoría de las gráficas

Abstract

La Teoría de las Gráficas es una rama de las Matemáticas Discretas que en los últimos años ha tenido un gran desarrollo, probablemente debido a la enorme cantidad de aplicaciones que estas tienen. Se considera que tiene su inicio en 1736 cuando Leonhard Euler [16] publicó Solutio problematis and geometrian situs pertinentis en donde aparece la solución al famoso Problema de los Puentes de Königsberg. Durante el siglo XIX la Teoría de las Gráficas fue redescubierta a través del estudio de diversos problemas obteniendo así nuevos y más resultados importantes. Por ejemplo, Arthur Cayley [11] en 1857, mientras estudiaba la cantidad posible que podía haber de ciertas estructuras químicas, descubrió una importante familia de gráficas, a las que llamó árboles. Aunque poco a poco iba aumentando el interés en ésta área, fue hasta 1936 cuando el húngaro Dénes König [26] publicó el primer libro sobre este tema. Así que podemos decir que la Teoría de las Gráficas es un área muy joven dentro del mundo de las matemáticas, sobre todo si la comparamos con la antigüedad de otras áreas como la Geometría o el Álgebra. El objetivo de este libro es proporcionar a estudiantes de cursos de Teoría de las Gráficas un texto escrito y pensado en español. Ha sido un esfuerzo intentar presentar los temas de este libro de forma simple y rigurosa. Los ejercicios que aparecen al final de cada capítulo forman una parte escencial para reforzar los conceptos, ideas y técnicas utilizadas en cada capítulo, por este motivo es que se recomienda ampliamente resolverlos.