¿QUÉ ES UN GRAFO?

Teoría de grafos :
La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos. En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada). Típicamente, un grafo está diseñado por una serie de puntos (los vértices) conectados por líneas (las aristas).

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado como uno de los primeros resultados de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología. En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos. En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos. 

Los grafos son, como veremos, un lenguaje, una notación, que permite representar relaciones binarias es decir, entre pares de objetos en un conjunto (recordemos la sección 3.5). De una manera informal, podríamos decir que un grafo es una colección de vértices y de aristas que unen estos vértices. Los vértices los dibujaremos como puntos del plano, y las aristas serán líneas que unen estos puntos. Vayamos con las definiciones formales: 

Definición Formal: Un grafo G es un conjunto no vacío V (de vértices) y un conjunto A (de aristas) extraído de la colección de subconjuntos de dos elementos de V. Una arista de G es, pues, un subconjunto {a, b}, con a, b ∈ V , a = b. 

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro. 

Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy legibles. Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un alcantarillado. 

Cibergrafía:

https://www.uam.es/personal_pdi/ciencias/gallardo/capitulo8a.pdf

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0701_Tc1003_TODO_Grafos.pdf