Matemáticas - Teoría de grafos

camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez. El problema de encontrar dichos caminos fue discutido por primera vez por Leonhard Euler, en el famoso problema de los puentes de Königsberg.

Ciclos eulerianos

Dibujar un sobre abierto, como el de la imagen, sin levantar el lápiz del papel ni pasar dos veces por el mismo sitio, es posible. En cambio, dibujar el sobre cerrado (prescindiendo del punto 5 y sus líneas adyacentes) es imposible.

En la imagen, ${\displaystyle C=\{1,2,3,4,6,3,5,4,1\}\,}$ es un ciclo euleriano, luego es un grafo euleriano.

Un grafo es una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo, como contrapartida un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano.

Si un grafo admite un ciclo euleriano, se denomina grafo euleriano.

Historia

El origen de la teoría de los ciclos eulerianos fue planteado y resuelto por el propio Leonhard Euler en 1736 en un problema que tiene el nombre de Siete puentes de la ciudad de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) dando origen a la Teoría de los grafos.

El problema se enuncia de la siguiente forma: Dos islas en el río Pregel, en Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?

Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo sin repetir las líneas?

Euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto, y para regresar al punto de partida, por caminos distintos en todo momento).

Casos

Dado un grafo conexo (no existen nodos aislados) y no dirigido ${\displaystyle G=(V,E\,)}$, si ${\displaystyle G\,}$ tiene exactamente dos vértices de grado impar, entonces ${\displaystyle G\,}$ tiene un camino euleriano no cerrado. En caso de que todos los vértices tengan grado par, ${\displaystyle G\,}$ tiene un ciclo euleriano.

Teorema

Dado ${\displaystyle G(V,E\,)}$ no orientado y conexo; si tiene ${\displaystyle 2k\,}$ nodos de grado impar, entonces ${\displaystyle G\,}$ puede ser escrito como unión de ${\displaystyle k\,}$ caminos (simples) distintos sobre los arcos y valen las siguientes expresiones:

1) ${\displaystyle G\,}$ es euleriano;

2) ${\displaystyle \forall v\in \ V}$ con grado ${\displaystyle (v)\geq 2}$ y par.

3) ${\displaystyle G=\coprod _{i=1}^{n}C_{i}}$ todos disjuntos (caminos distintos) en los arcos,

es decir ${\displaystyle C_{i}^{E}\cap \;C_{j}^{E}=\emptyset \;}$ con ${\displaystyle {i\not \neq \;j}}$

${\displaystyle \forall C_{i}}$ va de un nodo de grado impar a un nodo de grado impar.

Un grafo admite un camino euleriano cuando tiene exactamente dos nodos de grado impar (conexos a los caminos).

Propiedades

• Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
• Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos.
• Si un grafo no dirigido G es euleriano entonces su gráfo-línea L(G) se dice que es también euleriano.
• Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
• Un grafo no dirigido se dice que es susceptible de ser recorrido (en inglés: traversable) si es conexo y dos vértices en el grafo tienen grado impar.

Contando circuitos eulerianos en dígrafos

El número de circuitos euleriano en los dígrafos puede ser calculado mediante el teorema denominado en Inglés: BEST-theorem, procedente de los nombres de sus fundadores: de Bruijn, van Aardenne-Ehrenfest, Smith y Tutte.

En dicho teorema se menciona que dado un dígrafo euleriano G := (V, E), el número ciclos eulerianos no-equivalentes en el grafo es

${\displaystyle C\prod _{v\in V}(\deg ^{+}(v)-1)!}$

o equivalentemente

${\displaystyle C\prod _{v\in V}(\deg ^{-}(v)-1)!}$

siendo C cualquier cofactor de la matriz laplaciana de G.

clique en un grafo no dirigido G es un conjunto de vértices V tal que para todo par de vértices de V, existe una arista que las conecta. En otras palabras, un clique es un subgrafo en que cada vértice está conectado a cada otro vértice del subgrafo, es decir, todos los vértices del subgrafo son adyacentes. Esto equivale a decir que el subgrafo inducido por V es ungrafo completo. El tamaño de un clique es el número de vértices que contiene.

El Problema del clique, que consiste en dado un grafo, decidir si existe en él un clique con un tamaño particular, es NP-completo.

Lo opuesto de un clique es un conjunto independiente, en el sentido que cada clique corresponde a un conjunto independiente del grafo complemento.

El término proviene de la palabra inglesa clique, que define a un grupo de personas que comparten intereses en común. En esta analogía, las personas serían los vértices; las relaciones de interés, las aristas; y el hecho de que todas compartan un mismo interés, el grafo completo, es decir, el clique en si.

El grafo completo K₅. En unsubgrafo como éste, los vértices forman un clique de tamaño 5.

cobertura de aristas de un grafo es un conjunto de aristas donde cada vértice del grafo es incidente en al menos en una arista del conjunto. En ciencias de la computación, el problema de la cobertura mínima de arista es el problema de encontrar una cobertura de aristas de tamaño mínimo. Este es un problema de optimización que pertenece a la clase de problemas de covertura y puede resolverse en tiempo polinomial.

Formalmente, una cobertura de aristas sobre el grafo G es un conjunto de aristas C donde cada vértice es incidente con al menos una arista en C. Se dice que el conjunto C cubre los vértices de G. La siguiente imagen muestra ejemplos de covertura de aristas en dos grafos.

Una cobertura de aristas mínima es una cobertura de aristas del menor tamaño posible. El número de cubrimiento de aristas ${\displaystyle \rho (G)}$es el tamaño de una cobertura de aristas mínima. La siguiente imagen muestra ejemplos de la cobertura de aristas mínima.

Notar que en la figura de la derecha no solo es una cobertura de aristas si no también un matching. En particular, es un matching perfecto: un maching M en donde cada vértice es incidente con exactamente una arista en M. Un matching perfecto es siempre una cobertura de aristas mínima.