16 Caminos y conexion

Definición 16.1 (Camino).

Un camino de longitud $\displaystyle n$ entre los vertices $\displaystyle a$ y $\displaystyle b$ de un grafo no dirigido es una sucesion finita $\displaystyle(e_{0},\ldots,e_{n-1})$ de aristas del grafo

\displaystyle e_{0}=\{v_{0},v_{1}\},e_{1}=\{v_{1},v_{2}\},\ldots,e_{n-1}=\{v_{% n-1},v_{n}\},

de manera que $\displaystyle v_{0}=a$ , $\displaystyle v_{n}=b$ y cada arista sucesiva empieza donde termino la anterior. Si el grafo es simple, el camino $\displaystyle(e_{0},\ldots,e_{n-1})$ queda perfectamente determinado por la sucesion de vertices

\displaystyle(a,v_{1},v_{2},\ldots,v_{n-1},b).

Diremos que el camino anterior pasa por (o atraviesa) los vertices $\displaystyle a$ , $\displaystyle v_{1}$ , $\displaystyle v_{2}$ , $\displaystyle\ldots$ , $\displaystyle v_{n-1}$ , $\displaystyle b$ . Se dice que un camino es un circuito si es cerrada, esto es, empieza y termina en el mismo vertice, es decir, si $\displaystyle a=b$ . Se dice que un camino es simple si no contiene a la misma arista mas de una vez. Un circuito que no pasa dos veces por el mismo vertice (salvo el inicial por el que pasa dos veces) se llama ciclo.

Definición 16.2 (Conexo).

Se dice que un grafo no dirigido $\displaystyle G$ es conexo si para cualquier par de vertices $\displaystyle a$ y $\displaystyle b$ de $\displaystyle G$ existe un camino entre $\displaystyle a$ y $\displaystyle b$ .

Si un grafo no es conexo, se puede expresar como la union de dos o mas subgrafos conexos de manera que los conjuntos de vertices y de aristas de cada par de estos subgrafos son disjuntos entre si. A estos subgrafos se les denomina componentes conexas del grafo dado. De esta manera un grafo es conexo si y solo si tiene una unica componente conexa.

Teorema 16.1.

Sea $\displaystyle G$ un grafo (dirigido o no dirigido, con aristas multiples y lazos o no) y sea $\displaystyle A=(a_{ij})$ su matriz de adyacencias con respecto al orden $\displaystyle v_{1},v_{2},\ldots,v_{n-1},v_{n}$ de su conjunto de vertices. En estas condiciones el numero de caminos de longitud $\displaystyle m$ entre el vertice $\displaystyle v_{i}$ y el vertice $\displaystyle v_{j}$ es igual al coeficiente situado en el lugar $\displaystyle(i,j)$ de la potencia $\displaystyle m$ -esima de la matriz $\displaystyle A$ (con respecto al producto de matrices usual).

Demostración.

No la hacemos, pero se puede hacer por induccion sobre la longitud del camino entre dos vertices cualesquiera $\displaystyle v_{i}$ y $\displaystyle v_{j}$ de un grafo $\displaystyle G$ . ∎

Corolario 16.1.

Dado un grafo $\displaystyle G=(V,E)$ tal que $\displaystyle|V|=n$ , se verifica que $\displaystyle G$ es conexo si y solo si la matriz

\displaystyle I_{n}+A+A^{2}+\cdots+A^{n-1}

tiene todos los coeficientes distintos de cero.

Ejemplo.

Sea $\displaystyle G$ un grafo cuya matriz de adyacencia es:

\displaystyle A=\begin{pmatrix}0&1&0\\ 1&0&1\\ 0&1&0\\ \end{pmatrix}

Entonces su cuadrado es

\displaystyle A^{2}\coloneqq\begin{pmatrix}1&0&1\\ 0&2&0\\ 1&0&1\\ \end{pmatrix}

Por tanto $\displaystyle I_{3}+A+A^{2}$ tiene todas sus entradas no nulas y el grafo es conexo.

Definición 16.3 (Camino euleriano).

Un camino euleriano en un grafo no dirigido $\displaystyle G$ es un camino simple que contiene a todas las aristas de $\displaystyle G$ . Un circuito euleriano en $\displaystyle G$ es un circuito simple que contiene todas las aristas del grafo $\displaystyle G$ .

Definición 16.4 (Grafo euleriano).

Se dice que un grafo no dirigido es euleriano si contiene un circuito euleriano.

Un camino euleriano es un camino que recorre todas las aristas del grafo y sin repetir ninguna.

Teorema 16.2.

Un grafo $\displaystyle G=(V,E)$ con aristas no dirigidas es euleriano si y solo si todas las aristas estan en la misma componente conexa y todos los vertices tienen grado par.

El siguiente resultado nos da una condicion para la existencia de un camino euleriano no cerrado:

Proposición 16.1.

Un grafo $\displaystyle G=(V,E)$ con aristas no dirigidas tal que todas sus aristas estan en la misma componente conexa admite un camino euleriano no cerrado si y solo si contiene exactamente dos vertices de grado impar.

Proposición 16.2 (Algoritmo de Fleury).

Para calcular caminos/ciclos eulerianos en un grafo que los admite, usamos el algoritmo de Fleury:

Comprobacion previa: Todas las aristas estan en la misma componente conexa y a lo sumo hay dos nodos de grado impar (necesario para que existan cambios eulerianos).
Paso inicial: elegimos un vertice ( $\displaystyle v_{0}$ ) del siguiente modo:
- •
  
  Si hay vertices de grado impar, elegimos uno de grado impar al azar.
- •
  
  Si no hay vertices de grado impar, elegimos uno de grado par al azar.
Elegimos al azar una arista incidente en el vertice elegido en el paso anterior que no desconecte el grafo. Si no es posible hacerlo, elegimos una de las aristas incidentes al azar. En ambos casos borramos la arista elegida del grafo y nos movemos al vertice del otro extremo de la arista eliminada.
Repetimos el proceso hasta que no queden aristas.

La sucesion de aristas construidas antes es un camino/ciclo euleriano.

Definición 16.5 (Camino hamiltoniano).

Se denomina camino hamiltoniano en un grafo con aristas no orientadas $\displaystyle G=(V,E)$ a cualquier camino simple que contenga a todos los vertices de $\displaystyle G$ pasadno una sola vez por cada uno de ellos, pero permitiendo que el vertice inicial de dicho camino sea igual al vertice final. Si el camino hamiltoniano es cerrado, a dicho camino se le denomina circuito hamiltoniano.

Definición 16.6 (Grafo hamiltoniano).

Se dice que un grafo no dirigido $\displaystyle G=(V,E)$ es hamiltoniano si contiene un circuito hamiltoniano.

Pese a la aparente similitud con la definicion de los grafos eulerianos encontrar un circuito hamiltoniano en un grafo puede no ser tarea facil pues no se conoce una caracterizacion de los grafos hamiltonianos.

Como se ha comentado, no siempre es sencillo determinar si un grafo simple y conexo dado es hamiltoniano pues, para ello, el unico criterio que tenemos a priori es nuestra habilidad para encontrar o no un circuito hamiltoniano en el grafo dado. La siguiente proposicion nos aporta un resutlado que permite concluir que ciertos grafos son hamiltonianos.

Teorema 16.3 (de Dirac).

Sea $\displaystyle G=(V,E)$ un grafo simple conexo de $\displaystyle n$ vertices ( $\displaystyle n\geq 3$ ) tal que para cualquier vertice $\displaystyle v\in V$ se cumple que

\displaystyle gr(v)\geq\frac{n}{2}.

entonces $\displaystyle G$ es hamiltoniano.

El Teorema de Dirac da una condicion suficiente para saber si un grafo es hamiltoniano, pero esta condicion no es una condicion necesaria (en general).

Hasta el momento no existe ninguna caracterizacion de los grafos hamiltonianos en terminos de los grados del grafo.

Definición 16.7 (Isomorfismo de grafos).

Se dice que dos grafos simples $\displaystyle G_{1}=(V_{1},E_{1})$ y $\displaystyle G_{2}=(V_{2},E_{2})$ son isomorfos si existe una biyeccion $\displaystyle f\colon V_{1}\to V_{2}$ tal que $\displaystyle\forall u,v\in V_{1}$

\displaystyle\{u,v\}\in E_{1}\Leftrightarrow\{f(u),f(v)\}\in E_{2}

De la funcion $\displaystyle f$ que satisface dicha condicion se dice que es un isomorfismo de grafos entre los grafos $\displaystyle G_{1}$ y $\displaystyle G_{2}$ .

En otras palabras, dos grafos simples son isomorfos si existe una funcion biyectiva entre los dos conjuntos de vertices que preserva las adyacencias. Naturalmente esta definicion se puede extender a multigrafos y multidigrafos teniendo en cuenta el numero de aristas entre cada par de vertices y, en su caso, la orientacion de las aristas.

Ejemplo.

Los dos grafos de la figura son isomorfos. Para verlo basta comprobar que la funcion $\displaystyle f\colon\{a,b,c,d\}\to\{u,v,w,p\}$ , tal que $\displaystyle f(a)=u$ , $\displaystyle f(b)=v$ , $\displaystyle f(c)=w$ , $\displaystyle f(d)=p$ es un isomorfismo de grafos.

A menudo es dificil determinar si dos grafos simples son isomorfos. De hecho, empleando herramientas de combinatoria, puede comprobarse que hay $\displaystyle n!$ aplicaciones biyectivas entre los conjuntos de vertices de dos grafos con $\displaystyle n$ vertices, por lo que comprobar una por una si dichas biyecciones preservan las adyacencias no es un buen metodo, sobre todo si $\displaystyle n$ es un numero grande.

Debemos encontrar criterios para determinar si dos grafos simples son isomorfos o no lo son que no precisen una comprobacion exhaustiva.

Estos criterios se apoyan en el hecho de que hay ciertas propiedades, denominadas invariantes por isomorfismo, que, si un grafo las verifica, cualquier otro grafo isomorfo a el las debe tambien verificar. Por ejemplo:

1.

Dos grafos isomorfos deben tener el mismo numero de vertices y el mismo numero de aristas.
2.

Si $\displaystyle f\colon V_{1}\to V_{2}$ establece un isomorfismo entre los grafos $\displaystyle G_{1}=(V_{1},E_{1})$ y $\displaystyle G_{2}=(V_{2},E_{2})$ , entonces para cada $\displaystyle u\in V_{1}$ se tiene que $\displaystyle gr(u)=gr(f(u))$ .

Este tipo de resultados sirve para comprobar con cierta facilidad que algunos grafos no son isomorfos.

Teorema 16.4.

Si tenemos dos grafos que son isomorfos, entonces comparten todos los invariantes. Por tanto, si tenemos dos grafos que no comporten algun invariante, entonces no pueden ser isomorfos.