Graph theory

Teoría de grafos

La base de la teoría de grafos se encuentra en la combinatoria, siendo el rol de los “grafos” el de visualizar cosas. Sus aplicaciones y modelos involucran usualmente conexiones con el “mundo real” por una parte a menudo expresadas en términos gráficos vívidos y métodos computacionales y de definición dados por la combinatoria matemática y la maquinaria algebraica lineal, por otra. Para muchos, esta interacción es lo que hace que la teoría de grafos sea tan interesante. Este escrito es una introducción a los conceptos y resultados básicos en esta área del conocimiento.

Uno de los usos de la teoría de grafos es brindar un formalismo unificado para muchos problemas de tipo muy distinto. Así, esto basta para presentar los algoritmos en este formalismo común. Esto ha llevado al surgimiento de una clase especial, los llamados algoritmos gráficos. La mitad del contenido de este documento se dedica a estos, haciendo énfasis en los métodos teóricos de redes.

An introduction to combinatorics and graph theory

Una introducción a combinatoria y teoría de grafos

A menudo la combinatoria se describe de modo breve como contar; de hecho, contar es una parte importante de ella. Sin embargo, es algo más amplio, tal como el nombre lo sugiere: se refiere a combinar cosas. Las preguntas que surgen implican varios problemas: ¿en cuántas formas se pueden combinar estos elementos?, ¿cierta combinación es posible?, ¿cuál combinación es la mejor?. En este documento se revisarán todos estos interrogantes. Por su parte, la teoría de grafos se relaciona con diversos tipos de redes o modelos de redes llamados grafos, los cuales no son los aquellos de la geometría analítica sino otros que se describen a menudo como "puntos conectados por líneas".