algoritmos de grafos

Manual de algorítmica

Borrego Ropero Rafael 1 de 248 Recio Domínguez Daniel

MANUAL DE ALGORÍTMICA

Proyecto fin de carrera Escuela Técnica Superior de Ingeniería Informática

Departamento Matemáticas Aplicadas I Tutor: Alberto Márquez Pérez

Borrego Ropero, Rafael [email protected]

Recio Domínguez, Daniel

[email protected]



1.- Introducción................................................................................................... 6 2.- Conceptos generales. ................................................................................... 8

Grafos, tipos, ejemplos................................................................................ 8 Algunas definiciones. ................................................................................ 12 Algunos grafos básicos. ............................................................................ 17 Tipos de rutas ........................................................................................... 46 Grafo complementario............................................................................... 48 Grafo de línea. .......................................................................................... 50

3.- Algoritmos implementados. ......................................................................... 54 3.1.- Algoritmos sobre caminos mínimos...................................................... 54

Algoritmo de Dijkstra. ................................................................................ 54 Algoritmo de Floyd. ................................................................................... 61

3.2.- Algoritmos de distancias....................................................................... 65 Excentricidad de un vértice. ...................................................................... 65 Radio de un grafo...................................................................................... 67 Diámetro de un grafo................................................................................. 69 Distancia de un vértice. ............................................................................. 70 Algoritmo de la mediana............................................................................ 72 Algoritmo del centro. ................................................................................. 73

3.3.- Conectividad......................................................................................... 75 Algoritmo de componentes conexas. ........................................................ 75 Vértices de corte. ...................................................................................... 77 Aristas puente. .......................................................................................... 78 Bloques. .................................................................................................... 79

3.4.- Algoritmos de búsquedas. .................................................................... 88 Búsqueda en profundidad (DFS) .............................................................. 88 Búsqueda en anchura (BFS) .................................................................... 90

3.5.- Árboles recubridores de peso mínimo. ................................................. 92 Algoritmo de Boruvka. ............................................................................... 92 Algoritmo de Prim...................................................................................... 98 Algoritmo de Kruskal. .............................................................................. 100

3.6.- Prufer.................................................................................................. 103 Algoritmo de codificación. ....................................................................... 103 Algoritmo de decodificación. ................................................................... 110

3.7.- Algoritmo de emparejamientos ........................................................... 120 Algoritmo de emparejamiento maximal simple........................................ 121 Algoritmo de Kuhn-Munkres.................................................................... 128 Algoritmo de Kuhn-Munkres con preprocesamiento (peso mínimo)........ 142 Algoritmo de emparejamiento maximal de peso óptimo.......................... 146

3.8.- Euler ................................................................................................... 157 ¿ Es euleriano ?. ..................................................................................... 157

3.9.- Algoritmos de búsqueda de trayectorias eulerianas. .......................... 162 Algoritmo de Fleury ................................................................................. 162 Algoritmo de Tucker. ............................................................................... 183 Algoritmo de Hierholzer........................................................................... 201 Problema del cartero............................................................................... 205

3.10.- Algoritmos de vértice coloración....................................................... 212 Algoritmo de coloración Secuencial o Voraz. .......................................... 213



Algoritmo de coloración Welsh-Powell .................................................... 215 Algoritmo de coloración Matula-Marble-Isaacson ................................... 216 Algoritmo de coloración de Brelaz........................................................... 217 ¿Es bipartito? .......................................................................................... 221

3.11.- Algoritmos de aristas coloración....................................................... 225 Algoritmo basado en rellenar un cuadrado latino .................................... 225 Algoritmo basado en emparejamientos maximales................................. 228

3.-12.- Hamilton .......................................................................................... 235 Algoritmo de Dirac................................................................................... 235 Búsqueda de trayectorias hamiltonianas................................................. 239

4.- Bibliografía ................................................................................................ 248



1.- Introducción. Nos encontramos ante una aplicación desarrollada para el departamento de matemática aplicada I con el objetivo de proporcionar una herramienta que ayude al desarrollo de las prácticas de las asignaturas dedicadas al estudio de los grafos y la investigación. La aplicación desarrollada tiene como objetivos mejorar algunos aspectos de la aplicación “Algraf” la cual ha sido punto de partida de este proyecto por lo que se mantiene la compatibilidad con versiones anteriores. La aplicación resuelve todos los problemas recogidos en versiones anteriores de “Algraf” y se han incluido algunos nuevos por los que ahora la aplicación da solución a gran cantidad de problemas entre los que podemos destacar. - Problema de rutas. - Problemas de ubicación. - Problemas de compatibilidades o coloración. - Problemas de minimización de costes.

- Problemas de emparejamientos.

Los conceptos expuestos a continuación están enfocados a la comprensión única y exclusivamente a los algoritmos desarrollados para la aplicación. Se ha pretendido que sea un manual autocontenido por lo que cualquier concepto necesario para entender de los algoritmos o funcionamiento de la aplicación está debidamente explicado.



2.- Conceptos generales.

Grafos, tipos, ejemplos.

Un grafo G es un conjunto finito, no vacío de vértices V(G) y un

conjunto de aritas E(G) que puede ser vacío formado por pares no ordenados de elementos pertenecientes a V(G). Solo se establecerá un orden cuado hablemos de grafos dirigidos y a las aristas se las denomina arcos.

Ejemplo de grafo no dirigido.

La matriz de adyacencias del grafo es simétrica respecto a la

diagonal principal por ser no dirigido.

v1 v2 v3 v4 v5 v6 v7

v1 ∞ 1 ∞ 1 ∞ ∞ ∞ v2 1 ∞ 1 1 1 ∞ ∞ v3 ∞ 1 ∞ ∞ ∞ 1 ∞ v4 1 1 ∞ ∞ 1 ∞ ∞ v5 ∞ 1 ∞ 1 ∞ ∞ 1 v6 ∞ ∞ 1 ∞ ∞ ∞ ∞

v7 ∞ ∞ ∞ ∞ 1 ∞ ∞



Si dos o más aristas unen el mismo par de vértices se llaman aristas paralelas y en este caso tenemos un multigrafo.

Si una arista une un mismo vértice se trata de un lazo o bucle. Si en un grafo se permite aristas paralelas y bucles obtenemos un

seudografo.

Ejemplo de grafo dirigido.

Matriz de adyacencias del grafo.

v1 v2 v3 v4 v5

v1 ∞ ∞ 1 ∞ 1 v2 1 ∞ ∞ 1 ∞ v3 ∞ 1 ∞ ∞ ∞ v4 1 ∞ 1 ∞ ∞ v5 ∞ ∞ ∞ 1 ∞



Un grafo es ponderado si cada arista lleva asociada una magnitud, longitud, dificultad al recorrerla…

Ejemplo de grafo ponderado no dirigido.

La matriz de adyacencias del grafo es simétrica respecto a la

diagonal principal por ser no dirigido.

v1 v2 v3 v4 v5 v6 v7

v1 ∞ 3 ∞ ∞ 5 2 ∞ v2 3 ∞ 3 6 1 ∞ ∞ v3 ∞ 3 ∞ 1 ∞ ∞ 2 v4 ∞ 6 1 ∞ 1 ∞ ∞ v5 5 1 ∞ 1 ∞ ∞ ∞ v6 2 ∞ ∞ ∞ ∞ ∞ ∞ v7 ∞ ∞ 2 ∞ ∞ ∞ ∞



Ejemplo de grafo ponderado dirigido.

Matriz de adyacencias.

Si G es un grafo no dirigido y e = uv es una arista de G diremos que “u” es adyacente a “v” o que “v” es adyacente a “u” o “e” une “u” y “v”, e incide en “v” y “u”. En caso de tratarse de un grafo dirigido diremos que “u” es adyacente a “v” y “v” es adyacente desde “u”. El arco (u, v) es incidente desde “u” e incidente hacia “v”.

v1 v2 v3 v4 v5 v6 v7 v8

v1 ∞ 2 3 ∞ ∞ ∞ ∞ ∞ v2 ∞ ∞ ∞ 1 1 ∞ ∞ ∞ v3 ∞ ∞ ∞ ∞ ∞ ∞ 1 ∞ v4 ∞ ∞ ∞ ∞ ∞ 1 ∞ ∞ v5 ∞ ∞ ∞ ∞ ∞ 1 ∞ ∞ v6 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 v7 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 2 v8 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞



Algunas definiciones. Tamaño y orden de un grafo.

El orden de un grafo G es el número de vértices del grafo y tamaño es el número de aristas.

p = orden (G) = | V (G) |. q = tamaño (G) = | E (G) |. Valencia o grado de un vértice “v”.

En un grafo no dirigido el grado de un vértice “v” es el número de aristas que inciden en él o número de vértices adyacentes.

En grafos dirigidos se distingue entre grado de entrada y salida

del vértice.

El grado de entrada de “v” se define como el número de vértices adyacentes y el grado de salida de “v” es el número de vértices adyacentes hacia el “v” o número de vértices que apuntan a “v”.

Subgrafo. Un grafo H es subgrafo de un grafo G si V(H) ⊆ V(G).

Ejemplo.



Subgrafo H.

No es un subgrafo.



Subgrafo inducido por vértices.

Sea S un conjunto de vértices no vacío de un grafo G. El subgrafo inducido por S es el subgrafo maximal de G con vértices en el conjunto S. Al conjunto de aristas lo denotaremos por <S>.

En <S> están todas las aristas de G que unen dos vértices de S. Un subgrafo H es subgrafo inducido por vértices si existe S ⊆

V (G) tal que H = <S>.

Ejemplo



Subgrafo inducido por lo vértices {v1, v4, v5, v6}.

Subgrafo inducido por aristas. Sea X un conjunto no vació de aristas de G. El subgrafo inducido por X es el subgrafo mínimo de G con X el conjunto de aristas y <X> el conjunto de vértices. En <X> están todos los vértices incidentes con alguna arista de X.

Un subgrafo es subgrafo inducido por aristas si H = <X> para algún X ≠ ∅ ⊆ E (G).



Ejemplo

Subgrafo inducido por las aristas {v1v4, v4v5, v5v6, v6v3, v4v3}.



Algunos grafos básicos. Grafos completos. Sea G un grafo de orden “p”. G es completo si dos vértices cualesquiera

del grafo son siempre adyacentes, es decir, todos sus vértices tienen valencia o grado p-1 (kp).

Ejemplo k4.

Ejemplo k5.



Caminos simples. Un grafo de orden p ≥ 1 que es un camino simple se denota Pp.

Un camino simple tiene longitud par si “p” es impar y longitud impar

si “p” es par.

Ejemplo

Ciclos.

Los ciclos Cn o n-ciclos para p ≥ 3, son grafos que se asemejan a polígonos de “p” lados.

Un ciclo tiene longitud par si “n” es par y longitud impar si “n” es par.

Ejemplo C5.



Árbol.

Un árbol de “n” vértices es un grafo conexo, sin ciclos con exactamente n-1 aristas. Además posee las siguientes propiedades. a) Dos vértices cualesquiera están unidos por un único camino. b) Si al grafo le eliminamos cualquiera de sus aristas queda dividido exactamente en dos componentes conexas dando lugar a un bosque. Ejemplo.



Bosque Conjunto de árboles. Ejemplo.

Existen más tipos de grafos como los bipartitos los cuales se comentan más adelante. Concretamente hay un apartado dedicados exclusivamente para ellos y en el algoritmo de Kuhn-Munkres se comenta previamente los grafos bipartitos completos.



Árbol n-ario completo.

Una de las formas de representación de la información, como estructura de datos, más utilizada es el árbol . Un árbol consiste en un nodo inicial, llamado raíz, del que parten un cierto número de aristas, denominadas ramas , cada una hasta un nuevo vértice. Los vértices extremos de una arista se llaman también vértice padre , aquel que se representa más cerca de la raíz, y el otro vértice hijo . A su vez, estos vértices hijos pueden presentar ramas hacia nuevos nodos hijos, que deberán ser siempre nodos diferentes, ya que un árbol no puede presentar ciclos. Por último, aquellos vértices que no presentan ramas hacia ningún hijo, se denominan hojas . El caso de los árboles n-arios completos es un caso particular dentro de los árboles. La referencia a n-arios-completos se debe a que el número de ramas que sale de cada nodo padre, que es en todos los casos igual a n. Para definir completamente un grafo perteneciente a esta familia, en realidad son necesarios 2 parámetros. Uno es la n anteriormente comentado, y el otro es el número de niveles que se le quiere dar al grafo, esto es, el número de ramas que deberá tener el grafo desde el vértice raíz hasta cualquiera de los vértices hoja.



Grafos nulos Un grafo nulo es aquel que no contiene aristas. Un grafo nulo puede tener un número de vértices cualquiera pero todos ellos son vértices aislados. Obviamente, en un grafo nulo el número de componentes conexas será igual al número de vértices. Un ejemplo de grafo nulo de cuatro vértices puede observarse en la figura.



Rueda

Como en los casos de los grafos ciclos y los grafos estrella, la familia de los grafos ruedas toma su apelativo de la figura con la que se representan estos grafos. En este caso, la figura que muestra un grafo rueda viene a ser el resultado de la unión de las dos familias citadas anteriormente, esto es, un vértice central rodeado de los demás vértices del grafo en forma de círculo, de forma que éstos se unen mediante aristas entre vértices consecutivos, y, a su vez, mediante una arista más, quedan unidos al vértice central, dando al conjunto el aspecto de una rueda con sus radios. Así, para cada n≥4, el grafo rueda, Wn, con n+1 vértices, se define como la unión K1+Cn, de un vértice aislado con un ciclo de longitud n.



Cubos Otra de las familias de grafos que suelen considerarse con bastante asiduidad es la de los cubos. Esta familia está formada por los cubos de las distintas dimensiones, desde el cubo de dimensión 1, como observaremos en el apartado siguiente, hasta cualquier número de dimensiones. Sea K un entero positivo mayor que 1. El k-cubo, Qk, es el grafo cuyos vértices son las k-tuplas ordenadas de ceros y unos, en el cual dos vértices están unidos por una arista si y sólo si difieren exactamente en una posición. Así, por ejemplo, para k=3, los vértices son (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), y (1, 1, 1) y, por ejemplo, (0, 0, 0) está unido con (0, 0, 1), (0, 1, 0) y (1, 0, 0) pero no con ningún otro vértice. Se puede comprobar que un k-cubo tiene 2k vértices, 2(k-1)k aristas y es bipartito. Cubo de dimensión 1. El grafo que representa el cubo de dimensión 1, tal y como se ha explicado en el apartado anterior, tiene 21 vértices y (1/2)21 = 1 arista.



Cubo de dimensión 2. Como ya se ha explicado en apartados anteriores, el grafo que representa el cubo de dimensión dos tiene un total de 4 vértices de grado 2, para lo cual son necesarias 4 aristas.

Cubo de dimensión 3. Al igual que en los casos de los demás cubos, el grafo que representa el cubo de dimensión tres sigue la misma relación de vértices y aristas descrita en la introducción de este apartado. Por lo tanto, el cubo de 3 dimensiones, tal y como es comúnmente conocido, cuenta con 8 vértices de grado 3, para lo cual necesita 12 aristas.



Cubo de dimensión 4. Como en los casos anteriores, el cubo de 4 dimensiones también cumple la relación de vértices y aristas descrita, por lo que tiene 24 vértices y 25 aristas, lo que le da un grado 4 a todos sus vértices, como ya sabíamos.



Cubo de dimensión 5. Para terminar con los grafos relativos a la familia de los cubos n-dimensionales que se incluyen en la aplicación del presente proyecto fin de carrera, el cubo de 5 dimensiones constará, naturalmente, de 32 vértices con 80 aristas. Como en el resto de cubos, se puede comprobar que el grado de todos y cada uno de los vértices del grafo coincide con la dimensión, en este caso, 5.



Rejillas La familia de grafos que recibe la denominación de rejillas contiene aquellos grafos cuya representación da como resultado una trama de figuras regulares repetidas un cierto número de veces, lo que da al conjunto el aspecto de una rejilla, lo que le da nombre a la familia. Así, podrían existir tantos tipos de rejillas como figuran geométricas quisiéramos utilizar como base para la construcción de las mismas. En el presente trabajo se han considerado solamente las dos más sencillas: la rejilla rectangular y la rejilla triangular, que se explican a continuación. Rejilla rectangular La familia de grafos que componen las rejillas rectangulares se compone de todos aquellos grafos cuya representación tiene la forma de un rectángulo dividido en un cierto número de porciones de ancho por otro cierto número de porciones de alto, lo que da al conjunto el aspecto de una rejilla formada, a su vez, por rectángulos de igual tamaño. Estos grafos se caracterizan por tener lo que podríamos denominar tres grupos diferentes de vértices. Los vértices correspondientes a las esquinas del rectángulo, que tendrán, naturalmente, grado 2; los vértices que forman los lados del rectángulo, que tendrán grado 3; y los vértices interiores, que tendrán grado 4. El número de aristas de estos grafos está claramente determinado por las dimensiones que le demos al rectángulo. Para un número “i” de vértices de ancho y un número “j” de alto, el número de aristas del grafo vendrá determinado por la fórmula (j-1)i + (i-1)j.



Grafo rejilla rectangular de 20 x 5.

Rejilla triangular La familia de grafos de las rejillas triangulares, paralelamente a la del rejillas rectangulares, contiene grafos cuya representación es un triangulo dividido en porciones triangulares iguales. Como es fácil de suponer, el número de porciones en que se puede dividir el triángulo de la rejilla también está limitado. A diferencia de la rejilla rectangular, las dimensiones de la rejilla triangular se determinan perfectamente con un solo parámetro que será el número de vértices por cada lado. Al igual que ocurre con las rejillas rectangulares, en las triangulares también podemos encontrar tres grupos diferentes de vértices. Los vértices correspondientes a las esquinas del triángulo, que tendrán, igualmente, grado 2; los vértices que forman los lados del triángulo, que tendrán en este caso grado 4; y los vértices interiores, que tendrán grado 6. El número de aristas de estos grafos también viene determinado, lógicamente, por las dimensiones que le demos al triángulo. Para un número “n” de vértices de lado del triángulo, el número de aristas del grafo vendrá determinado por la fórmula (3/2)n(n-1).



Grafo rejilla triangular de 11 vértices de lado.



Grafos Platónicos En el espacio de tres dimensiones, un poliedro es un sólido limitado por superficies, llamadas comúnmente caras , cada una de las cuales es un plano. Un sólido se dice que es convexo si cualesquiera dos puntos de su interior pueden unirse mediante una línea recta que se encuentre completamente en el interior del sólido. Sea ϕϕϕϕ una cara de un grafo plano G. Definimos el grado de ϕϕϕϕ, denotado por d(ϕϕϕϕ), al número de aristas del contorno de ϕϕϕϕ. Los vértices y las aristas de un poliedro, que forman el esqueleto del sólido, forman un grafo simple en el espacio de tres dimensiones. Se puede ver que si el poliedro es convexo el grafo resultante es planar, y claramente, que también es conexo. Que el grado mínimo de cada vértice será, como mínimo, de 3 y que el grado de cada cara es también como mínimo de 3. Además, en particular el grafo resultante también es simple, por lo que se puede establecer la definición: Un grafo conexo, simple y plano G se denomina poliédrico si d(v)≥ 3 para cada vértice v de G y d(ϕϕϕϕ)≥3 para cada cara ϕϕϕϕ de G. Teorema: Sea P un poliedro convexo y sea G su grafo poliédrico. Para cada n≥3 sea vn el número de vértices de G de grado n y sea fn el número de caras de G de grado n. << vérticesG + carasG = aristasG +2 >> El poliedro P, y por lo tanto el grafo G, tiene al menos una cara limitada por un ciclo de longitud n para n=3, 4, o 5. Los antiguos griegos descubrieron cinco poliedros regulares. Se dice que un poliedro es regular si es convexo y sus caras son polígonos regulares congruentes (esto es, que los ángulos del poliedro son todos iguales). Estos cinco poliedros son conocidos como sólidos platónicos. Usando la fórmula de Euler se puede demostrar que no existe ningún otro poliedro regular además de los 5 que descubrieron los griegos y cuyos grafos correspondientes constituyen la familia que se incluye en la herramienta y los cuales se presentan a continuación.



A continuación, se detalla un poco más cada uno de los citados grafos. Tetraedro El grafo platónico que representa la figura del tetraedro consta, naturalmente, de 4 vértices y 6 aristas. Como se puede observar en la figura siguiente, todos los vértices del grafo tienen grado 3, y las caras de la figura representada son todas triángulos, como corresponde a dicha figura. El grafo platónico tetraedro se encuentra representado planarmente en la siguiente figura.



Hexaedro Como el hexaedro que representa, el grafo platónico hexaedro tiene 8 vértices y 12 aristas, formando 6 caras de cuatro lados. Como todos sabemos ya, la figura geométrica hexaedro recibe también el nombre de cubo refiriéndose al cubo de tres dimensiones, por lo que el grafo platónico hexaedro, coincide exactamente con el grafo que representa el cubo tridimensional. El grafo platónico hexaedro se encuentra representado planarmente en la siguiente figura.



Octaedro Como es bien conocido, un octaedro es una figura geométrica que, como su propio nombre indica, consta de ocho caras, en forma de triángulo. Como es lógico, el grafo que lo representa tiene sus mismas características, como ya hemos visto en los ejemplos anteriores, es decir, 6 vértices y 12 aristas. El grado de todos los vértices de este grafo, obviamente, es 4. El grafo platónico octaedro se encuentra representado planarmente en la siguiente figura.



Icosaedro Como en todos los casos anteriores el grafo platónico icosaedro, al representar la figura geométrica de la que toma nombre, posee también sus mismas características. En el caso del icosaedro, 12 vértices de grado 5, con 30 aristas, para lograr formar 20 caras triangulares. El grafo platónico icosaedro se encuentra representado planarmente en la siguiente figura.



Dodecaedro La última de las figuras representadas en la aplicación y, por lo tanto, contenidas en el presente texto, mediante un grafo platónico es la del dodecaedro. Este grafo contará, pues, con los mismos 20 vértices y las mismas 30 aristas que dan a la figura mencionada sus características 12 caras pentagonales. Para ello, los vértices de este grafo tienen todos grado 3. El grafo platónico dodecaedro se encuentra representado planarmente en la siguiente figura.



Herschel Se ha incluido en la aplicación el grafo atribuido a Herschel ya que tiene la particularidad de constituir el ejemplo más pequeño de grafo poliédrico no-hamiltoniano.



Harary Otra de las familias que se incluyen en el presente trabajo es la correspondiente a los grafos de Harary . Los grafos de Harary se definen mediante dos parámetros: el número de vértices del grafo, que se denota por n; y el grado mínimo que debe tener cada vértice del grafo, que se denota por k. Debido a esta notación, los grafos de Harary suelen describirse mediante la simbología: Hk, n. Estos grafos cumplen la propiedad de hacer que cada uno de sus vértices tenga, como mínimo grado k, pero utilizando para ello el mínimo número de aristas posible. Un ejemplo de este tipo de grafos, donde se pueden observar las características descritas es H11, 10.



Grafos enlazados. Los grafos enlazados se caracterizan porque, si numeramos sus vértices, las aristas del grafo enlazan vértices cuyo número se diferencia un una cantidad fija -que podemos llamar k-, es decir, siguiendo una determinada progresión lineal. Por ejemplo, si hacemos k=2, el vértice 1 se uniría al 3, el 2 al 4, y así sucesivamente con todos los vértices del grafo. Si en lugar de tener en cuenta tan sólo este valor de k, tomáramos una serie completa de valores k1, k2, ... , kn, obtendríamos un grafo que podríamos denominar n-enlazado. Los grafos enlazados más comunes son aquellos para los que n=1, que denotamos por Ln,r y aquellos en los que n=2, que denotamos por Ln,r,s . Enlazados L N, R Dado un grafo G, definido por un conjunto de vértices V y un conjunto de aristas A. Supongamos v1, ..., vn los vértices contenidos en V. Se dice que G es un grafo enlazado L n, r si cumple que: vi, vj ∈ V, tales que (j<r ∧ j+n=i+r) ∨ (j=r ∧ j=i+r), la arista (vi, vj) ∈ A Los grafos enlazados Ln, r se caracterizan porque todos sus vértices tienen grado dos. Para r>1, la forma de estos grafos, situando sus vértices en círculo, es de estrella, como se puede observar en el ejemplo de la figura. L5,2.



Enlazados L N, R, S

Dado un grafo G, definido por un conjunto de vértices V y un conjunto de aristas A. Supongamos v1, ..., vn los vértices contenidos en V. Se dice que G es un grafo enlazado Ln, r, s si cumple que: r ≠ s, vi, vj ∈ V, tales que (j<r ∧ j+n=i+r) ∨ (j=r ∧ j=i+r), la arista (vi, vj) ∈ A, y vk, vl ∈ V, tales que (l<r ∧ l+n=k+r) ∨ (l=r ∧ l=k+r), la arista (vk, vl) ∈ A Los grafos enlazados Ln, r, s se caracterizan porque todos sus vértices tienen grado cuatro. Un ejemplo de estos grafos es el que se puede observar en la figura L7, 2, 3.



Grafo de Petersen El grafo que aquí se presenta debe su nombre a que la primera persona que lo estudió fue Petersen en el año 1891. Las tres representaciones más habituales del grafo de Petersen.

Entre las muchas cualidades interesantes que presenta este grafo, podemos mencionar las siguientes. Es un grafo 3-regular y de cintura 5, siendo además, el grafo de orden mínimo que cumple estas características. Es un grafo de diámetro 2 lo que se traduce en que tiene 10 vértices de la forma más compacta posible. Tiene valor de conectividad y de arista-conectividad 3, característica esta que ha sido ampliamente estudiada en la rama de las redes de telecomunicaciones. No es un grafo hamiltoniano pero tiene la peculiaridad de que el subgrafo resultante de eliminar cualquiera de sus vértices sí lo es. Además, es el menor grafo con esta propiedad.



Grafo de Grötzsch. Otro de los grafos que por su relevancia han sido incluidos en la aplicación como grafo singular es el denominado grafo Grötzsch. Para entender el interés que presenta este grafo es necesario primero introducir algunos conceptos de la Teoría de Grafos. A continuación pasamos a definir brevemente tales conceptos. Para cualquier grafo G un subgrafo completo de G se denomina clique de G. El número de vértices del clique más grande de G se denomina el número clique de G y se denota por cl(G). Sea G un grafo. Un coloreado de vértices de G asigna colores, normalmente denotados por 1, 2, 3,... a los vértices de G, uno por cada vértice, de forma que vértices adyacentes tienen asignados colores diferentes. Un k-coloreado de G es un coloreado que consiste en k colores diferentes y, en ese caso, el grafo G se dice que es k-coloreable. El mínimo número “k” para el cual existe un k-coloreado del grafo G se denomina número cromático de G (o índice cromático de G) . Teorema: Para cada k≥1 existe un grafo k-cromático Mk que no tiene subgrafos triángulos (K3). De esta familia de grafos Mi denominada familia Mycielski, el de Grötzsch representa el grafo M4. La siguiente figura muestra una representación del grafo de Grötzsch.



Grafo de Heawood

Se trata de un grafo 3-regular de cintura 6 con menor número de vértices.



Tutte El grafo de Tutte es un grafo planar, 3-conexo no hamiltoniano. El aspecto más importante que presenta este grafo es que se utiliza para refutar la conjetura de Tait, que afirmaba que "todo grafo 3-regular, 3-conexo y planar es hamiltoniano". Esta conjetura tenía importancia para demostrar de una forma sencilla el teorema de los cuatro colores, pero fracasó a causa de este grafo contraejemplo. Una representación de este grafo como la de la figura nos permitirá comprobar las propiedades descritas.



Tipos de rutas

A continuación definiremos algunos conceptos sobre rutas que debemos conocer para comprender algunos de los algoritmos explicados. Definiremos: Camino.

Recorrido. Camino simple. Camino cerrado. Ciclo. Circuito. Un camino “w” simple en un grafo G es una sucesión de alternada de vértices y aristas o arcos (si es dirigido) w: v0e1v1e2v2…vn-1envn comenzando y terminando con vértices tal que ei = vi-1vi con 1≤ i ≤ n. Diremos que “w” tiene longitud “n” si posee “n” aritas. Un camino de longitud cero se denomina camino trivial. Ejemplo.

Camino 1: v1v3v5v2v4v3v1v2. Camino 2: v4v2v5v3v1.



Un recorrido o trayectoria es un camino donde no se repiten aristas. Un posible ejemplo basándonos en el grafo anterior.

Recorrido 1: v4v2v5v3v1.

Recorrido 2: v5v3v1v2.

Un camino simple es un camino en el que no se repiten vértices.

Camino simple: v4v2v5v3v1.

Un ciclo es un camino simple v0v1…vn con n ≥ 3, v0 = vn y los “n” vértices son distintos. Al ciclo de longitud “n” lo denominaremos n-ciclo.

Ciclo: v1v3v5v2v1

Un ciclo es un camino cerrado que cumple las propiedades anteriores y un camino simple es un camino abierto.

Un camino cerrado donde no se repiten es un circuito.

Circuito: v1v2v5v3v2v4v3v1.

Vértices repetidos Aristas repetidas Abierto Cerrado Tipo ruta SI SI Camino SI SI SI Camino cerrado SI NO Recorrido SI NO SI Circuito NO NO SI Camino simple NO NO SI Ciclo



Grafo complementario. El grafo complementario de G (Ĝ) es un grafo con V(Ĝ) = V(G) y tal que si uv es una arista de Ĝ si y solo si uv no es una arista de G. Ejemplo 1. (Grafo no dirigido)

Grafo complementario.



Ejemplo 2. (Grafo dirigido).

Grafo complementario.



Grafo de línea. El grafo de línea L(G) de G es un grafo que posee tantos vértices como aristas tiene G, es decir, | V(L(G)) | = | E(G) |. Dos vértices “v” y “u” de L(G) son adyacentes si “u” y “v” son aristas de G y inciden en un mismo vértice.

Ejemplo 1

Grafo de línea.



Ejemplo 2.

Grafo de línea.



3.- Algoritmos implementados.

3.1.- Algoritmos sobre caminos mínimos.

Algoritmo de Dijkstra. Sea G un grafo ponderado no trivial la distancia entre dos vértices u y v en G es la longitud mínima ponderada de todos los caminos u-v en G, si existe, en otro caso infinito. El algoritmo de Dijkstra calcula la distancia en desde un vértice fijo tomado como origen al resto de vértices del grafo. Dicho algoritmo se ha implementado mediante técnicas de programación dinámica haciendo uso de una tabla en la que se van realizando una serie de cálculos previos para encontrar la distancia mínima entre el vértice origen y el resto de vértices del grafo. Para llevar a cabo la implementación se ha usado una tabla bidimensional la cual posee tantas filas y columnas como vértices posee el grafo. Además se utilizan dos variables temporales “m” y “Vi“ las cuales se van machacando en cada iteración las cuales almacenaran la distancia mínima recorrida hasta el momento y el vértice en el que nos encontramos actualmente en un determinado instante de la ejecución respectivamente. Inicialmente la variable “m” tiene el valor cero y “Vi“ almacena el vértice origen.

Además debemos saber que en cada posición se almacena una tupla de dos componentes. En la primera componente se almacena la distancia desde el vértice “Vi“ al vértice que ocupa una determinada columna. Y en la segunda almacenamos el vértice padre del vértice que ocupa la columna, que en cada iteración será “Vi“, a partir del cual se reconstruirá el camino mínimo.

Una vez que tenemos claro la información que contiene dicha tabla

podemos rellenarla siguiendo los siguientes pasos. La primera fila tiene de la tabla se inicializa por defecto con la tupla

(∞, -1). El “-1” indica que el vértice de la columna aún no tiene asignado ningún padre.



En cada iteración se rellena una fila, siguiendo los siguientes pasos: 1.- Buscamos los vértices adyacentes al vértice “Vi“ y en la columna

correspondiente al adyacente. Si la distancia total recorrida hasta el momento más la distancia entre

“Vi“ y el adyacente es menor o igual que la ya recorrida entonces actualizamos la tupla con la nueva distancia y vértice padre.

Es importante actualizar la tabla si la distancia es igual ya que así

conseguiremos obtener varias rutas mínimas entre el vértice origen y destino. 2.- A continuación tomamos como nuevo vértice “Vi“, el vértice

correspondiente a la columna cuya distancia es mínima. Una vez escogido el vértice cuya distancia es mínima la columna queda cerrada, es decir no vuelve a considerarse para rellenar el resto de la tabla.

Una vez que tenemos rellenada la tabla reconstruir el camino mínimo a partir de la misma es bastante fácil. Se ha optado por reconstruir el camino desde el vértice destino al vértice origen, por lo que el primer vértice que forma parte del camino parcialmente construido es el vértice destino.

Acto seguido nos situamos en la primera posición distinta de “*” de la

columna correspondiente al vértice destino comenzando por la parte inferior de la tabla y el vértice padre es el siguiente que forma parte del camino. La longitud del camino viene determinada por la distancia almacenada en dicha posición.

Ahora nos situamos en la columna del vértice padre y repetimos el

proceso anterior hasta llegar al vértice origen. En ese momento tendremos el camino mínimo completo.

Para que la exposición del algoritmo quede totalmente clara expondremos algunos ejemplos.



Ejemplo 1

Aplicamos el algoritmo de Dijkstra para encontrar el camino mínimo entre el vértice v1 y v8 obteniendo la siguiente tabla.

V1 (v2,P(v2)) (v3,P(v3)) (v4,P(v4)) (v5,P(v5)) (V6,P(v6)) (v7,P(v7)) (v8,P(v8)) m Vi

(0,NP) (∞,NP) (∞,NP) (∞,NP) (∞,NP) (∞,NP) (∞,NP) (∞,NP) 0 V1 * (2,v1) (3,v1) (∞,NP) (∞,NP) (∞,NP) (∞,NP) (∞,NP) 2 V2

* * (3,v1) (3,v2) (3,v2) (∞,NP) (∞,NP) (∞,NP) 3 V3

* * * (3,v2) (3,v2) (∞,NP) (6,v3) (∞,NP) 3 V4

* * * * (3,v2) (4,v4) (6,v3) (∞,NP) 3 V5

* * * * * (4,v5) (6,v3) (∞,NP) 4 V6

* * * * * * (6,v3) (8,v6) 6 V7

* * * * * * * (8,v7) 8 V8

A continuación reconstruiremos el camino desde el vértice v1 a vértice v8

comenzando por este último. Para ir desde el vértice v8 al vértice v1 es necesario pasar por el padre

de v8. El camino construido hasta el momento es v8 � v7 � ... � v1. Seguidamente miraríamos quien es el padre del último vértice que forma

parte del camino parcialmente construido, en este caso es v3 y así sucesivamente.



El camino completo es: v8 {P(v8)} � v7 {P(v7)} � v3 {P(v3)} � v1 {P(v1)}. Camino mínimo: v1 � v3 � v7 � v8. La longitud del camino es 8. Podemos observar en la columna del vértice de destino que existen dos

tuplas con padres distintos e igual distancia lo cual no índica que existe más de un camino mínimo.

Reconstrucción del segundo camino: v8 {P(v8)} � v6 {P(v6)} � v5 {P(v5)} � v2 {P(v2)} � v1 {P(v1)}. Camino mínimo: v1 � v2 � v5 � v6 � v8. La longitud del camino es 8. Podemos observar que en la columna correspondiente al vértice V6

existen dos tuplas con padres distintos y misma distancia por lo que existe otro camino mínimo más.

Reconstrucción del tercer camino: v8 {P(v8)} � v6 {P(v6)} � v4 {P(v4)} � v2 {P(v2)} � v1 {P(v1)}. Camino mínimo: v1 � v2 � v4 � v6 � v8. La longitud del camino es 8.



Ejemplo 2


V1 (v2,P(v2)) (v3,P(v3)) (v4,P(v4)) (v5,P(v5)) m Vi (0,NP) (∞,NP) (∞,NP) (∞,NP) (∞,NP) 0 V1

* (5,v1) (4,v1) (∞,NP) (∞,NP) 4 V3

* (5,v1) * (12,v3) (6,v3) 5 V2

* * * (7,v2) (6,v3) 6 V5

* * * (7,v5) * 7 V4

Recontracción del primer camino mínimo desde el vértice v1 a v4. V4 {P(v4)} � v5 {P(v5)} � v3 {P(v3)} � v1 {P(v1)}. Camino mínimo: v1 � v3 � v5 � v4. La longitud del camino es 7. Recontracción del segundo camino mínimo desde el vértice v1 a v4. V4 {P(v4)} � v2 {P(v2)} � v1 {P(v1)}. Camino mínimo: v1 � v2 � v4. La longitud del camino es 7.



Ejemplo3




V1 (v2,P(v2)) (v3,P(v3)) (v4,P(v4)) (v5,P(v5)) m Vi

(0,NP) (∞,NP) (∞,NP) (∞,NP) (∞,NP) 0 V1 * (1,v1) (∞,NP) (∞,NP) (∞,NP) 1 V2

* * (4,v2) (∞,NP) (∞,NP) 4 V3

* * * (∞,NP) (∞,NP)

* * * * *

En este caso observamos que el vértice destino no tiene padre asignado, lo cual nos indica que el grafo no es conexo, por lo que no existe ningún camino entre el vértice origen y destino.



Algoritmo de Floyd.

El algoritmo de Floyd calcula el camino mínimo entre todos los pares de vértices del grafo ponderado y no negativo mediante técnicas de programación dinámica.

Para ello calcularemos una serie de matrices Dk[i,j] que debe cumplir:

Donde Dk[i, j] = mínimo(Dk-1[i,k] + Dk-1[k,j]), D[i][j]). Longitud del camino más corto para ir desde el vértice “i” al vértice “j” pudiendo pasar por los vértices 1,2,..., hasta k. Básicamente la expresión anterior nos dice: “si para ir desde el vértice “i” al “j” mejoramos pasando por el vértice “k”, este se añade al camino. Además para reconstruir el camino se hace uso de una matriz de trayectorias donde en cada iteración si se mejora el camino desde el vértice “i” al vértice “j” pasado por “k”, este se anota en la matriz de trayectorias. El algoritmo de Floyd quedaría: Func floyd (ady: Array[1..n,1..n] de entero) dev(D: Array[1..n,1..n] de entero, p: Array[1..n,1..n] de entero )

var i,j,k: Entero

prin desde i=1 hasta n

desde j=1 hasta n desde k=1 hasta n si k <> i y k<>j si D[i,j] > D[i,k] + D[k,j] D[i, j] := D[i,k] + D[k,j] P[i,j] := k // Vértice de paso. fsi fsi fdesde

fdesde fdesde

Dk-1[i, k]+ Dk-1[k, j] (pasando por k). Dk-1[i, j] (no pasando por k).

Dk[i, j] =



fin

A continuación veremos un ejemplo con más detalle:

Ejemplo1

Calcularemos la sucesión de matrices Dk. Sea M[i,j] la matriz de adyacencias del grafo. M [j, j] = Primera iteración D1 representa el camino más corto para ir desde vértice “i” al vértice “j” pudiendo pasar únicamente por el vértice 1. D1 = P[i,j] =

V1 V2 V3 V4 V1 0 5 ∞ ∞ V2 50 0 15 5 V3 30 ∞ 0 15 V4 15 ∞ 5 0

V1 V2 V3 V4 V1 0 5 ∞ ∞ V2 50 0 15 5 V3 30 35 0 15 V4 15 20 5 0

V1 V2 V3 V4 V1 0 0 0 0 V2 0 0 0 0 V3 0 1 0 0 V4 0 1 0 0



D2 representa el camino más corto para ir desde vértice “i” al vértice “j” pudiendo pasar únicamente por el vértice 1 y 2. D2 = P[i,j] =

D3 representa el camino más corto para ir desde vértice “i” al vértice “j” pudiendo pasar únicamente por el vértice 1, 2 y 3. D3 = P[i,j] = D4 representa el camino más corto para ir desde vértice “i” al vértice “j” pudiendo pasar únicamente por el vértice 1, 2, 3 y 4. En la última etapa se consideran todos los vértices del grafo. D4 = P[i,j] =

V1 V2 V3 V4 V1 0 5 20 10 V2 50 0 15 5 V3 30 35 0 15 V4 15 20 5 0

V1 V2 V3 V4 V1 0 0 2 2 V2 0 0 0 0 V3 0 1 0 0 V4 0 1 0 0

V1 V2 V3 V4 V1 0 5 20 10 V2 45 0 15 5 V3 30 35 0 15 V4 15 20 5 0

V1 V2 V3 V4 V1 0 0 2 2 V2 3 0 0 0 V3 0 1 0 0 V4 0 1 0 0

V1 V2 V3 V4 V1 0 5 15 10 V2 20 0 10 5 V3 30 35 0 15 V4 15 20 5 0

V1 V2 V3 V4 V1 0 0 4 2 V2 4 0 4 0 V3 0 1 0 0 V4 0 1 0 0



¿Cómo se reconstruye el camino?. Para ir desde un vértice vi a un vértice vj consultamos la posición P[i,j] de la matriz de trayectorias:

Si es “0” entonces existe camino directo para ir desde el vértice “i” al “j” y el camino se obtiene directamente.

En otro caso sea Vpaso = P[i,j]. Ahora visitamos la posición P[Vpaso,j]

repitiendo el mismo proceso. Reconstrucción del camino mínimo para ir desde el vértice v2 al vértice v3.

P[2,3] = 4 por lo que para ir de v2 a v3 es necesario pasar por el vértice 4. P[4,3] = 0 existe camino directo. Camino mínimo: v2 � v4 � v3.



3.2.- Algoritmos de distancias.

Excentricidad de un vértice. La excentricidad de un vértice “v” de un grafo G es la distancia de “v” al vértice más alejado de él, es decir, se trata de la mayor longitud del camino más corto entre el vértice y cualquier otro. Para implementar el algoritmo pueden seguirse los siguientes pasos: 1.- Calculamos Dijsktra desde el vértice “v” a resto de vértices del grafo. 2.- Finalmente de todos los caminos mínimos obtenidos tomamos la longitud mayor. Seguidamente veremos un ejemplo. Para el grafo de la figura calcularemos la excentricidad del vértice v1.

Distancia mínima Valor camino mínimo distmin(v1, v2) 5 distmin(v1, v3) 4 distmin(v1, v4) 7 distmin(v1, v5) 6



La excentricidad es 7.



Radio de un grafo. El radio de un grafo G es la excentricidad más pequeña de cualquiera de sus vértices. Para implementar el algoritmo pueden seguirse los siguientes pasos:

1.- Para cada vértice obtenemos la excentricidad. 2.- Obtener la excentricidad más pequeña. Veamos un ejemplo.

Para el grafo de la figura calcularemos el radio.






Distancia mínima Valor camino mínimo

distmin(v4, v1) 7 distmin(v4, v2) 2 distmin(v4, v3) 3 distmin(v4, v5) 1

Distancia mínima Valor camino mínimo


Como sabemos la excentricidad de cada vértice es la mayor longitud del camino más corto. A partir de los cálculos realizados con anterioridad podemos obtener una tabla con la excentricidad de cada vértice. Para obtener el radio basta con obtener el mínimo del array.

v1 v2 v3 v4 v5

7 5 5 7 6



Diámetro de un grafo. El diámetro de un grafo G es la mayor distancia existente entre dos vértices cualesquiera del grafo, es decir, es la excentricidad más grande de cualquiera de sus vértices. Para implementar el algoritmo pueden seguirse los siguientes pasos:

1.- Para cada vértice obtenemos la excentricidad. 2.- Obtener la excentricidad máxima. Veamos un ejemplo:

Para el grafo de la figura obtendremos el diámetro, aprovechado los cálculos anteriores realizados para el radio. El diámetro del grafo es 7.



Distancia de un vértice. La distancia de un vértice "v" en un grafo G ponderado o no, es la suma de las distancias mínimas a todos los vértices del grafo. Para implementar el algoritmo pueden seguirse los siguientes pasos: 1.- Calcula Dijsktra para todos los vértices del grafo. 2.- Sumar todas las distancias. Si entre un vértice “v” y otro cualquiera existiera más de un camino mínimo solo se tendrá en cuenta un de los caminos a la hora sumar las distancias. Veamos un ejemplo: Para el grafo de la figura calcular la distancia del vértice v1 y v5.




distancia 22 Distancia mínima Valor camino mínimo


distancia 12 Antes de comentar los algoritmos de la mediana y el centro de un grafo

definiremos el concepto de subgrafo inducido por el conjunto de vértices del grafo. Sea “S” un conjunto de vértices no vació de un grafo G. El subgrafo inducido por “S” es el subgrafo maximal de G, con vértices en el conjunto “S”. Las aristas que forman parte del subgrafo inducido son todas las aristas de G que inciden o unen vértices de S.



Algoritmo de la mediana.

La mediana de un grafo G es el subgrafo inducido por los vértices que tienen mínima distancia.

Para implementar el algoritmo pueden seguirse los siguientes pasos:

1.- Calcular la distancia de cada vértice. . 2.- Escoger el subconjunto de vértices de mínima distancia. 3.- Construir el subgrafo inducido por dicho conjunto de vértices obtenidos en el paso 2.

Veamos un ejemplo.

Calcular la mediana en el siguiente grafo.

distancia(V1) 22 distancia(v2) 15 distancia(v3) 14 distancia(v4) 13 distancia(v5) 12



En este caso la mediana del grafo esta formada por un único vértice. Dicho vértice es v5.

Algoritmo del centro.

El centro de un grafo G, es el subgrafo inducido por los vértices que tienen excentricidad mínima.

Para implementar el algoritmo pueden seguirse los siguientes pasos:

1.- Para cada vértice calculamos la excentricidad. 2.- Escoger el subconjunto de vértices de mínima excentricidad. 3.- Construir el subgrafo inducido por dicho conjunto de vértices

obtenidos en el paso 2.

Veamos un ejemplo

Aprovechamos el cálculo de la excentricidad realizado anteriormente.

v1 v2 v3 v4 v5

7 5 5 7 6



El subconjunto de vértices de mínima excentricidad esta formado por los vértices v2 y v3.



3.3.- Conectividad.

Algoritmo de componentes conexas. Se trata de determinar si un grafo dirigido o no, es conexo o no lo es. Podemos usar la propiedad de que si un grafo es conexo es porque existe camino entre todo par de vértices o, lo que es lo mismo, a partir de cualquier vértice es posible alcanzar a todos los demás. Para la implementación se realiza mediante técnicas de programación dinámica. Se hace uso de un array en la que cada posición hace referencia a un vértice del grafo. Aquellas posiciones que al finalizar la ejecución posean el mismo valor estarán conectadas y formaran parte de la misma componente conexa. Inicialmente se suponen todos los vértices desconectados por lo que todas las posiciones del array tienen un valor distinto. Seguidamente se itera sobre las aristas o matriz de adyacencias del grafo, de tal forma que si existe una aritas entre el vértice correspondiente a la fila “i” y columna “j” se almacena en dos variables la componente mayor y menor respectivamente. Acto seguido se itera sobre el array de componente de tal forma que todas las posiciones donde el valor es igual a la componente mayor se actualizan con el valor de la componente menor, es decir, a vértices conectados se les asigna el mismo valor y se pasa a la siguiente arista repitiendo dicho proceso. Tras iterar sobre todas las aristas el array almacena tantos números distintos como componentes conexas tiene el grafo. Dicha componente conexa viene determinada por el subgrafo inducido de los vértices que pertenecen a dicha componente conexa. Veamos un ejemplo



v1 v2 v3 v4 v5 v6 Mayor Menor 1 2 3 4 5 6 * *

En principio todos los vértices están desconectados.

v1 v2 v3 v4 v5 v6 Mayor Menor 1 2 3 1 5 6 4 1

El vértice v1 y v4 están conectados. Actualizada la posición del vértice v4.


El vértice v2 y v5 están conectados. Actualizada la posición del vértice v5.


El vértice v3 y v6 están conectados. Actualizada la posición del vértice v6. Como puede apreciarse el grafo posee tres componentes conexas que son v1v4 , v2v5 y v3v6 .



Vértices de corte. Sea G un grafo y “v” un vértice de G. Se dice que “v” es un vértice de corte si al eliminar el vértice del grafo este es no conexo, es decir, el número de componentes conexas es mayor que uno. La implementación del algoritmo consta de los siguientes pasos: 1.- Calculamos las componentes conexas que posee inicialmente el grafo.

2.- Eliminamos un vértice del grafo.

3.- En estas condiciones se calculan el número de componentes conexas. Si el número de componentes actuales es distinto del número de componentes calculadas inicialmente más uno, entonces se trata de un vértice de corte.

4.- Restauramos el vértice borrado, así como sus aristas y repetimos el proceso con el resto de vértices (ir al paso 2).

Ejemplo

El grafo posee tres vértices de corte: v3, v4, v7. Basta observar que si eliminamos algunos de estos vértices el grafo no es conexo.



Aristas puente. Una arista “e” en un grafo G se dice que es una arista puente si al eliminar la arista del grafo, este deja de ser conexo. La implementación del algoritmo consta de los siguientes pasos: 1.- Calculamos las componentes conexas que posee inicialmente el grafo.

2.- Eliminamos una arista del grafo.

3.- En estas condiciones se calculan el número de componentes conexas. Si el número de componentes actuales es distinto del número de componentes calculadas inicialmente entonces se trata de una arista puente.

4.- Restauramos la arista del grafo y repetimos el proceso para el resto de aristas del grafo. (Ir al paso 2) Ejemplo

Las aristas puentes son v4v5, v6v5 y v3v7.



Bloques. Un bloque B de un grafo G conexo es un subgrafo no separable de G y mayor con esta propiedad. Los bloques permiten hacer una partición en el conjunto de las aristas. Un grafo conexo no trivial sin vértices de corte recibe el nombre de grafo no separable. Un subgrafo G1 de G es maximal con respecto a una propiedad si no hay ningún otro subgrafo que también posea esa propiedad y que contenga a G. Algunas propiedades.

a) Si G es no separable G es un bloque.

b) Los bloques permiten hacer una partición del conjunto de las aristas.

c) Cada dos bloques a lo sumo tienen un vértice en común y este es un vértice de corte.

d) Un bloque con exactamente un vértice de corte se denomina bloque final.

e) Un grafo G conexo con al menos un vértice de corte tiene como mínimo dos bloques.

f) Una arista puente es considerada un bloque. El algoritmo para el cálculo de bloque consta de 6 pasos:

1.- Calcular los vértices de corte y aristas puente del grafo.

2.- Eliminar los vértices de corte del grafo (guardando las aristas).

3.- Calcular las componentes conexas.

4.- Restaurar los vértices de corte junto con las aristas y eliminar las aristas puente del grafo.



5.- Para cada vértice de corte y aristas de cada componente conexa. Si G existe una arista formada por el vértice de corte y el vértice origen o destino (o al contrario, es decir, el vértice origen o destino y el vértice de corte en caso de ser un grafo dirigido) de una arista de la componente conexa actualmente procesada almacenamos la arista formada por el vértice de corte en un conjunto S. Una vez procesadas todas las aristas de la componente conexa actual, añadimos todas las aristas almacenadas en S, a la componente actual, obteniendo las aristas de uno de los bloques del grafo.

6.- Finalmente añadimos como bloques todas las aristas puente del grafo a la vez que las restauramos en el grafo G. A continuación veremos un ejemplo para cada tipo de grafo. Ejemplo para un grafo no dirigido.

PASO 1.

Vértices de corte {v5}.

Aristas puente {v4v5, v5v6}.



PASO 2.

Eliminamos el vértice de corte y guardamos las aristas eliminadas {v5v6, v5v4, v1v5, v3v5}.

PASO 3. Componentes conexas {{v1v2, v1v3, v3v2}, {v4}, {v6}}. PASO 4.

Restauramos el único vértice de corte v5 junto con las aristas eliminadas {v5v6, v5v4, v1v5, v3v5} y eliminamos las aristas puente.



PASO 5. Comprobamos si en el grafo existe alguna arista formada por v5 y algún vértice de las aristas de la componente conexa. Este proceso se realiza para cada una de las componentes conexas. Componentes conexas {{v1v2, v1v3, v3v2}, {v4}, {v6}}. Primera componente conexa {v1v2, v1v3, v3v2}.

Conjunto de aristas encontradas {v5v1, v5v3}. Añadimos las aristas encontradas a la lista de aristas de la primera componente conexa obteniendo las aristas del primer bloque.

Bloque 1 {v1v2, v1v3, v3v2, v5v1, v5v3}.

El resto de componentes conexas nos las saltamos, pues no tienen aristas que procesar. PASO 6 Finalmente añadimos las aristas puente como bloque del grafo. Bloque 2 {v4v5}. Bloque 3 {v5v6}. Bloques del grafo: Bloque 1 {v1v2, v1v3, v3v2, v5v1, v5v3}. Bloque 2 {v4v5}. Bloque 3 {v5v6}.



Ejemplo para un grafo dirigido.

PASO 1.

Vértices de corte {v2, v3}. Aristas puente {v2v3}.



PASO 2.

Eliminamos el vértice de corte y guardamos las aristas eliminadas {v2v3, v2v5, v1v2, v4v2, v3v6, v3v7}.

PASO 3.

Componentes conexas {{v1v5, v5v4}, {v6v7}}.



PASO 4.

Restauramos los vértices de corte junto con las aristas eliminadas {v2v3, v2v5, v1v2, v4v2, v3v6, v3v7} y eliminamos las aristas puente.

PASO 5.

Comprobamos si en el grafo existe alguna arista formada por algún vértice de corte y algún vértice de las aristas de la componente conexa. Este proceso se realiza para cada una de las componentes conexas.

Componentes conexas {{v1v5, v5v4}, {v6v7}}. Primera componente conexa {v1v5, v5v4}.

Conjunto de aristas encontradas {v2v5, v1v2, v4v2}

Con el vértice v3 no se encontró ninguna arista. Añadimos las aristas encontradas a la lista de aristas de la primera componente conexa obteniendo las aristas del primer bloque.

Bloque 1 {v1v5, v5v4, v2v5, v1v2, v4v2}.



Segunda componente conexa {v6v7}.

Conjunto de aristas encontradas {v3v6, v3v7}.

Con el vértice v2 no se encontró ninguna arista. Añadimos las aristas encontradas a la lista de aristas de la segunda componente conexa obteniendo las aristas del segundo bloque.

Bloque 2 {v6v7, v3v6, v3v7}.

PASO 6 Finalmente añadimos las aristas puente como bloque del grafo. Bloque 3 {v2v3}. Bloques del grafo: Bloque 1 {v1v5, v5v4, v2v5, v1v2, v4v2}.

Bloque 2 {v6v7, v3v6, v3v7}.

Bloque 3 {v2v3}.



3.4.- Algoritmos de búsquedas.

Búsqueda en profundidad (DFS) .

El algoritmo de recorrido en profundidad, en inglés depth-first search y que denotaremos DFS para abreviar, permite obtener un árbol recubridor del grafo original.

Si G es un grafo un grafo conexo, el algoritmo de búsqueda en

profundidad obtiene un árbol recubridor de G. Se trata de un grafo en el que aparecen todos los vértices de G, pero no todas sus aristas.

El árbol recubridor no es único depende del vértice de partida. El algoritmo puede implementarse mediante una pila, de tal forma que el

vértice activo o a partir del cual se expande el árbol siempre se encuentra en la cima de la pila.

En cada paso se introduce en la pila unos de los vértices adyacentes al

vértice activo, añadiéndose al árbol recubridor la arista que une el vértice activo con dicho adyacente.

Puede ocurrir que el vértice activo no posea adyacentes o que todos

hayan sido visitados con anterioridad y aún no se han visitados todos los vértices del grafo, en tal caso el vértice es retirado de la pila y continuamos con el proceso con el nuevo vértice activo.

El algoritmo termina cuando la pila está completamente vacía, lo que es

equivalente a decir que todos los vértices del grafo han sido visitados. Seguidamente detallaremos los pasos del algoritmo en un ejemplo. Ejemplo



Aplicaremos el algoritmo de búsqueda en profundidad comenzando por el vértice v1

Pila Vértices Aristas Visitados v1 v2 v1 v2 v1 v2

v1 v2 v3 v2 v3 v1 v2 v3 v1 v2 v3 v5 v3 v5 v1 v2 v3 v5

v1 v2 v3 v5 * * v1 v2 v3 v5 v1 v2 v3 v6 v3 v6 v1 v2 v3 v5 v6

v1 v2 v3 v6 v4 v6 v4 v1 v2 v3 v5 v6 v4 v1 v2 v3 v6 v4 * *

v1 v2 v3 v6 * * v1 v2 v3 * *

v1 v2 * * v1 * *

Pila vacía * * La columna de vértices visitados puede ser útil para no introducir en la

pila vértices considerados anteriormente. Además afinando un poco mas y aprovechado el conjunto de vértices visitados podemos para la ejecución del algoritmo cuando dicho conjunto contenga todos los vértices del grafo sin necesidad de vaciar la pila.

Orden en el que se visitan los vértices: v1, v2, v3, v5, v6 y v4. Puede observarse que el árbol recubridor construido depende del vértice

de partida y del orden en el que se visiten los adyacentes al vértice activo. Árbol recubridor obtenido:



Búsqueda en anchura (BFS) .

El algoritmo de recorrido en anchura, en inglés breadth-first search y que denotaremos BFS para abreviar, al igual que el algoritmo de búsqueda en profundidad permite obtener un árbol recubridor donde los vértices son recorridos por niveles.

Al igual que en el caso anterior, si el grafo es conexo se encuentra el

árbol recubridor, el cual no es único, dependerá del vértice de partida el orden en que se visitan los vértices adyacentes al vértice activo.

El algoritmo puede implementarse mediante una cola, de tal forma que el

vértice activo o a partir del cual se expande el árbol siempre se encuentra en la cabeza de la cola.

En cada paso se introduce en la cola unos de los vértices adyacentes al vértice activo, añadiéndose al árbol recubridor la arista que une el vértice activo con dicho adyacente. Los vértices adyacentes son introducidos por el final de la cola de tal forma que el vértice activo no cambia, hasta que este se queda sin adyacentes, en este momento el vértice es extraído de la cola y se repite el proceso con el resto de vértices, hasta que todos los vértices del grafo han sido visitados.

Seguidamente detallaremos los pasos del algoritmo en un ejemplo. Ejemplo



Aplicaremos el algoritmo de búsqueda en anchura comenzando por el vértice v1.

Cola Vértices Aristas Visitados

v1 v2 v1 v2 v1 v2 v2v1 v4 v1 v4 v1 v2 v4

v4 v2v1 v6 v1 v6 v1 v2 v4 v6 v4 v2 * * v1 v2 v4 v6 v4 v2 v3 v2v3 v1 v2 v4 v6 v3

v3v4 v2 * * v1 v2 v4 v6 v3 v3v4 * * v1 v2 v4 v6 v3 v3 v5 v3 v5 v1 v2 v4 v6 v3 v5

v5 v3 * * v5 * *

Cola vacía * *

La columna de vértices visitados puede ser útil para no introducir en la cola vértices considerados anteriormente. Además afinando un poco mas y aprovechado el conjunto de vértices visitados podemos para la ejecución del algoritmo cuando dicho conjunto contenga todos los vértices del grafo sin necesidad de vaciar la cola.

Orden en el que se visitan los vértices: v1, v2, v4, v6, v3 y v5. Puede observarse que el árbol recubridor construido depende del vértice

de partida y del orden en el que se visiten los adyacentes al vértice activo. Árbol recubridor obtenido:



3.5.- Árboles recubridores de peso mínimo.

Se han implementado dos algoritmos que devuelven un árbol recubridor o un bosque de peso mínimo si el grafo no es conexo.

Algoritmo de Boruvka.

El algoritmo de Boruvka obtiene un árbol recubridor mínimo en un grafo G ponderado y conexo (no se admiten ponderaciones negativas). El algoritmo de Boruvka consiste en elegir desde cada vértice la arista de menor peso que sale de él, y así formar al inicio un conjunto de componentes de vértices unidos por dichas aristas. A partir de entonces en cada paso se busca la arista de menor peso entre los vértices de cada componente y un vértice que no lo sea, es decir, cada componente se unirá a otra distinta. El algoritmo termina cuando todos los vértices del grafo pertenecen a la misma componente. A este algoritmo también se le denomina "el algoritmo de las burbujas". El grafo se cubre por una colección de burbujas y en cada paso cada burbuja se adhiere a su burbuja más cercana. Aplicar Boruvka al siguiente grafo ponderado y conexo.



Paso 1 Elegimos de cada vértice la arista de menor para formar un conjunto de componentes de vértices.



Paso 2 Buscamos las aristas de menor peso entre vértices de componentes distintas.

Como el grafo ya es conexo el algoritmo termina. El peso del árbol recubridor es 16.



Veamos otro ejemplo.

Paso 1 Elegimos de cada vértice la arista de menor para formar un conjunto de componentes de vértices.



Paso 2 Buscamos las aristas de menor peso entre vértices de componentes distintas.

Repetimos dicho proceso hasta que el grafo sea conexo.



El grafo ya es conexo por lo que el algoritmo termina. El peso del árbol recubridor es 66.



Algoritmo de Prim.

El algoritmo de Prim obtiene un árbol recubridor mínimo en un grafo G ponderado (no se admiten ponderaciones negativas) y conexo.

La implementación del algoritmo se ha realizado partiendo de un vértice

que puede proporcionar el usuario, aunque no es obligatorio. Además sea cual sea el vértice de partida el árbol recubridor siempre tendrá el mismo peso mínimo.

El algoritmo comienza con un vértice y en cada interacción añade al

grafo una arista de peso mínimo la cual tiene como origen un vértice perteneciente al árbol parcialmente construido y como destino un vértice perteneciente al grafo G y que no formaba parte del árbol, de tal forma que no pueda insertarse ningún ciclo.

Dicho proceso se lleva a cabo hasta que todos los vértices de G han

sido visitados. Veamos un ejemplo:

Aplicar Prim al siguiente grafo ponderado y conexo.



Como vértice de partida tomaremos el vértice “v1”. T0 = { v1}. T1 = T0 + {v1, v6}. T2 = T1 + {v1, v4}. T3 = T2 + {v4, v7}. T4 = T3 + { v4, v5}. T5 = T4 + { v3, v5}. T6 = T5 + { v2, v4}. T7 = T6 + { v5, v8}. Peso del árbol recubridor = 16. Árbol recubridor obtenido:



Algoritmo de Kruskal.

El algoritmo de Kruskal obtiene un árbol recubridor de peso mínimo en un grafo G ponderado (no se admiten ponderaciones negativas) y conexo. Si el grafo G no es conexo obtiene un bosque de peso mínimo.

Como paso previo se realiza un preprocesamiento a las aristas del grafo

ordenándolas de menor a mayor según su ponderación. En cada iteración se añade una arista de peso mínimo que no forme

ciclo con el árbol recubridor parcialmente construido. Dicho algoritmo se ha implementado mediante técnicas de programación

dinámica haciendo uso de una tabla en la que se van realizando una serie de cálculos previos para encontrar el árbol recubridor de peso mínimo.

Para llevar a cabo la implementación se ha usado una tabla bidimensional con la cual tiene un número de columnas igual al número de aristas del grafo más uno y el número de columna igual al número de vértices.

Además haremos uso de dos variables “m” y “M” para almacenar el valor

de la componente de menor y mayor respectivamente. Para rellenar la tabla se debe siguientes los siguientes pasos. Paso 1 La primera fila se rellena con el número de fila correspondiente al vértice

en la matriz de adyacencias. El resto de filas se corresponden con las aristas ordenadas de menor a

mayor peso. Paso 2 Ahora rellenaremos las filas correspondientes con las aristas. Sea una

arista e1 que une los vértice u y v. En la fila anterior obtenemos el valor correspondiente a la columna que

indique u y v mediante la fila o columna correspondiente a la matriz de adyacencias del grafo. El valor máximo se almacena en “M” y el valor mínimo en “m”.

Si ambos valores son distintos entonces la arista forma parte del árbol

recubridor puesto que al añadirla no se introduce ningún ciclo.



A continuación podemos rellenar la fila correspondiente a dicha arista teniendo en cuenta los valores calculados en la fila anterior.

Para obtener los valores de la fila correspondientes a la arista copiamos

los valores de la fila anterior excepto cuando el valor de la fila anterior sea igual a M en cuyo caso se machara con el valor de la componente de menor “m”.

Este proceso se repite hasta que terminemos con todas las aristas del

grafo.

Veamos un ejemplo:

Aplicar Kruskal al siguiente grafo ponderado y conexo.



Árbol recubridor de peso mínimo obtenido.

El peso del árbol recubridor es 16.

arista comp(v1) comp(v2) comp(v3) comp(v4) comp(v5) comp(v6) comp(v7) comp(v8) m M arista 1 2 3 4 5 6 7 8 * * *

e1={v1,v6} 1 2 3 4 5 1 7 8 1 6 e1 e2={v4,v5} 1 2 3 4 4 1 7 8 4 5 e2 e3={v4,v7} 1 2 3 4 4 1 4 8 4 7 e3 e4={v1,v4} 1 2 3 1 1 1 1 8 1 4 e4 e5={v3,v5} 1 2 1 1 1 1 1 8 1 3 e5 e6={v4,v6} 1 2 1 1 1 1 1 8 * * * e7={v5,v7} 1 2 1 1 1 1 1 8 * * * e8={v2,v4} 1 1 1 1 1 1 1 8 1 2 e8 e9={v6,v7} 1 1 1 1 1 1 1 8 * * * e10={v5,v8} 1 1 1 1 1 1 1 1 1 8 e10



3.6.- Prufer

Algoritmo de codificación. Una secuencia de Prüfer de longitud n-2 para n≥2 es cualquier secuencia de enteros entre 1 y n, permitiendo repeticiones. El algoritmo de codificación que se presenta aquí, parte de un árbol (grafo) para dar lugar a una secuencia de Prüfer que lo determina unívocamente. Como observación se puede comprobar que el grado de cada uno de los vértices es uno más que el número de veces que su etiqueta aparece en la secuencia de Prüfer. El algoritmo recibe como entrada un árbol A de n vértices y retorna una secuencia S de n-2 vértices.

Implementación:

func codificaciónPrufer (g: Grafo) dev(S: secuencia de vértices)

var

a: entero prin

S := <inicializar a vacía>

// Número de aristas del grafo. a := g.obtenerNúmeroAristas()

mientras a-1 > 0

Encontrar un vértice v de A de grado 1. Sea v-w la arista que incide en v. Introducir w en S. Eliminar la arista v-w del grafo. a := a-1



fmientras fin

La búsqueda del vértice de grado 1 (hoja) se realiza en la matriz de adyacencias del grafo comenzando de izquierda a derecha y de arriba abajo a partir de la fila correspondiente al vértice “v”. Una vez que se encuentra la hoja “w” eliminamos arista formada por los vértices v-w para no volver a tenerla en cuenta. Para determinar si un vértice es hoja sumamos la fila correspondiente a dicho vértice, si el valor de la suma es 1 se trata de una hoja.

Obtener la codificación de Prüfer del siguiente árbol.

Matriz de adyacencias del grafo.

v1 v2 v3 v4 v5 v6 v7 v1 0 1 1 ∞ 1 ∞ ∞ v2 1 0 ∞ 1 ∞ 1 1 v3 1 ∞ 0 ∞ ∞ ∞ ∞ v4 ∞ 1 ∞ 0 ∞ ∞ ∞ v5 1 ∞ ∞ ∞ 0 ∞ ∞ v6 ∞ 1 ∞ ∞ ∞ 0 ∞ v7 ∞ 1 ∞ ∞ ∞ ∞ 0



La primera hoja encontrada es el vértice v3 y v3-v1 es la arista que incide en v3. Eliminamos dicha arista y añadimos v1 a la secuencia.

S = {v1}.

El árbol nos quedaría

v1 v2 v3 v4 v5 v6 v7 v1 0 1 ∞∞∞∞ ∞ 1 ∞ ∞ v2 1 0 ∞ ∞∞∞∞ ∞ 1 1 v3 ∞∞∞∞ ∞ 0 ∞ ∞ ∞ ∞ v4 ∞ ∞∞∞∞ ∞ 0 ∞ ∞ ∞ v5 1 ∞ ∞ ∞ 0 ∞ ∞ v6 ∞ 1 ∞ ∞ ∞ 0 ∞ v7 ∞ 1 ∞ ∞ ∞ ∞ 0




S = {v1, v2}.


v1 v2 v3 v4 v5 v6 v7 v1 0 1 ∞∞∞∞ ∞ 1 ∞ ∞ v2 1 0 ∞ 1 ∞ 1 1 v3 ∞∞∞∞ ∞ 0 ∞ ∞ ∞ ∞ v4 ∞ 1 ∞ 0 ∞ ∞ ∞ v5 1 ∞ ∞ ∞ 0 ∞ ∞ v6 ∞ 1 ∞ ∞ ∞ 0 ∞ v7 ∞ 1 ∞ ∞ ∞ ∞ 0




S = {v1, v2, v1}.


v1 v2 v3 v4 v5 v6 v7 v1 0 1 ∞∞∞∞ ∞ ∞∞∞∞ ∞ ∞ v2 1 0 ∞ ∞∞∞∞ ∞ 1 1 v3 ∞∞∞∞ ∞ 0 ∞ ∞ ∞ ∞ v4 ∞ ∞∞∞∞ ∞ 0 ∞ ∞ ∞ v5 ∞∞∞∞ ∞ ∞ ∞ 0 ∞ ∞ v6 ∞ 1 ∞ ∞ ∞ 0 ∞ v7 ∞ 1 ∞ ∞ ∞ ∞ 0




S = {v1, v2, v1, v2}.


v1 v2 v3 v4 v5 v6 v7 v1 0 1 ∞∞∞∞ ∞ ∞∞∞∞ ∞ ∞ v2 1 0 ∞ ∞∞∞∞ ∞ ∞∞∞∞ 1 v3 ∞∞∞∞ ∞ 0 ∞ ∞ ∞ ∞ v4 ∞ ∞∞∞∞ ∞ 0 ∞ ∞ ∞ v5 ∞∞∞∞ ∞ ∞ ∞ 0 ∞ ∞ v6 ∞ ∞∞∞∞ ∞ ∞ ∞ 0 ∞ v7 ∞ 1 ∞ ∞ ∞ ∞ 0




S = {v1, v2, v1, v2, v2}.


Como el tamaño de la secuencia es n-2 el algoritmo termina, siendo n el número de vértices del árbol el algoritmo termina.

v1 v2 v3 v4 v5 v6 v7 v1 0 1 ∞∞∞∞ ∞ ∞∞∞∞ ∞ ∞ v2 1 0 ∞ ∞∞∞∞ ∞ ∞∞∞∞ ∞∞∞∞ v3 ∞∞∞∞ ∞ 0 ∞ ∞ ∞ ∞ v4 ∞ ∞∞∞∞ ∞ 0 ∞ ∞ ∞ v5 ∞∞∞∞ ∞ ∞ ∞ 0 ∞ ∞ v6 ∞ ∞∞∞∞ ∞ ∞ ∞ 0 ∞ v7 ∞ ∞∞∞∞ ∞ ∞ ∞ ∞ 0



Algoritmo de decodificación. El procedimiento de decodificación siguiente convierte una secuencia de Prüfer en su correspondiente árbol. Este procedimiento de decodificación establece una función fd: Pn-2 � Tn que hace corresponder a un conjunto de secuencias de Prüfer de longitud n-2 un conjunto de árboles de n vértices.

El algoritmo recibe como entrada el número de vértices “n” que debe tener el árbol a generar y una secuencia S de n-2 vértices. Los vértices de la secuencia forman parte del árbol y pueden estar repetidos. A partir de la secuencia proporcionada se genera un árbol.

El algoritmo podemos dividirlo en X pasos.

PASO 1 Crear un grafo G con “n” vértices. (Sin aristas). PASO 2 2.1.- Calcular el conjunto de vértices que no forma parte de la secuencia “NS”. 2.2.- Calcular el conjunto de vértices ocupados “VO”. 2.3.- Obtener la diferencia entre ambos conjuntos NS – VO. PASO 3 Si la secuencia es vacía insertamos una arista formada por los dos vértices incluidos en NS – VO y FIN.

En otro caso insertamos la arista que tiene como origen el primer vértice de la secuencia y como destino el primer vértice de la diferencia NS – VO. Seguidamente eliminar el primer vértice de la secuencia y volver al PASO 2.



Veamos el siguiente ejemplo: Sea n = 7 y la secuencia S = {v1, v2, v4, v6, v2}.

PASO 1 Sea G el grafo:



PASO 2.1 Secuencia S = {v1, v2, v4, v6, v2}.

Vértices no incluidos en la secuencia NS = {v3, v5, v7}. Vértices ocupados VO = {}.

PASO 3.1 Como la secuencia no está vacía formamos una arista que posee como origen el primer vértice de la secuencia y como destino el primer vértice de la diferencia entre NS y VO.

Calculamos la diferencia entre NS y VO.

NS –VO = {v3, v5, v7}.

Insertamos en G la nueva arista v1-v3 y eliminamos v1 de la secuencia.



PASO 2.2 Secuencia S = {v2, v4, v6, v2}.

Vértices no incluidos en la secuencia NS = {v1, v3, v5, v7}. Vértices ocupados VO = {v3}.



NS –VO = {v1, v5, v7}.




PASO 2.3 Secuencia S = {v4, v6, v2}.

Vértices no incluidos en la secuencia NS = {v1, v3, v5, v7}. Vértices ocupados VO = {v1, v3}.



NS –VO = {v5, v7}.




PASO 2.4 Secuencia S = {v6, v2}.

Vértices no incluidos en la secuencia NS = {v1, v3, v4, v5, v7}. Vértices ocupados VO = {v1, v3, v5}.



NS –VO = {v4, v7}.




PASO 2.5 Secuencia S = {v2}.

Vértices no incluidos en la secuencia NS = {v1, v3, v4, v5, v6, v7}. Vértices ocupados VO = {v1, v3, v4, v5}.



NS –VO = {v6, v7}.




PASO 2.6 Secuencia S = {}.

Vértices no incluidos en la secuencia NS = {v1, v2, v3, v4, v5, v6, v7}. Vértices ocupados VO = {v1, v3, v4, v5, v6}.

PASO 3.6 Como la secuencia está vacía solo nos falta insertar una arista. Los vértices que forman parte de la misma se obtienen calculando la diferencia entre NS y VO.


NS –VO = {v2, v7}.

Insertamos en G la nueva arista v2-v7 y FIN.



3.7.- Algoritmo de emparejamientos Un emparejamiento de un grafo simple G, es cualquier subgrafo 1-regular de G, es decir un subgrafo inducido por las aritas dos a dos no incidentes entre sí) Un emparejamiento máximo en un grafo G es cualquier emparejamiento de G de orden máximo, es decir, con el mayor número de vértices posibles. Un emparejamiento maximal de peso óptimo en un grafo G es un emparejamiento de G de orden máximo donde la suma de las ponderaciones de las aristas es máxima o mínima. Un emparejamiento es completo o perfecto si tiene exactamente p/2 aristas, siendo “p” el orden del grafo. Sea M un emparejamiento, se denomina arista emparejada respecto de “M” a cada una de las aristas de G que están en “M”. Si dicha arista no esta en “M” se dice que no esta emparejada. Se llaman vértice emparejado con respecto a “M” a cada uno de los vértices incidentes con alguna arista de “M”, en otro caso se trata de un vértice no emparejado. Una vez que tenemos claros los conceptos anteriores comentaremos los tres algoritmos de emparejamientos.



Algoritmo de emparejamiento maximal simple La implementación del algoritmo trata de buscar un emparejamiento mediante un camino alternado. Se denomina camino alternado de G con respecto a “M” a un camino de G cuyas aristas son alternativamente emparejadas y no emparejada. En cada paso se escoge un vértice no emparejado y busca un camino alternado aumentante mediante BFS. En el camino no pueden a parecer vértices repetidos. Dicho camino deja de expandirse en cuanto encontremos un vértice de G que no haya sido emparejado. Repetimos este proceso para el resto de vértice del grafo. Al final obtendremos un emparejamiento maximal que puede ser completo si todos los vértices del grafo han sido emparejados. Veamos un ejemplo:



Comenzamos por el vértice v1 y construimos el camino alternado formado por las aristas.

M = {v1, v6}. A continuación pasamos al vértice v2. M = {v2, v8}.

Para el vértice v3 = {v3,v7}



Para el vértice v4 = {v4, v9}.

Para el vértice v5 = {{v5, v9}, {v4, v6}, {v1, v7}, {v2, v8}, {v3, v10}}



Finalmente el emparejamiento nos queda.



Algoritmo de Kuhn-Munkres Se trata de un algoritmo de emparejamiento de peso máximo para grafos ponderados, bipartitos y completos.

Los grafos bipartitos completos km,n, son grafos de (n + m) vértices y (m * n) aristas que admiten una partición de sus vértices en sendos conjuntos V y U de “m” y “n” vértices respectivamente, de manera que cada uno de los “m” vértices de V es adyacente a todos y cada uno de los “n” vértices de U. Se denominan bipartitos completos porque no se pueden añadir arista alguna sin que deje de ser bipartito.

Otro concepto importante es el de matriz de pesos del grafo. Se trata de

una matriz que posee tantas filas y columnas como elementos tiene los conjuntos X e Y respectivamente. Cada posición de la matriz almacena la ponderación de una arita cuyo origen pertenece al conjunto X y el destino al conjunto Y.

Ahora explicaremos de forma detallada los cuatro pasos en los que

hemos dividido el algoritmo.

PASO 1

P.1.1.- Identificar los conjuntos V y U de vértices. P.1.2.- Obtener la matriz de pesos del grafo “MatrizPesos”. Sean “i” y “j” los índices para iterar por la matriz de pesos del grafo. P.1.3.- Consideremos las tuplas L(vi) y L(uj) con un tamaño igual al

número de vértices que forman parte del conjunto V y U respectivamente. Inicializamos las tuplas con un etiquetado viable

L(vi) se inicializa con el máximo de la fila correspondiente al

vértice “vi” en MatrizPesos[i, j] con (j <= | V |) (cardinal de V). L(uj) se inicializa a cero para todo uj.



PASO 2 Seguidamente construimos un grafo que verifique la expresión: L(uj) + L(vi) = MatrizPesos[i, j]. var G: Grafo. I, j: enteros

prin G := <inicializamos el grafo>

// Iteramos sobre la matriz de pesos del grafo, si se cumple la expresión // incluimos la arista al grafo “g” con la ponderación correspondiente.

desde i := 0 hasta | V | desde j := 0 hasta | U | si L(uj) + L(vi) = MatrizPesos[i, j] G.añadirArista(u, v, MatrizPesos[i, j]) fsi fdesde fdesde fin PASO 3 P.3.1.- Buscamos un emparejamiento máximo M en el grafo G con el algoritmo de emparejamiento maximal simple. P.3.2.- Si cada vértice de V está emparejado con respecto a M, entonces retorna M y FIN.



PASO 4 A continuación cambiamos las etiquetas de los conjuntos L(vi) y L(uj).

Sea V(T) los vértices del el primer camino alternado enraizado en un vértice no emparejado del conjunto V que no puede ser extendido más en G. P.4.1.- Para ello obtenemos los siguientes conjuntos. I = V ∩ V(T). D = U – V(T). P.4.2.- Calculamos el valor que minimiza la expresión:

L(vi) + L(uj) – MatrizPesos[i, j] con vi y ui pertenecientes a los conjuntos I y D respectivamente.

P.4.3.- Finalmente cambiamos el etiquetado. Para cada vértice vi perteneciente a la intersección restamos el valor del mínimo en L(vi).

Para cada vértice ui no perteneciente a la diferencia sumamos el valor del mínimo en L(ui).

Volvemos al PASO 2.



Consideremos el siguiente grafo al cual aplicaremos el algoritmo de Kuhn-Munkres.

PASO 1 Identificamos los conjuntos U y V. U = {u1, u2, u3, u4, u5}. V = {v1, v2, v3, v4, v5}. Matriz de pesos del grafo, L(vi) y L(uj)

V/U u1 u2 u3 u4 u5 L(vi) v1 5 1 1 3 2 5 v2 0 1 3 3 4 4 v3 2 5 4 3 0 5 v4 2 2 3 4 4 4 v5 6 2 0 0 1 6 L(uj) 0 0 0 0 0



PASO 2.1 Construimos un grafo G2.1 que verifique la expresión

L(uj) + Lv(vi) = MatrizPesos[i, j].



PASO 3.1 Buscamos un emparejamiento máximo en G2.1.

Como no se ha conseguido un emparejamiento máximo para los vértices del conjunto V cambiamos el etiquetado.



PASO 4.1 v5 es el primer vértice no emparejado perteneciente a V.

V(T) es el conjunto de vértices del árbol alternado enraizado en v5 que no puede ser extendido más.

V(T) = {v5, v1, u1}. Calculamos los siguientes conjuntos. V ∩ V(T) = {v5, v1}.

V – V(T) = {u2, u3, u4, u5}.

Minimizamos la expresión L(uj) + L(vi) – MatrizPesos[i, j] para los vértices que forman parte de los conjuntos I y D.

L(v5) + L(u2) - 2 = 4.

L(v5) + L(u3) - 0 = 6.

L(v5) + L(u4) - 0 = 6. L(v5) + L(u5) - 1 = 5. L(v1) + L(u2) - 1 = 4. L(v1) + L(u3) - 1 = 4. L(v1) + L(u4) - 3 = 2. L(v1) + L(u5) - 2 = 3. El mínimo es 2.

Ahora restamos el valor del mínimo a los vértices que forman parte del conjunto I en L(vi) y sumamos el valor del mínimo a los vértices que no forman parte del conjunto D en L(uj). Y volvemos al paso 2

V/U u1 u2 u3 u4 u5 L(vi) v1 5 1 1 3 2 3 v2 0 1 3 3 4 4 v3 2 5 4 3 0 5 v4 2 2 3 4 4 4 v5 6 2 0 0 1 4



L(uj) 2 0 0 0 0



PASO 2.2

Construimos un grafo G2.2 que verifique la expresión


Como no se ha conseguido un emparejamiento máximo para los vértices del conjunto V cambiamos el etiquetado.



PASO 4.2 v5 es el primer vértice no emparejado perteneciente a V.

V(T) es el conjunto de vértices del árbol alternado enraizado en v5 que no puede ser extendido más.

V(T) = {v5, v1, u1, v4, u4, v2, u5}. Calculamos los siguientes conjuntos. V ∩ V(T) = {v5, v1, v4, v2}.

V – V(T) = {u2, u3}.

Minimizamos la expresión L(uj) + L(vi) – MatrizPesos[i, j] para los vértices que forman parte de los conjuntos I y D.

L(v5) + L(u2) - 2 = 4.

L(v5) + L(u3) - 0 = 4. L(v1) + L(u2) - 1 = 2. L(v1) + L(u3) - 1 = 2. L(v4) + L(u2) - 2 = 2. L(v4) + L(u3) - 3 = 1.

L(v2) + L(u2) - 1 = 3. L(v2) + L(u3) - 3 = 1. El mínimo es 1.

Ahora restamos el valor del mínimo a los vértices que forman parte del conjunto I en L(vi) y sumamos el valor del mínimo a los vértices que no forman parte del conjunto D en L(uj). Y volvemos al paso 2

V/U u1 u2 u3 u4 u5 L(vi) v1 5 1 1 3 2 2 v2 0 1 3 3 4 3 v3 2 5 4 3 0 5 v4 2 2 3 4 4 3 v5 6 2 0 0 1 3



L(uj) 3 0 0 1 1



PASO 2.3 Construimos un grafo G2.3 que verifique la expresión





Como todos los vértices del conjunto V están emparejados el algoritmo

termina. El peso del emparejamiento es 21.



Algoritmo de Kuhn-Munkres con preprocesamiento (pes o mínimo). El algoritmo de Kuhn-Munkres se utiliza para obtener un emparejamiento de peso máximo en un grafo bipartito, ponderado y completo. También podemos usarlo para obtener el emparejamiento de peso mínimo aunque previamente es necesario realizar un preprocesamiento a las ponderaciones de las aristas del grafo. El preprocesamiento cambia las ponderaciones de las aristas manteniendo la relación de orden, pero las aristas que antes eran mínimas ahora son máximas por lo que bastara aplicar el algoritmo de Kuhn-Munkres y deshacer los cambios en las ponderaciones de las aristas para obtener el emparejamiento de peso mínimo. PREPROCESAMIENTO.

1.- Calcular la ponderación máxima de todas las aristas del grafo.

2.- Para cada arista cambiamos su peso por: | PesoArista – PonderaciónMaxima |.

3.- Finalmente aplicamos el algoritmo de Kuhn-Munkres y obtenemos el

emparejamiento de peso mínimo.



Encontrar el emparejamiento de peso mínimo en el siguiente grafo.

Realizar el preprocesamiento. La arista v5u1 es la que posee mayor ponderación en el grafo. Su peso es 6.



Ahora cambiamos las ponderaciones de las aristas.

A continuación aplicaremos el algoritmo de Kuhn-Munkres obteniendo un emparejamiento de peso máximo que nos dará las aristas de peso mínimo cuando deshagamos los cambios realizados en el preprocesamiento. Aristas del emparejamiento de peso máximo: Arista (v1, u3, 5).

Arista (v2, u1, 6). Arista (v3, u5, 6). Arista (v4, u2, 4). Arista (v5, u4, 6). El peso del emparejamiento es 27.



Deshacemos los cambios en las ponderaciones obteniendo el peso original de las aristas.

Aristas del emparejamiento de peso mínimo: Arista (v1, u3, 1).

Arista (v2, u1, 0). Arista (v3, u5, 0). Arista (v4, u2, 2). Arista (v5, u4, 0).

El peso del emparejamiento es 3.



Algoritmo de emparejamiento maximal de peso óptimo.

El problema de búsquedas de emparejamientos máximo de peso óptimo (máximo o mínimo) es un problema NP-completo. Aunque existen métodos aproximados se ha optado por un algoritmo de búsqueda exhaustiva, implementado mediante la técnica de backtracing. El esquema que implementa el backtracing:

proc btÓptimo(x: Etapa)

var xsig: Etapa cand: Candidatos prin si (esSolución(x)) si (esMejor()) actualizaSolución() fsi fsi xsig := nuevaEtapa(x) cand := calculaCandidatos(x) mientras (quedanCandidatos(cand)) seleccionaCandidato(cand, xsig); si (esPrometedor(cand, xsig)) anotaSolución(cand, xsig); btOptimo(xsig); cancelaAnotación(cand, xsig); fsi fmientras fin

A continuación comentaremos algunas características del problema que se pretende resolver y detallaremos cada uno de los métodos y clases que hacen posible la búsqueda del emparejamiento de peso óptimo.



Comenzaremos por la Clase “Solución” Clase Solución // Atributos

emparejamientos: Array[][] de enteros. /// Almacena el peso del emparejamiento. pesoEmparejamiento: real /// Número de vértices emparejados. numVérticesEmparejados: entero fclase La matriz emparejamientos se inicializa con 0 excepto la diagonal principal y posiciones en las que o existe aritas que se inicializa con infinito o menos infinito dependiendo si el emparejamiento buscado es de peso mínimo o máximo respectivamente.

Además a lo largo de la ejecución almacena las parejas encontradas a las cuales les asignan un número que hace referencia al orden en el que se han encontrado.

La profundidad al que se encuentra la solución que viene determinada

por el número máximo de vértices que pueden ser emparejados, pero determinar esto en un grafo no es trivial, por ello en cada etapa marcamos la fila y columna de los vértices emparejados con el valor de la etapa para que no vuelvan a ser considerados y saber cuando terminamos el proceso de búsqueda de parejas. Dicho proceso finaliza cuando la matriz “emparejamientos” no contiene ningún 0. Esto se comprueba en el método “esSolución”.

Además si emparejamiento buscado es de peso mínimo puede aplicarse

una poda al árbol de expansión si hemos encontrado previamente una posible solución. La poda de una rama se produce si el peso del emparejamiento encontrado es menor o igual que el peso del emparejamiento parcialmente construido. En dicho caso la rama no es examinada.

Si por el contrario el emparejamiento buscado es de peso máximo será

necesario expandir el árbol completo, pues no es posible aplicar ninguna poda. Por otra parte como se trata de un problema de optimización una

solución se considera mejor otra, si existe un mayor número de vértices emparejados o si el número de vértices emparejados es igual en ambas soluciones se comprueba el peso y en función del tipo de emparejamiento se escoge la solución de mayor o menor peso. Esta comprobación se realiza en el método “esMejor”. Cada vez que encontremos una solución mejor



actualizaremos la solución obtenida hasta el momento, lo cual se realiza en el método “actualizaSolución”.

Clase “Candidatos” Clase Candidatos // Atributos

vérticesSinPareja: Array[] de enteros; // Índice para iterar sobre el array de candidatos. i: entero

fila: entero

fclase

En el array “vérticesSinPareja” almacenamos las columnas de los vértices que aún no tienen parejas.

El atributo “fila” indica la fila en la matriz de adyacencias donde se encontraron los vértices candidatos.

Los candidatos de una etapa son las columnas de los vértices aún

no emparejados escogidos de la primera fila de la matriz “emparejamientos” en la que aparece un 0.

Clase “Etapa” // Atributos // Profundidad del árbol de expansión k: entero // Candidato actualmente procesado. i: entero

fclase El valor inicial de la etapa y candidato actualmente procesado

comienzan en 0.



Ahora detallaremos los atributos de la clase que da cuerpo a cada uno de los métodos del esquema.

Clase “EmparejamientoMaximalPesoOptimoBacktracking” // Atributos // Matriz de adyacencias del grafo. adyacencias: Array[][] de real tipoEmparejamineto: Lógico // Fila del vértice sin pareja. fila: entero // Columna del vértice sin pareja columna: entero // Almacena las soluciones parciales encontradas sol: Solución // Almacena la solución óptima encontrada. solÓptima: Solución fclase

El atributo “tipoEmparejamiento” informa del tipo de emparejamiento

buscado por el usuario. Si su valor es “cierto” buscamos un emparejamiento de peso máximo, en otro caso de peso mínimo.

Por último comentar algunos detalles del resto de métodos del esquema. En el método “nuevaEtapa” tan solo incrementamos el valor de la etapa

actual. En “quedanCandidatos” se comprueba si el atributo “i” utilizado para

iterar sobre el array “verticesSinpareja” que almacena los candidatos ha llegado al final del array.

En “selecionaCandidato” actualizamos los atributos “fila” y “columna” del

vértice no emparejado. Además se incrementa el índice del candidato usado para iterar sobre el array que almacena los vértices sin pareja y asignamos dicho valor al atributo que indica en la etapa el candidato que se esta procesando actualmente.

En “anotaSolución” se marca la fila y columna de los vértices

emparejados con el valor “-k” de la etapa. Por otra parte posición de la matriz 2



“emparejamientos” correspondiente al emparejamiento se marca con el valor “k” de la etapa indicando el orden en el que se ha encontrado la pareja. También incrementamos en dos el número de vértices emparejados y actualizamos el peso del emparejamiento parcialmente construido con el peso de la nueva arista considerada. Finalmente en “cancelaAnotación” decrementamos el valor “k” y restauramos el valor del candidato actualmente de la etapa. Además se restaura el valor de la fila y columna, se desmarcan la fila y columnas de los últimos vértices emparejados. También restauramos el valor del peso del emparejamiento y vértice emparejados con el valor que tenían antes de considerar la nueva pareja. En definitiva las típicas operaciones que deben aparecer en toda vuelta atrás. A continuación veremos un par de ejemplos donde encontrar el emparejamiento óptimo es trivial, pero son útiles para visualizar el árbol de expansión generado. Además a la hora de mostrar los candidatos pondremos los propios vértices en vez de la posición que estos ocupan en la matriz de adyacencias.

Emparejamiento máximo de peso máximo.



Árbol de expansión:

Etapa k = 0 {v2, v3, v4}

peso = 0

k = 1 {v4} {v4} {v3} peso = 2 peso = 10 peso = 4

k = 2 peso = 5 peso = 14 peso = 9 El emparejamiento óptimo de peso máximo es 14. En este caso ha sido necesario expandir todo el árbol para obtener el emparejamiento de peso máximo con el mayor número de vértices.

Aristas del emparejamiento: Arista (v1, v3, 10) Arista (v2, v4, 4)

v1 v2 v3 v4

v1 ∞ 0 0 0 v2 0 ∞ 0 0 v3 0 0 ∞ 0 v4 0 0 0 ∞

v1 v2 v3 v4

v1 ∞ -1 1 -1 v2 -1 ∞ -1 0 v3 -1 -1 ∞ -1 v4 -1 0 -1 ∞

v1 v2 v3 v4

v1 ∞ -1 -1 1 v2 -1 ∞ 0 -1 v3 -1 0 ∞ -1 v4 -1 -1 -1 ∞

v1 v2 v3 v4

v1 ∞ 1 -1 -1 v2 -1 ∞ -1 -1 v3 -1 -1 ∞ 0 v4 -1 -1 0 ∞

v1 v2 v3 v4

v1 ∞ 1 -1 -1 v2 -1 ∞ -1 -1 v3 -1 -1 ∞ 2 v4 -1 -1 -2 ∞

v1 v2 v3 v4

v1 ∞ -1 1 -1 v2 -1 ∞ -1 2 v3 -1 -1 ∞ -1 v4 -1 -2 -1 ∞

v1 v2 v3 v4

v1 ∞ -1 -1 1 v2 -1 ∞ 2 -1 v3 -1 -2 ∞ -1 v4 -1 -1 -1 ∞



Emparejamiento máximo de peso mínimo.

Árbol de expansión:

Etapa k = 0 {v2, v3, v4}

peso = 0

k = 1 {v4} {v4} {v3} peso = 2 peso = 10 peso = 4

k = 2 peso = 5 peso = 9 El emparejamiento óptimo de peso mínimo es 5. En este caso no ha sido necesario expandir todo el árbol pues ya teníamos una solución cuyo peso es 5 y por la segunda rama el emparejamiento parcialmente construido tiene peso 10 por lo que no es posible mejorar el emparejamiento encontrado inicialmente.

Aristas del emparejamiento: Arista (v1, v2, 2)

v1 v2 v3 v4

v1 ∞ 0 0 0 v2 0 ∞ 0 0 v3 0 0 ∞ 0 v4 0 0 0 ∞

v1 v2 v3 v4

v1 ∞ -1 1 -1 v2 -1 ∞ -1 0 v3 -1 -1 ∞ -1 v4 -1 0 -1 ∞

v1 v2 v3 v4

v1 ∞ -1 -1 1 v2 -1 ∞ 0 -1 v3 -1 0 ∞ -1 v4 -1 -1 -1 ∞

v1 v2 v3 v4

v1 ∞ 1 -1 -1 v2 -1 ∞ -1 -1 v3 -1 -1 ∞ 0 v4 -1 -1 0 ∞

v1 v2 v3 v4

v1 ∞ 1 -1 -1 v2 -1 ∞ -1 -1 v3 -1 -1 ∞ 2 v4 -1 -1 -2 ∞

v1 v2 v3 v4

v1 ∞ -1 -1 1 v2 -1 ∞ 2 -1 v3 -1 -2 ∞ -1 v4 -1 -1 -1 ∞



Arista (v3, v4, 3)



Seguidamente un par de ejemplos para grafos con un mayor número de vértices y aritas.

Ejemplo 1.

Aristas del emparejamiento de peso máximo:

Arista (v1, u4, 3).





Aristas del emparejamiento óptimo de peso mínimo:

Arista (v1, u3, 1).



Ejemplo 2.

Aristas del emparejamiento óptimo de peso máximo:

Arista (v1, v5, 4).

Arista (v2, v6, 1).




Aristas del emparejamiento óptimo de peso mínimo:

Arista (v1, v4, 2).

Arista (v2, v5, -1).




3.8.- Euler

¿ Es euleriano ?. Un grafo simple conexo es euleriano si y solo si todos los vértices tienen valencia par.

Si el grafo es dirigido y el grado de entrada y salida de cada vértice de es igual entonces es euleriano. La implementación del algoritmo hace distinción entre grafos simples y dirigidos.

Si se trata de un grafo simple se suma las filas de la matriz de adyacencias para cada vértice y si todos tienen valencia par entonces el grafo es euleriano. En caso contrario el grafo no es euleriano.

Si el grafo es dirigido se calcula el grado de entrada sumado la fila y el

grado de salida sumando la columna correspondiente al vértice en la matriz de adyacencias del grafo. Si el grado de entrada y salida de todos los vértices es igual entonces el grafo es euleriano.

A continuación veremos dos ejemplos para cada tipo de grafo.

Grafos simples. Ejemplo 1



Vértices grado

v1 4 v2 4 v3 4 v4 2 v5 2 v6 2 v7 2

Como todos los vértices son de valencia par el grafo es euleriano.

Ejemplo 2.

Vértices grado v1 3 v2 4 v3 4 v4 2 v5 2 v6 1



Como el grafo posee dos vértices impares no es euleriano.



A continuación expondremos los ejemplos para los grafos dirigidos. Grafos dirigidos. Ejemplo 1

Vértices Entrada Salida

v1 2 2 v2 2 2 v3 2 2 v4 2 2 v5 3 3 v6 2 2 v7 1 1

Como todos los vértices tienen el grado de salida igual al grado de entrada el grafo es euleriano.



Ejemplo 2

Vértices Entrada Salida v1 2 2 v2 2 1 v3 2 1 v4 2 2 v5 1 1

Como existen vértices cuyo grado de salida es distinto al grado de entrada el grafo no es euleriano.



3.9.- Algoritmos de búsqueda de trayectorias euleri anas. Antes de comenzar a exponer los diversos algoritmos que tratan de

buscar trayectorias eulerianas en los grafos debemos tener claro una serie de conceptos.

Comenzaremos definiendo el concepto de trayectoria como una sucesión de vértices con la propiedad de que cada vértice es adyacente al siguiente y tal que en la correspondiente sucesión de aristas todas son distintas. Además esta permitido que un vértice aparezca más de una vez.

Si dicha trayectoria comienza y termina en el mismo vértice tenemos un circuito.

Una vez definido el concepto general de trayectoria nos centraremos en

las trayectorias eulerianas la cual recorre todas las aristas de un grafo conexo. Análogamente si termina y comienza en el mismo vértice se trata de un circuito euleriano. A continuación comentaremos tres algoritmos que se encargan de buscar trayectorias eulerianas.

Para que en un grafo conexo exista una trayectoria euleriana es necesario que el grafo no posea más de dos vértices de valencia impar, por lo que si un grafo conexo que tiene exactamente dos vértices de valencia impar tiene al menos una trayectoria euleriana. Cualquier trayectoria de Euler debe comenzar en uno de los vértices de grado impar y finalizar en el otro.

Sin embargo para que exista al menos un circuito euleriano todos los

vértices deben tener grado par y el circuito puede construirse partiendo desde cualquier vértice.

Algoritmo de Fleury El algoritmo de Fleury trata de buscar una trayectoria euleriana en un grafo conexo y en el que no existen más de dos vértices de grado impar. La implementación del algoritmo se ha realizado mediante técnicas de programación dinámica combinada con voraz. La heurística seguida para encontrar la trayectoria euleriana es la siguiente. Se comprueba que previamente que el grafo satisface las condiciones para que exista dicha trayectoria.



Seguidamente no situamos en unos de los vértices impares si existen o en caso contrario uno cualquiera de grado par. A continuación de todos los vértices adyacentes respecto al que estamos situados escogemos el primero según orden existente en la matriz de adyacencias y al ser posible que no sea una arista puente salvo que no exista ninguna otra alternativa. Una vez seleccionada la arista, esta no vuelve a tenerse en cuenta por lo que es como si la hubiéramos eliminado del grafo. Repetimos este proceso hasta recorrer todas las aristas del grafo, pudiendo repetir vértices. Si el grafo es no dirigido la trayectoria se encuentra sin problemas, sin embargo en grafos dirigidos puede no encontrarse dicha trayectoria si el grafo posee más de un vértice impar. En este caso lo único que podemos hacer es relanzar la búsqueda partiendo del otro vértice impar. Veamos algunos ejemplos: Encontrar una trayectoria euleriana en el siguiente grafo no dirigido.

Vértices Grado

v1 2 v2 2 v3 3 v4 3 v5 2 v6 2



v7 2 Como posee dos vértices impares y el grafo es no dirigido posee una trayectoria euleriana abierta. Los vértices impares son v3 y v4. Comenzamos por el primer vértice impar v3. v3 � v1

v3 � v1 � v2

La última arista tomada es puente, pues no existe ninguna alternativa.



v3 � v1 � v2 � v3


v3 � v1 � v2 � v3 � v4




v3 � v1 � v2 � v3 � v4 � v5

v3 � v1 � v2 � v3 � v4 � v5 � v6




v3 � v1 � v2 � v3 � v4 � v5 � v6 � v7


v3 � v1 � v2 � v3 � v4 � v5 � v6 � v7 � v4.




Encontrar una trayectoria euleriana en el siguiente grafo dirigido.

.

Vértices Entrada Salida v1 2 2 v2 1 1 v3 1 1 v4 2 2 v5 2 1 v6 0 1

El grafo no es euleriano pues existen vértices con grado de entrada y salida distintos, concretamente v5 y v6. En este caso podemos intentar encontrar dicha trayectoria partiendo de algunos de los vértices anteriores.



Los vértices con grado de entrada distinto del grado de salida son v5 y v6. Comenzamos por el primer vértice impar v5. v5 � v4

v5 � v4 � v1



v5 � v4 � v1 � v2

v5 � v4 � v1 � v2 � v3



v5 � v4 � v1 � v2 � v3 � v4 La última arista tomada es puente, pues no existe ninguna alternativa.



v5 � v4 � v1 � v2 � v3 � v4 � v2




v5 � v4 � v1 � v2 � v3 � v4 � v2 � v5 . La última arista tomada es puente, pues no existe ninguna alternativa.

En el siguiente paso nos damos cuenta que el vértice v5 no posee ningún

vértice adyacente por lo que no se ha encontrado la trayectoria buscada pues no se han recorrido todas las aristas. En este caso lo único que podemos hacer comenzar a construir la trayectoria desde el otro vértice impar.



Comenzamos por el primer vértice impar v6. v6 � v1

v6 � v1 � v2



v6 � v1 � v2 � v3

v6 � v1 � v2 � v3 � v4 La última arista tomada es puente, pues no existe ninguna alternativa.



v6 � v1 � v2 � v3 � v4 � v1

v6 � v1 � v2 � v3 � v4 � v1 � v5




v6 � v1 � v2 � v3 � v4 � v1 � v5 � v4

v6 � v1 � v2 � v3 � v4 � v1 � v5 � v4 � v2



v6 � v1 � v2 � v3 � v4 � v1 � v5 � v4 � v2 � v5.

En este caso partiendo desde el otro vértice impar es posible encontrar la trayectoria euleriana abierta pero puede ocurrir que dicha trayectoria no exista.



Veamos un ejemplo de grafo dirigido el que solo existen dos vértices de grado impar pero no existe una trayectoria euleriana.

Vértices Entrada Salida v1 0 2 v2 3 1 v3 1 1 v4 1 1 v5 1 1

En este caso no existe trayectoria euleriana pues es imposible visitar las aristas v1v2 y v1v5 si partimos del vértice v2. Si por el contrario partiéramos del vértice v1 no podríamos recorrer todas las que salen de dicho vértice pues el grado de entrada es cero. Como conclusión podemos decir que en grafos dirigidos existe una trayectoria euleriana si el grado de entrada y salida de cada vértice son iguales, en otro caso la trayectoria puede no existir. Seguidamente expondremos dos algoritmos encargados de buscar trayectorias eulerianas cerradas en cualquier tipo de grafos, pero con estrategias claramente distintas. Por ello en ambos se exige que los grafos cumplan ciertas restricciones. Si se trata de un grafo no dirigido todos los vértices deben ser de grado par y si es no dirigido los grados de entrada y salida de cada vértice deben ser idénticos para garantizar la existencia del ciclo euleriano. Teniendo claro lo anteriormente comentado pasaremos a explicar detalladamente las estrategias de ambos algoritmos.



Algoritmo de Tucker. Tras comprobar las condiciones que permiten la ejecución del algoritmo se siguen dos estrategias según el tipo de grafo. Si el grafo es no dirigido para cada vértice cuyo grado es mayor que dos se duplica hasta conseguir que reducir su grado a dos, en caso de ser un grafo dirigido duplicamos aquellos vértices cuyo grado de entrada o salida sean distintos de uno hasta reducirlos a ese valor. Al final del proceso tenemos una lista de vértices duplicados y los respectivos vértices con los que se identifica. Además cabe mencionar que el número de aristas del grafo original se conserva, lo único que pueden aumentar es el número de vértices. Una vez concluido el proceso de duplicación el grafo queda dividido en un conjunto de componentes conexas a partir de las cuales iremos reconstruyendo los ciclos a la misma vez que identificamos los vértices duplicados con el vértice resultado de la duplicación para dejar el grafo como estaba originalmente. Para terminar de comprender el algoritmo veremos un par de ejemplos.



Aplicaremos el algoritmo de Tucker al siguiente grafo no dirigido.

Vértices Grado

v1 4 v2 4 v3 2 v4 4 v5 2 v6 2 v7 2 v8 2 v9 2 v10 2 v11 2 v12 2

Los vértices cuyo grado es mayor que dos son v1, v2 y v4. Estos vértices serán duplicados hasta conseguir reducir el grado a dos para cada uno de ellos.



Duplicamos el vértice v1 dando el vértice v13.




Finalmente para que todos los vértices posean grado 2 duplicamos el vértice v4 dando el vértice v15.

Tras el proceso de duplicación el grafo queda dividido en un conjunto de componentes conexas concretamente cuatro y tenemos una lista de vértices duplicados y el correspondiente vértice con el que se identifica.

Vértice duplicado Vértice con el que se identifica

v1 v13

v2 v14

v4 v15

Ahora reconstruiremos el grafo y la trayectoria euleriana cerrada identificando los vértices duplicados. Si el grafo ha sido dividido en varias componentes conexas tomamos un vértice de la lista de duplicados tal que el vértice duplicado y el vértice con el que se identifica estén en componentes conexas distintas comenzando por las primeras posiciones de la tabla anterior. Además en ese caso en la primera iteración reconstruiremos dos ciclos y los reensamblaremos por el final.



Si el grafo solo posee una componente conexa reconstruir la trayectoria es trivial, viene determinada por el propio grafo, bastará identificar los vértices duplicados y al mismo tiempo actualizarlos en la trayectoria. En este caso escogemos el vértice duplicado v4 y el vértice resultado de la duplicación v15. Reconstruimos los dos ciclos identificando el vértice. Primer ciclo {v4-v7-v8-v9-v4}. Segundo ciclo {v4-v3-v1-v2-v4}. Identificamos el vértice y reensamblamos los ciclos.

Ciclo reensamblado {v4-v7-v8-v9-v4-v3-v1-v2-v4}. Como el grafo aún no es conexo escogemos de la lista de vértices duplicados uno que no haya sido considerado y cuyo vértice duplicado pertenezca a la trayectoria parcialmente construida para que sea más fácil la concatenación del nuevo ciclo. Por lo que escogemos el vértice duplicado v2 y el vértice resultado de la duplicación v14



Reconstruimos el ciclo identificando el vértice {v2-v5-v6-v2}



Identificamos el vértice.

Reensamblamos el nuevo ciclo en la trayectoria parcialmente construida por el final. {v4-v7-v8-v9-v4-v3-v1-v2-v5-v6-v2-v4}. Finalmente escogemos el vértice duplicado v1 y el vértice resultado de la duplicación v13. Construimos el ciclo identificando el vértice {v1-v10-v11-v12-v1} Por último identificamos los vértices y reensamblamos el ciclo por el final en la trayectoria euleriana parcialmente construida obteniendo la trayectoria cerrada completa.



Trayectoria euleriana cerrada {v4-v7-v8-v9-v4-v3-v1-v10-v11-v12-v1-v2-v4}.



Veamos otro ejemplo

Vértices Grado v1 4 v2 2 v3 2 v4 4 v5 2 v6 2

Los vértices cuyo grado es mayor que dos son v1 y v4. Estos vértices serán duplicados hasta conseguir reducir el grado a dos para cada uno de ellos.




Para terminar de conseguir que todos los vértices tengan grado 2 duplicaremos el vértice v4 dando el vértice v8.

Vértice duplicado Vértice con el que se identifica

v1 v7

v4 v8



Como el grafo ha sido dividido 2 componentes conexas tomamos un vértice de la lista de duplicados tal que el vértice duplicado y el vértice con el que se identifica estén en componentes conexas distintas comenzando por las primeras posiciones la tabla anterior. Además en ese caso en la primera iteración reconstruiremos dos ciclos y los reensamblaremos por el final. En este caso escogemos el vértice duplicado v4 y el vértice resultado de la duplicación v8.

Reconstruimos los dos ciclos identificando el vértice. Primer ciclo {v4-v1-v2-v3-v4}. Segundo ciclo {v4-v5-v7-v6-v4}. Identificamos el vértice y reensamblamos los ciclos.

Ciclo reensamblado {v4-v1-v2-v3-v4-v5-v7-v6-v4}. El grafo ya es conexo por lo que solo nos queda identificar el resto de vértices si existen para obtener la trayectoria euleriana cerrada.



Identificamos el último vértice duplicado que nos queda v1 con v7.

Identificamos el vértice en la trayectoria {v4-v1-v2-v3-v4-v5-v1-v6-v4}.



Finalmente detallaremos un ejemplo para un grafo dirigido.

Vértices Entrada Salida v1 3 3 v2 1 1 v3 1 1 v4 1 1 v5 2 2 v6 1 1 v7 1 1 v8 1 1 v9 1 1

Como se trata de un grafo dirigido debemos conseguir que todos los vértices tengan grado de entrada y salida igual a 1, por lo que duplicaremos los vértices v1 y v5.




Una vez que los grados de entrada y salida de todos los vértices son iguales a 1 comenzamos el proceso reconstrucción de la trayectoria euleriana cerrada e identificación de vértices para dejar el grafo como estaba originalmente.

Vértice duplicado Vértice con el que se identifica v1 v10

v1 v11

v5 v12

Como es la primera iteración reconstruiremos dos ciclos. Buscamos un vértice duplicado y vértice con el que se identifica de tal forma que pertenezcan a componentes conexas distintas. En este caso escogemos comenzando por las primeras posiciones de la tabla el vértice duplicado v1 y el vértice resultado de la duplicación v1. Reconstruimos los dos ciclos identificando el vértice. Primer ciclo {v1-v2-v3-v1}. Segundo ciclo {v1-v9-v1}.



Identificamos el vértice y reensamblamos los ciclos.

Ciclo reensamblado {v1-v2-v3-v1-v9-v1}. Como el grafo aún no es conexo escogemos de la lista de vértices duplicados uno que no haya sido considerado y cuyo vértice duplicado pertenezca a la trayectoria parcialmente construida para que sea más fácil la concatenación del nuevo ciclo. Por lo que escogemos el vértice duplicado v1 y el vértice resultado de la duplicación v11. Construimos el ciclo identificando el vértice {v1-v4-v12-v6-v7-v5-v8-v1}. Identificamos el vértice.



Reensamblamos los ciclos {v1-v2-v3-v1-v9-v1-v4-v12-v6-v7-v5-v8-v1}. Como el grafo ya es conexo tan solo nos falta identificar el resto de vértices duplicados. Finalmente identificamos el vértice duplicado v5 y el vértice resultado de la duplicación v12 y obtenemos la trayectoria euleriana cerrada.

Identificamos el vértice en la trayectoria {v1-v2-v3-v1-v9-v1-v4-v5-v6-v7-v5-v8-v1}.



Algoritmo de Hierholzer. Tras comprobar las condiciones que permiten la ejecución del algoritmo, seguimos la siguiente estrategia independientemente del tipo de grafo. Nos situamos en un vértice cualquiera y construimos un ciclo. Si todas las aristas del grafo han sido visitadas tenemos la trayectoria euleriana en otro caso partimos de un vértice que forme parte de la trayectoria euleriana parcialmente construida y que aún le queden adyacentes por considerar. Partiendo de este vértice construimos otro ciclo y lo reensamblamos con el obtenido anteriormente comenzando por el principio de la lista que almacena la trayectoria euleriana. Para construir el ciclo basta coger en cada iteración un adyacente del vértice en el cual nos encontramos. El vértice actual en cada iteración es el adyacente obtenido. Dicho proceso se repetirá hasta llegar al vértice de partida. Este proceso se realiza hasta que todas las aritas del grafo hayan sido visitadas. Veamos algunos ejemplos para terminar de comprender el algoritmo. Aplicar el algoritmo de Hierholzer al siguiente grafo no dirigido.



El primer ciclo podemos construirlo partiendo de cualquier vértice del grafo, por ejemplo v5. Obtenemos el ciclo {v5-v2-v1-v3-v4-v2-v6-v5}. A continuación obtenemos otro ciclo partiendo de un vértice perteneciente al ciclo anteriormente encontrado para que sea más fácil la concatenación de ambos. Partimos del vértice v1 y obtenemos el ciclo {v1-v10-v11-v12-v1}. Ahora reensamblamos los ciclos: {v5-v2-v1-v10-v11-v12-v1-v3-v4-v2-v6-v5}. Como aún no se han recorrido todas las aristas del grafo obtendremos otro ciclo partiendo de un vértice contenido en los ciclos concatenados con anterioridad. Por lo que podemos partir del vértice v4, obteniendo el ciclo {v4-v7-v8-v9-v4}. Ahora concatenamos los ciclos y obtenemos la trayectoria euleriana cerrada. {v5-v2-v1-v10-v11-v12-v1-v3-v4-v7-v8-v9-v4-v2-v6-v5}.



Veamos un ejemplo para un grafo dirigido.

El primer ciclo podemos construirlo partiendo de cualquier vértice del grafo, por ejemplo v3. Obtenemos el ciclo {v3-v1-v2-v3}. A continuación obtenemos otro ciclo partiendo de un vértice perteneciente al ciclo anteriormente encontrado para que sea más fácil la concatenación de ambos. Partimos del vértice v1 y obtenemos el ciclo {v1-v4-v5-v6-v7-v5-v8-v1}. Ahora reensamblamos los ciclos: {v3-v1-v4-v5-v6-v7-v5-v8-v1-v2-v3}. Como aún no se han recorrido todas las aristas del grafo obtendremos otro ciclo partiendo de un vértice contenido en los ciclos concatenados con anterioridad. Por lo que podemos partir del vértice v1, obteniendo el ciclo {v1-v9-v1}. Ahora concatenamos los ciclos y obtenemos la trayectoria euleriana cerrada. {v3-v1-v9-v1-v4-v5-v6-v7-v5-v8-v1-v2-v3}.



Problema del cartero Este problema modeliza numerosas situaciones de la vida real como es la recogida de basura de una ciudad, repartos de mercancías, en definitiva situaciones donde se sale de punto y es necesario llegar o pasar por un conjunto de zonas y regresar a dicho punto minimizando el coste del trayecto.

Tradicionalmente se conoce como problema del cartero debido al trabajo que esta persona realizan, puesto que un cartero debe salir de la oficina, repartir todas las cartas a todas las casas y volver a la oficina minimizando el coste del recorrido. El objetivo encontrar un recorrido cerrado de coste óptimo que pase por todas las aristas del grafo, pudiendo repetir las que sean necesarias. El algoritmo podemos dividirlo en cinco pasos bien diferenciados que detallaremos a continuación. PASO 1 Obtener los vértices impares del grafo. PASO 2 Formar el grafo completo kn con los vértices impares. La ponderación de las aristas del grafo anterior viene determinada por la distancia del camino mínimo en el grafo original entre cada par de vértice del grafo completo formado por los vértices impares. Para obtener el peso de las aristas se ha empleado el algoritmo de Dijkstra. PASO 3 Buscar un emparejamiento perfecto de peso mínimo en el grafo completo formado por los vértices impares. PASO 4 Duplicar las aristas del camino mínimo anteriormente calculado según el emparejamiento obtenido, es decir, si se obtuvo la siguiente pareja (v1, v2) se duplican las aristas del camino mínimo que une v1 con v2 en el grafo original.



PASO 5 Encontrar el recorrido cerrado de menor coste. Para ello se ha utilizado el algoritmo de Fleury. Seguidamente veremos un ejemplo en el que detallaremos cada uno de los pasos anteriormente comentados. Sea G el siguiente grafo.

Vértices Grado

v1 4 v2 4 v3 3 v4 4 v5 3 v6 1 v7 1

PASO 1 Los vértices impares son v3, v5, v6 y v7.



PASO 2 Construimos el grafo completo formado por los vértices v3, v5, v6 y v7.

Ahora calcularemos las ponderaciones de las aristas. Para ello obtendremos la distancia del camino mínimo en G entre cada par de vértices del grafo completo formado por los vértices impares. dG (v3, v5) = 2. dG (v3, v6) = 7. dG (v3, v7) = 2. dG (v5, v7) = 4. dG (v6, v5) = 6. dG (v6, v7) = 9.



Por lo que las ponderaciones de las aritas del grafo formado por los vértices impares nos queda.

PASO 3 Buscamos un emparejamiento perfecto de peso mínimo en el grafo formado por los vértices impares. Para ello se ha utilizado el algoritmo de emparejamiento de peso óptimo explicado en la sección dedicada a los emparejamientos. El emparejamiento obtenido esta formado por las aristas v3v7 y v5v6.

PASO 4 Ahora debemos duplicar en G las aristas del camino mínimo existente entre los vértices emparejados para lo cual volvemos a aplicar Dijkstra.



Obtenemos las aristas que forman parte del camino mínimo entre v3 y v7.

Obtenemos las aristas que forman parte del camino mínimo entre v5 y v6.



Las aristas coloreadas de azul se duplican en G. PASO 5 Finalmente encontramos el recorrido cerrado de coste mínimo aplicando el algoritmo de Fleury teniendo en cuenta las aristas duplicadas, es decir, podemos pasar por ellas dos veces. El recorrido es v6-v1-v2-v1-v4-v2-v4-v3-v7-v3-v4-v5-v2-v5-v1-v6. Orden en el que se recorren las aristas: Arista (v6, v1, 2). Arista (v1, v2, 3). Arista (v2, v1, 3) Arista (v1, v4, 4). Arista (v4, v2, 6). Arista (v2, v4, 6). Arista (v4, v3, 1).



Arista (v3, v7, 2). Arista (v7, v3, 2). Arista (v3, v4, 1). Arista (v4, v5, 1). Arista (v5, v2, 1). Arista (v2, v5, 1). Arista (v5, v1, 5). Arista (v1, v6, 2). El peso total del recorrido es 36 unidades.



3.10.- Algoritmos de vértice coloración Se denomina vértice coloración de un grafo G(V,A) a una asignación c: V�/N que asocie a cada vértice vi un color ci ∈ /N de tal forma que ha vértices adyacentes les correspondan colores distintos. Dado un grafo G(V,A), siempre existe un valor umbral “k” para el cual G admite una vértice coloración con una paleta de “k” colores, pero no una de (k-1)-coloración. Es decir “k” es el menor número de colores con los se puede obtener una vértice coloración de G. Este valor se conoce como número cromático G. Determinar el número cromático de un grafo es un problema complejo, no se conoce ningún algoritmo capaz de dar una solución óptima en tiempo polinómico, por lo que será necesario utilizar técnicas algorítmicas capaces de aproximar una solución del problema en intervalos de tiempos polinomiales. Seguidamente expondremos cuatro algoritmos de coloración de vértices de carácter voraz y aplicaremos dichos algoritmos al siguiente grafo que tomaremos como ejemplo.



Algoritmo de coloración Secuencial o Voraz. Este algoritmo sigue una estrategia voraz, es decir comienza la coloración de los vértices según orden de los éstos en la matriz de adyacencias del grafo, por lo que la entrada del algoritmo es una ordenación de los vértices del grafo. La coloración se realiza siguiendo los siguientes pasos. 1.- Asignar el color 1 al primer vértice de la entrada del algoritmo. 2.- A continuación escogemos el siguiente vértice en la ordenación y le asignamos el menor color posible diferente respecto a sus adyacentes. Repetimos este proceso hasta que todos los vértices del grafo hayan sido coloreados.

En cada paso se le asigna un color a un vértice y no se le vuelve a modificar más a lo largo de la ejecución de ahí el carácter voraz del algoritmo. Aplicaremos el algoritmo la grafo de la figura.

Orden de coloración: v1, v2, v3, v4, v5, v6, v7.

vértices v1 v2 v3 v4 v5 v6 v7

color 1 2 1 3 1 2 2



Algoritmo de coloración Welsh-Powell

La única diferencia respecto al algoritmo voraz es el orden en el que se realiza la coloración de vértices.

En este caso los vértices se ordenan de mayor a menor grado, es decir

en función del número de vértices adyacentes. A continuación aplicaremos la coloración de Welsh-Powell al grafo

anterior. Orden de coloración: v2, v4, v5, v1, v3, v6, v7.


color 3 1 2 2 3 1 1



Algoritmo de coloración Matula-Marble-Isaacson

La única diferencia respecto a los otros dos algoritmos de coloraciones el orden en el que se realiza la coloración vértices.

En este caso el orden de los vértices es inverso al proceso de selección.

Primero se elige vn como el vértice de menor grado, luego se elige vn-1 como el vértice de menor grado en G-{vn} (prescindiendo del vértice vn), y así se continúa examinando los vértices de menor grado y eliminándolos del grafo.

A continuación aplicaremos la coloración de Welsh-Powell al grafo anterior.

Orden de coloración: v5, v4, v2, v1, v7, v3, v6.


color 1 3 1 2 1 2 2



Algoritmo de coloración de Brelaz

El orden de coloración de los vértices depende del grado g(V) y grado de saturación o color de los vértices gs(V) y es determinado en tiempo de ejecución. El grado de un vértice es número de adyacentes del mismo y el grado de saturación es el número colores no repetidos usados en los adyacentes o vecinos. A continuación expondremos los pasos del algoritmo: PASO 1 Calcular el grado de todos los vértices y colorear un vértice de grado máximo con el color 1. PASO 2 Seleccionamos un vértice, aún sin colorear, con grado de saturación o color máximo. Si existen varios vértices con el mismo grado de saturación máximo escogemos el de mayor grado entre esos vértices. Si además coinciden en grado seleccionamos el primero comenzando por la izquierda de la tabla. PASO 3 Colorear el vértice seleccionado en el paso 2 con el menor color posible. PASO 4 Si todos los vértices se han coloreado, FIN. En caso contrario, volver al paso 3.



A continuación aplicaremos la coloración de Brelaz al grafo anterior.

La primera fila almacena el grado o el número de adyacentes de cada vértice y la segunda fila contiene el grado de color o saturación de cada vértice que en principio es cero par todos los vértices pues aún no existe ningún vértice coloreado. La última fila informa del color asignado al vértice. El primer vértice coloreado es el vértice de grado máximo que en nuestro caso es v2 al cual se le asigna el color 1. Tras colorearlo el grado de saturación sus vértices adyacentes aumenta en una unidad. A continuación habría que escoger un vértice de grado de saturación o color máximo pero existen varios por lo que seleccionamos el primer vértice de grado máximo no colorado comenzando por la izquierda de la tabla. Dicho vértice es v4 al cual se le asigna el menor color posible. En este caso el color 2.


grado g(V) 2 4 2 3 3 1 1 saturación gs(V) 0 0 0 0 0 0 0

color - - - - - - - orden - - - - - - -



color - 1 - - - - - orden - 1 - - - - -



color - 1 - 2 - - - orden - 1 - 2 - - -



En los siguientes pasos volvemos a seleccionar vértice con grado de color máximo y si existiera más de uno escogeríamos el de mayor grado, hasta colorear todos los vértices del grafo. Veamos la evolución de la tabla.



color - 1 - 2 3 - - orden - 1 - 2 3 - -



color 3 1 - 2 3 - - orden 4 1 - 2 3 - -



color 3 1 3 2 3 - - orden 4 1 5 2 3 - -



color 3 1 3 2 3 1 - orden 4 1 5 2 3 6 -



color 3 1 3 2 3 1 1 orden 4 1 5 2 3 6 7



¿Es bipartito?

Los grafos bipartitos kn,m, que son aquellos que admiten una partición de sus vértices en dos conjuntos V = X∪Y, de manera que las aristas tienen un extremo en cada uno de estos conjuntos (van de vértices en X a vértices en Y).

El conjunto X e Y constan de “n” y “m” vértices respectivamente. | X | = n. | Y | = m.

Un grafo bipartito si y solo si no contiene ciclos de orden impar o su número cromático X(G) es dos. Estas dos propiedades nos permiten saber si un grafo es bipartito. Teorema El algoritmo de Brelaz colorea con dos colores a los grafos bipartitos. Por lo que tenemos un algoritmo polinómico para decidir si un grafo es bipartito o no. Bastará aplicar la coloración de Brelaz al grafo. Si el número de colores usados es igual a dos entonces el grafo es bipartito. En otro caso el grafo no es bipartito. Veamos el siguiente ejemplo.



Aplicamos el algoritmo de Brelaz.

Como el número de colores utilizados es dos el grafo es bipartito. Veamos otro ejemplo



Aplicamos el algoritmo de Brelaz.

Como el número de colores utilizados es distinto de dos el grafo no es bipartito.



3.11.- Algoritmos de aristas coloración Expondremos dos algoritmos para la coloración de las aristas de un grafo, ambos de carácter voraz. Algoritmo basado en rellenar un cuadrado latino Un cuadrado latino es un matriz cuadrada cuya dimensión es n x n, donde “n” es el número de vértices del grafo. Cada posición de la matriz representa una arista entre dos vértices. Para llevar acabo la coloración rellenaremos la matriz con “n” símbolos de tal forma que no existan símbolos repetidos en ninguna fila o columna. Como curiosidad cabe mencionar que el algoritmo es parecido a la resolución de sodokus salvo que en estos existen aristas previamente coloreadas y nosotros rellenaremos el cuadrado latino sin ninguna restricción añadida. Para rellenar la tabla se comienza de izquierda a derecha y de arriba abajo asignado un color que no este ya en la fila y columna correspondiente a la arista tratada. Seguidamente veremos un ejemplo que aclarará todo lo expuesto anteriormente.



Rellenamos el cuadrado latino. vértices v1 v2 v3 v4 v5 v6 v7 v8 v9

v1 0 1 2 ∞ 3 ∞ 4 ∞ 5 v2 1 0 3 ∞ ∞ ∞ ∞ ∞ ∞ v3 2 3 0 ∞ 1 ∞ ∞ ∞ ∞ v4 ∞ ∞ ∞ 0 2 1 ∞ ∞ ∞ v5 3 ∞ 1 2 0 4 ∞ 5 ∞ v6 ∞ ∞ ∞ 1 4 0 ∞ ∞ ∞ v7 4 ∞ ∞ ∞ ∞ ∞ 0 1 ∞ v8 ∞ ∞ ∞ ∞ ∞ ∞ 1 0 ∞ v9 5 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0

Lógicamente el cuadrado latino es simétrico pues las aristas vivj o vjvi

son la misma para cualquier tipo de grafo en lo que a coloración de arista se refiere, por ello tienen asignado el mismo color. Si una posición del cuadrado latino aparece un infinito indica que no existe arista entre ambos vértices.



Algoritmo basado en emparejamientos maximales Este algoritmo colorea las aritas del grafo utilizando el algoritmo de emparejamiento maximal simple. Para ello comienza buscando un emparejamiento maximal en el grafo. Al conjunto de aristas obtenidas les asigna el color “k”. Seguidamente elimina dichas aristas del grafo y vuelve a calcular un emparejamiento maximal al cual le asigna el color “k+1”. Dicho proceso se repite hasta eliminar todas las aritas del grafo. Iniciar k := 1 Paso 1 Encontrar un emparejamiento máximo M de G, y colorear todas las aristas de M con el color k. Hacer G := G - M. Paso 2 Si el grafo no posee aristas, FIN. En caso contrario hacer k := k+1 y volver al paso 1. A continuación detallaremos un ejemplo para el siguiente grafo.



Calculamos un emparejamiento maximal al cual le asignamos el color 1. Arista (v1, v2). Arista (v3, v5). Arista (v4, v6). Arista (v7, v8). Eliminamos del grafo las aristas del primer emparejamiento.

Calculamos otro emparejamiento maximal y le asignamos el color 2. Arista (v1, v7). Arista (v2, v3). Arista (v4, v5).



Eliminamos del grafo las aristas del segundo emparejamiento.

Calculamos otro emparejamiento maximal y le asignamos el color 3. Arista (v1, v3). Arista (v5, v6).



Eliminamos del grafo las aristas del tercer emparejamiento.

Calculamos otro emparejamiento maximal y le asignamos el color 4. Arista (v1, v5).



Eliminamos del grafo la arista del cuarto emparejamiento.

Calculamos otro emparejamiento maximal y le asignamos el color 5. Arista (v5, v8).



Eliminamos del grafo la arista del quinto emparejamiento.

Como no quedan aristas por colorear el algoritmo termina.



3.-12.- Hamilton Un grafo conexo se dice hamiltoniano cuando admite un ciclo hamiltoniano. Un ciclo hamiltoniano es un ciclo que pasa por todos los vértices del grafo. Un camino hamiltoniano es un camino simple que pasa por todos los vértices del grafo sin repetir ninguno.

Algoritmo de Dirac. El problema de decidir si un grafo es hamiltoniano está abierto (no existe un procedimiento para saber si lo es). Teorema de Dirac.



Un grafo G (V, A) es hamiltoniano si todos los vértices tienen valencia δ(V) ≥ n/2 donde “n” es el número de vértices del grafo. Esta condición es suficiente pero no necesaria por lo que si el grafo no satisface dicha relación no podemos asegurar que no sea hamiltoniano.



Ejemplo 1.

El grafo es hamiltoniano pues todos los vértices tienen valencia mayor o igual que 3.

Vértices • (V) ≥ n/2 v1 5 ≥ 6/2 = 3 v2 3 ≥ 6/2 = 3 v3 4 ≥ 6/2 = 3 v4 4 ≥ 6/2 = 3 v5 3 ≥ 6/2 = 3 v6 3 ≥ 6/2 = 3



Ejemplo 2.

Como existen vértices que no cumplen la relación, no podemos asegurar

que el grafo no sea hamiltoniano.

Vértices δ(V) ≥ n/2 v1 6 ≥ 8/2 = 4 v2 3 ≥ 8/2 = 4 v3 4 ≥ 8/2 = 4 v4 4 ≥ 8/2 = 4 v5 3 ≥ 8/2 = 4 v6 4 ≥ 8/2 = 4 v7 2 ≥ 8/2 = 4 v8 2 ≥ 8/2 = 4



Búsqueda de trayectorias hamiltonianas. El problema de búsqueda de trayectorias hamiltonianas es un problema NP-completo. Aunque existen métodos aproximados se ha optado por un algoritmo de búsqueda exhaustiva, implementado mediante la técnica de backtracing. El esquema que implementa el backtracing:

proc btÓptimo(x: Etapa)

var xsig: Etapa cand: Candidatos prin si (esSolución(x)) si (esMejor()) actualizaSolución() fsi fsi xsig := nuevaEtapa(x) cand := calculaCandidatos(x) mientras (quedanCandidatos(cand)) seleccionaCandidato(cand, xsig); si (esPrometedor(cand, xsig)) anotaSolución(cand, xsig); btOptimo(xsig); cancelaAnotación(cand, xsig); fsi fmientras fin

A continuación comentaremos algunas características del problema que se pretende resolver y detallaremos cada uno de los métodos y clases que hacen posible la búsqueda de la trayectoria hamiltoniana. Comenzaremos por la Clase “Solución” Clase Solución // Atributos solución : Array de enteros. fclase



La solución se almacena en un array de enteros donde que almacena la posición del vértice respecto a la matriz de adyacencias del grafo. El tamaño del array y la profundidad a la que se encuentra la solución en caso de existir vienen determinados por el número de vértices del grafo. Podemos decir que si existe la solución se encuentra a dicha profundidad en el árbol de expansión, en otro caso no existe solución. Una vez que se encuentra una solución el se para el proceso de búsqueda y reconstruiremos la trayectoria a partir de las posiciones del los vértices en la matriz de adyacencias. Además al no tratarse de un problema de optimización el método “esMejor” retorna siempre “cierto”. y actualiza solución se deja vacío.

Clase “Candidatos” Clase Candidatos // Atributos

vérticesDestinos: Array de enteros i: entero fclase

El array almacena las posiciones de los posibles vértices destinos respecto a la matriz de adyacencias del grafo del último vértice que forma parte de la trayectoria hamiltoniana que no hayan sido ya considerados por lo que todos los candidatos son prometedores, por ello el método “esPrometedor“ siempre retornará “cierto”. En la primera etapa Los candidatos se obtienen en el método “calculaCandidatos”. El entero “i” se utiliza para iterar y seleccionar el vértice candidato, operación realizada en el método “seleccionaCandidato”.



Clase “Etapa” Clase Etapa // Atributos k: entero fclase El entero almacena la profundidad del árbol de expansión. Ahora detallaremos los atributos de la clase que da cuerpo a cada uno

de los métodos del esquema. Clase “HamiltoBacktracing” Clase “HamiltoBacktracing”

// Matriz de adyacencias del grafo. adyacencias: Array [][] de real

hamiltoniano: Array de entero // Tipo de trayectoria búsqueda (ciclo o camino) ciclo: Lógico // Número de vértices del grafo. numVértices: entero. vérticeActual: entero // Si su valor es “cierto” se ha encontrado la solución. solEncontrada: Lógico // Almacenará la trayectoria si se encuentra.

sol: Solución fclase El array “hamiltoniano” almacena la secuencia de posiciones de los vértices que forman parte de la trayectoria respecto a la matriz de adyacencias del grafo y el entero “vérticeActual” almacena la posición del último vértice que forma parte de la trayectoria. El tipo de trayectoria buscada es elegida por el usuario.



Finalmente comentar que en el método “anotaEnSolución” se añade el vértice candidato a la trayectoria parcialmente construida y en “cancelaAnotación” solo decrementamos el valor de la etapa.

Para aclara todo lo expuesto anteriormente realizaremos una serie ejemplo.

Consideremos el siguiente grafo en el cual encontrar el ciclo o camino

hamiltoniano es trivial pero nos servirá para mostrar el árbol de expansión completo. En el árbol en vez de mostraremos los vértices y no las posiciones que estos ocupan en la matriz de adyacencias.

En este caso el array que almacena la solución posee tamaño 3 y a dicha profundidad obtendremos la solución, pero seguiremos expandiendo el árbol para ver como evoluciona aunque no es necesario y de hecho no se realiza en la implementación proporcionada para la aplicación pues seria una perdida de tiempo. Al lado de cada tupla entre llaves aparecen lo candidatos. Etapa [-, -, -] {v1, v2, v3}

k= 0

[v1, -, -] {v2, v3} [v2, -, -] {v1, v3} [v3, -, -] {v1, v2} k = 1 [v1, v2, -] [v1, v3, -] [v2, v1, -] [v2, v3, -] [v3, v1, -] [v3, v2, -]



k = 2 {v3} {v2} {v3} {v1} {v2} {v1} [v1, v2, v3] [v1, v3, v2] [v2, v1, v3] [v2, v3, v1] [v3, v1, v2] [v3, v2, v1]



La solución encontrada es v1-v2-v3 si se desea el camino o v1-v2-v3 -v1 en el caso del ciclo, el resto del árbol no seria necesario generarlo. En cada tupla se actualiza la posición correspondiente con la etapa en la que nos encontramos considerando que las posiciones del array comienzan en cero. A continuación expondremos otro ejemplo con su árbol de expansión para un grafo en el que existe un camino hamiltoniano. Una vez encontrado el camino no seguiremos expandiendo el árbol.

Etapa [-, -, -, -] {v1, v2, v3, v4}

k = 0 [v1, -, -, -,] {v2, v3, v4} [v2, -, -, -] {v1} k = 1 [v1, v2, -, -] {} [v1, v3, -, -] {v4} [v1, v4, -, -] {v3} [v2, v1, -, -] {v3, v4} k = 2 [v1, v3, v4, -] {} [v1, v4, v3, -] {} [v2, v1, v3, -] {v4} k = 3

[v2, v1, v3, v4]



El camino hamiltoniano es v2-v1-v3-v4.



Finalmente podremos un ejemplo de búsqueda de un ciclo hamiltoniano en el que solo mostraremos la solución.

El ciclo hamiltoniano es v3-v5-v1.v2.v4-v6-v3.



4.- Bibliografía Apuntes de la asignatura de matemática discreta de la escuela técnica superior de informática de la universidad de Sevilla http://ma1.eii.us.es/miembros/mcruz/MD/md_ii.html. Apuntes de la asignatura de teoría de grafos de la escuela técnica superior de informática de la universidad de Sevilla http://ma1.eii.us.es/Docencia/Doc_info/XSLT.asp?xml=teorgraf.xml&xsl=programa.xsl&par=esp:. Coloración de vértices y aristas http://www.dma.fi.upm.es/grafos/color03.pdf. Apuntes sobre grafos eulerianos http://www.google.es/search?hl=es&q=grafos+German+Combariza&btnG=B%C3%BAsqueda&meta=. Conectividad en grafos http://mipagina.cantv.net/jhnieto/md/Grafos.pdf.

algoritmos de grafos

Documents