El grado de un vértice o nodo en un grafo es el número de conexiones directas que tiene un vértice con otros vértices en el grafo. El grado de un vértice se puede considerar como una medida de su conectividad dentro del grafo.

Grado de Entrada y Grado de Salida en Grafos dirigidos
En un grafo dirigido, donde las aristas tienen una dirección que va de un vértice a otro, distinguimos entre el grado de entrada y el grado de salida de un vértice:

• Grado de entrada de un vértice: es el número de aristas que llegan al vértice $v$ desde otros vértices. Es decir, cuenta cuántas aristas tienen a $v$ como vértice destino.
• Grado de salida de un vértice: es el número de aristas que salen del vértice $v$ hacia otros vértices. Este cuenta cuántas aristas tienen a $v$ como su punto de origen.

Ejemplo ilustrativo.

Consideremos un grafo con cinco vértices ($A$, $B$, $C$, $D$, y $E$) como el que se muestra a continuación:

• El grado de $A$ es 2, ya que está conectado a $B$ y $C$.
• El grado de $B$ es 2, conectado a $A$ y $C$.
• El grado de $C$ es 3, ya que conecta con $A$, $B$, y $D$.
• El grado de $D$ es 2, conectado a $C$ y $E$.
• El grado de $E$ es 1, ya que solo tiene una conexión con $D$.

En la imagen de arriba el grado de cada vértice está indicado en rojo.

Propiedad de los grafos no dirigidos

La suma de los grados de todos los vértices es igual al doble del número de aristas. 

Esto es debido a que cada arista contribuye con 1 al grado de cada uno de los dos vértices que conecta.

Matemáticamente se expresa así: \(\sum_{v \in V} \deg(v) = 2·A\)

$V$ representa el conjunto de todos los vértice, $A$ el conjunto de todas aristas y $v$ cada uno de los vértices del conjunto $V$.

En el grafo anterior, la suma de los grados de todos los vértices es 10, y el número de aristas es 5. Dado que $10=2·5$, se confirma que la propiedad se cumple.

Caminos

Un camino en un grafo es una secuencia de vértices conectados por aristas, donde cada par de vértices consecutivos en la secuencia está unido directamente por una arista del grafo.

En la siguiente imagen,  podemos observar un grafo que consta de varios vértices numerados del 1 al 8.

Podemos establecer diferentes caminos para ir desde el vértice "2" al vértice "8". A continuación se muestran cuatro de ellos, donde el camino se dibuja coloreando las aristas de amarillo:

Un camino en un grafo puede expresarse sin el uso de gráficos mediante una secuencia ordenada de vértices por los que pasa el camino. Cada vértice en la secuencia está conectado al siguiente por una arista en el grafo. Esta secuencia se puede presentar como una lista o una sucesión de vértices, a menudo separados por comas o flechas para indicar la dirección del camino. Por ejemplo, $2 \rightarrow 1 \rightarrow 6 \rightarrow 7 \rightarrow 5 \rightarrow 8$ se corresponde con el camino 2 representado en la esquina superior derecha.

Tipos de vértices

En un camino dentro de un grafo podemos identificar tres tipos de vértices basados en su función o posición dentro del camino. Estos son:

• Vértice de Salida: este es el punto de inicio del camino. Es el vértice desde el cual comienzas a seguir el camino. En un grafo dirigido, este sería el vértice de donde parte la primera arista del camino. En un grafo no dirigido, simplemente es el primer vértice de la secuencia. En la secuencia "$2 \rightarrow 1 \rightarrow 6 \rightarrow 7 \rightarrow 5 \rightarrow 8$", el vértice "2" es el vértice de salida.
• Vértices de Paso: estos son los vértices intermedios por los que pasa el camino en su recorrido desde el vértice de salida hasta el vértice de llegada. Los vértices de paso se encuentran entre el inicio y el final del camino. No son ni el punto de partida ni el punto de destino final del camino, pero son esenciales para conectar el inicio y el final. En la secuencia dada, los vértices "1", "6", y "7" son vértices de paso.
• Vértice de Llegada: este es el destino final del camino, el punto donde termina el camino. En un grafo dirigido, sería el vértice al que llega la última arista del camino. En un grafo no dirigido, es el último vértice de la secuencia. En nuestro ejemplo, el vértice "8" es el vértice de llegada.

Los vértices de paso deben cumplir una condición específica respecto a su grado: cada vértice de paso debe tener un grado par. Esta condición se debe a que, para cada vez que el camino entra en un vértice de paso (a través de una arista), debe haber una arista correspondiente por la cual el camino puede salir. En otras palabras, si un camino entra en un vértice de paso, la paridad del grado asegura que siempre habrá una salida.

Para el vértice de salida y el vértice de llegada, el camino puede "entrar" o "salir" una vez más que el otro, respectivamente, lo que significa que pueden tener un grado impar. 

Si el camino es cerrado y comienza y termina en el mismo vértice, todos los vértices deben tener un grado par, incluidos el de salida y llegada, ya que son el mismo vértice en este caso.

Ejemplo: Grafo del cubo
Considerando un cubo como el poliedro de origen:

Vértices del Poliedro: Los 8 vértices del cubo se convierten en 8 vértices en el grafo.
Aristas del Poliedro: Las 12 aristas del cubo se convierten en 12 aristas en el grafo, conectando los vértices de manera que reflejen la estructura del cubo.

Cada camino sobre el cubo se corresponde con un camino sobre el grafo, y viceversa.

Observa cómo el camino trazado sobre el cubo, partiendo del vértice "A" para llegar al vértice "G", tiene su equivalente en el grafo del cubo.

De esta manera, podemos identificar y calcular todos los caminos posibles entre "A" y "G". En la siguiente imagen se muestran algunos de los caminos posibles.

Ciclos

Un ciclo es un caso especial de camino en el que el vértice inicial y final son el mismo, formando así un bucle cerrado.

En el grafo de la imagen, se observa que las aristas de color amarillo forman una secuencia que comienza en un vértice, recorre otros vértices y vuelve al vértice inicial sin utilizar ninguna arista más de una vez. Por consiguiente, podemos afirmar que es un ciclo.

Camino de Euler

Un camino de Euler es un camino que recorre cada arista de un grafo exactamente una vez. Un camino de Euler puede empezar y terminar en el mismo vértice (formando un ciclo de Euler) o en vértices diferentes.

Un grafo que contiene un camino de Euler, que es un camino que recorre cada arista del grafo exactamente una vez, se puede trazar sin levantar el lápiz del papel y sin pasar dos veces por la misma arista.

En la siguiente imagen se muestra un grafo que contiene un camino de Euler, que comienza en el vértice "Inicio" (grado 3, impar) y finaliza en "Fin" (grado 3, impar). El resto de los vértices (vértices de paso) tiene grado par. Observa cómo es posible trazarlo sin levantar el lápiz del papel , pasando una única vez por cada arista.

Grafos que se pueden trazar sin levantar el lápiz del papel y sin pasar dos veces por la misma arista

Para que un grafo no dirigido contenga un camino de Euler, es decir, un camino que recorra cada arista exactamente una vez (se puede trazar sin levantar el lápiz del papel y sin pasar dos veces por la misma arista), debe cumplir con las siguientes condiciones:

• El grafo debe ser conexo, excepto por vértices aislados (vértices sin aristas). Esto significa que debe haber un camino entre cualquier par de vértices en el grafo, asegurando que sea posible llegar de un vértice a cualquier otro vértice a través de una serie de aristas.
• Debe tener exactamente 0 ó 2 vértices de grado impar:
  • Si un grafo no dirigido tiene exactamente 0 vértices de grado impar, entonces contiene un ciclo de Euler, es decir, un camino de Euler que comienza y termina en el mismo vértice.
  • Si tiene exactamente 2 vértices de grado impar, entonces contiene un camino de Euler que comienza en uno de estos vértices de grado impar y termina en el otro. Esto se debe a que, para recorrer todas las aristas exactamente una vez y terminar en un vértice diferente al de inicio, el vértice inicial debe tener un número impar de aristas (una más para "salir" que para "entrar") y el vértice final debe tener también un número impar de aristas (una más para "entrar" que para "salir").

Ciclo de Euler
Un ciclo de Euler es un tipo específico de camino de Euler que empieza y termina en el mismo vértice, recorriendo todas las aristas del grafo exactamente una vez. Un grafo que tiene un ciclo de Euler se conoce como grafo euleriano. Cuando un grafo no contiene un ciclo de Euler pero si un camino de Euler se le conoce como grafo semieuleriano o recorrible, y su condición es que tenga todos los vértices con grado par salvo dos con grado impar que serán el comienzo y el fin del camino.

El grafo anterior no contiene un ciclo de Euler, pues existen dos vértice de grado impar.

Ejemplos

Algunos ejemplos prácticos que muestran la aplicación de grafos eulerianos son los siguientes:

• Sistema de rutas de servicio postal: En una ciudad pequeña, un cartero debe entregar correo en todas las calles sin pasar dos veces por la misma. Un grafo euleriano representa las calles (aristas) y las intersecciones (nodos), y permite al cartero planificar una ruta que minimiza el tiempo y el combustible al no repetir ninguna calle.
• Recorrido de inspección de puentes: Un ingeniero necesita inspeccionar todos los puentes en una serie de islas conectadas por puentes. Los puentes son las aristas y las islas los nodos. Usando un grafo euleriano, el ingeniero puede planificar el recorrido más eficiente que le permita inspeccionar todos los puentes una sola vez, asegurando que no se pierda ninguno y optimizando su recorrido.
• Planificación de rutas de limpieza urbana: Un ayuntamiento debe planificar las rutas de los camiones de limpieza para barrer todas las calles de la ciudad. Al modelar las calles como un grafo euleriano, pueden crear un plan que cubra todas las calles sin duplicar el trabajo, asegurando así una limpieza eficiente y ahorrando tiempo.
• Turismo de sitios patrimoniales: Un guía turístico organiza un tour que incluye todos los caminos dentro de un parque histórico, asegurando que los turistas experimenten cada sendero sin repetir ninguno. Un grafo euleriano ayuda a mapear todos los senderos (aristas) y cruces (nodos), diseñando una ruta que maximiza la experiencia del visitante siendo a la vez eficiente.

Camino y ciclo de Hamilton o hamiltoniano

Un camino hamiltoniano en teoría de grafos es un camino en un grafo que visita cada vértice del grafo exactamente una vez.

La imagen que se muestra a continuación, presenta dos caminos distintos sobre un grafo, ambos iniciando en el vértice "1" y concluyendo en el vértice "6". El camino ilustrado en el lado izquierdo no cumple con los criterios de un camino hamiltoniano, ya que el vértice "1" se recorre dos veces. Por otro lado, el camino mostrado en el lado derecho sí es hamiltoniano, dado que cada vértice se visita únicamente una vez. En ambos casos, se recorren todos los vértices del grafo.

Si el camino retorna al vértice de inicio, entonces lo denominamos un ciclo hamiltoniano.

Grafo hamiltoniano

Un grafo hamiltoniano es un tipo de grafo que permite trazar un camino que visita cada vértice exactamente una vez y regresa al punto de origen, formando un ciclo. Este camino se denomina ciclo hamiltoniano. La existencia de un ciclo hamiltoniano en un grafo no es siempre garantizada, y determinar si un grafo dado es hamiltoniano puede ser un problema computacionalmente difícil. Si el grafo posee un camino hamiltoniano, pero no un ciclo hamiltoniano (el camino no empieza y termina en el mismo vértice), se denomina grafo semihamiltoniano,

El grafo mencionado es tanto euleriano como hamiltoniano, ya que permite trazar un ciclo euleriano y un ciclo hamiltoniano:

Ciclo euleriano: $1 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 6 \rightarrow 5 \rightarrow 4 \rightarrow 6 \rightarrow 3 \rightarrow 1$ (ilustrado en el lado izquierdo).

Ciclo hamiltoniano: $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 1$ (ilustrado en el lado derecho).

Los grafos eulerianos y hamiltonianos son conceptos fundamentales en la teoría de grafos, pero se refieren a características distintas de los grafos.

Grafos euleriano vs hamiltonianos

• Enfoque:
  • Los grafos eulerianos se centran en recorrer todas las aristas sin repetirlas.
  • Los grafos hamiltonianos se centran en visitar todos los vértices sin repetirlos.
• Condiciones de existencia:
  • Los grafos eulerianos tienen condiciones bien definidas para su existencia basadas en el grado de los vértices.
  • Para los grafos hamiltonianos, no hay criterios simples que garanticen su existencia.
• Complejidad computacional:
  • Determinar si un grafo es euleriano es relativamente sencillo y se puede hacer en tiempo polinomial.
  • Determinar si un grafo es hamiltoniano es un problema NP-completo, lo que implica una mayor complejidad computacional para grafos grandes.
• Aplicaciones prácticas:
  • Los grafos eulerianos se aplican en problemas relacionados con el recorrido de aristas, como el diseño de rutas eficientes para el mantenimiento de infraestructuras.
  • Los grafos hamiltonianos son útiles en problemas de optimización de rutas y secuenciación, donde el foco está en visitar puntos o nodos.