Grafos

Teoría de los grafos:
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafose representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) o gráfica es el principal objeto de estudio de la teoría de grafos.
Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permitenrepresentar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo,en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.
Un grafo:
Un grafo es un par ordenado , donde:
* es un conjunto de vérticeso nodos, y
* es un conjunto de aristas o arcos, que relacionan estos nodos.
Normalmente suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.
Se llama orden del grafo a su número de vértices, .
El grado de un vértice o nodo es igual al número de arcos que se encuentran en él.
Un bucle es una arista que relaciona al mismo nodo; es decir, unaarista donde el nodo inicial y el nodo final coinciden.

Ejemplos grafos:

La imagen es una representación del siguiente grafo:
* V:={1,2,3,4,5,6}
* E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}
El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1 ~ 2.
* En la Teoría de las categorías una categoría puede ser considerada como un multigrafo dirigido,con los objetos como vértices y los morfismos como aristas dirigidas.
* En ciencias de la computación los grafos dirigidos son usados para representar máquinas de estado finito y algunas otras estructuras discretas.
* Una relación binaria R en un conjunto X es un grafo dirigido simple. Dos vértices a, b en X están conectados por una arista dirigida ab si aRb.

Origen de la teoría de losgrafos:
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado 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 loscircuitos 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 WolfgangHaken, 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.

Problema de los puentes de Königsberg:
1
Mapa de Königsberg en la época de Leonhard Euler, que muestra dónde se encontraban los siete puentes (en verde claro) y las ramas del río (en celeste).
El problema de los...