Primeros conceptos de la teoría de grafos

Definiciones

Para las matemáticas y las ciencias de la computación, un grafo es el principal objeto de estudio de la teoría de grafos. De esta forma, un grafo se representa gráficamente como un conjunto de puntos (llamados vértices o nodos), unidos por líneas (aristas). Los grafos permiten estudiar las interrelaciones entre unidades que se encuentran en interacción.
Son diagramas que interpretados de forma adecuada proporcionan información, como por ejemplo: los mapas, diagramas de circuitos o de flujos, entre otros.

Tipos de grafos:

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:

• Grafos Dirigidos: son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta =. En grafos dirigidos, para cada lado , a, es el vértice origen, se conoce como la cola del lado y b, el cual es el vértice destino. 
• Grafos No Dirigidos(pueden ser considerados un caso particular de los anteriores): son aquellos en los cuales los lados no están orientados (no son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (vi,vj)=(vj,vi). 

El ciclo de Euler

Un ciclo de un grafo o multigrafo se dice de Euler si pasa por todos los vértices recorriendo cada arista exactamente una vez.
Teorema: Sea G un grafo (finito y conexo).
(a) la suma de las valencias de todos sus vértices es par. Es decir, hay un “número par de vértices impares”.
(b) Si el número de vértices impares es mayor que dos, el grafo no se puede recorrer [sin pasar dos veces por ninguna arista].
(c) Si el número de vértices impares es cero, el grafo se puede recorrer. Podemos además elegir por qué vértice empezar, y el camino siempre será cerrado (termina donde empezó).
(d) Si el número de vértices impares es dos, el grafo se puede recorrer, pero el camino ha de empezar en uno de los dos vértices impares y terminar en el otro.

Un grafo que admita un ciclo de Euler se denomina grafo euleriano.

Ciclo de Hamilton

El problema de conocer si un grafo es Hamiltoniano y en tal caso encontrar un ciclo de Hamilton es uno de los más antiguos en Teoría de Grafos. Reciben su nombre del famoso matemático Sir William Hamilton a quien suele atribuirse el origen del problema en cuestión. Sin embargo, fueron investigados con anterioridad por el matemático T. P. Kirkman.
En 1856, Hamilton inventó un juego matemático llamado el “dodecaedro del viajero”. Tal juego consiste en un dodecaedro cada uno de cuyos veinte vértices estaba etiquetado con el nombre de una ciudad de la época. El objetivo del juego era viajar a lo largo de las aristas del dodecaedro, visitando cada ciudad exactamente una vez y volviendo al punto de partida.

Tal recorrido se denominaba “un viaje alrededor del mundo.”

Un ciclo hamiltoniano, o de Hamilton, es un grafo G es un camino que comienza y termina en un mismo vértice, pasando exactamente una vez por cada vértice.  

Biografía

Apuntes de Matemática Discreta: Grafos
Teoría de grafos. Conceptos básicos
Conceptos de Teoría de Grafos