Universidad de los Andes

El Problema del Arbol MınimoGenerador de un Grafo. Algoritmos y

Complejidad.

Autor:Juan Pablo Henao Henao

Director:Tristram Bogart

Noviembre 18, 2015

Indice general

1. Algoritmo de Kruskal 4

2. Algoritmo de Tarjan y Cheriton 17

3. Grafos Densos y Planares 28

4. Medidas de Similaridad entre Superficies 34

A. Teorıa de Grafos 41

B. Complejidad Computacional 44

1

Resumen

El problema de encontrar el arbol mınimo generador (AMG) de un grafo es estudiado. Se estudiandiferentes algoritmos para resolverlo. Dichos algoritmos se deben a resultados de Kruskal y deTarjan y Cheriton. Ademas se estudia la complejidad computacional teorica de estos, y se verificanlos resultados con implementaciones de dos algoritmos diferentes. Ademas, para grafos densos yplanares Tarjan y Cheriton proponen una complejidad computacional lineal. Finalmente se estudiauna aplicacion del problema al calculo de medidas de similaridad entre superficies representadascomo nubes de puntos.

Palabras clave: Arbol mınimo generador, Algoritmo de Kruskal, Algoritmo de Tarjan y Cheriton,Complejidad computacional, Grafos densos y planares, Medidas de similaridad de superficies.

2

Introduccion

El AMG, es un problema clasico de optimizacion combinatoria cuyo estudio tomo fuerza alrededorde 1950 con el interes creciente en los campos de computacion y algoritmos [1]. Este problema esimportante debido a sus diferentes aplicaciones practicas y teoricas.

El problema de encontrar el Arbol Mınimo Generador (AMG) se puede formular de la siguienteforma: dado un grafo conexo G = (V,E) con n vertices y m arcos, y una funcion peso c : E → R≥0

en sus arcos, se quiere encontrar un arbol generador1 T = (V,E′) tal que el peso total∑

vw∈E′ c(vw)sea mınimo [2].

Una de las formas de atacar el problema es resolverlo como un problema de programacion entera.No obstante, este trabajo tiene otro enfoque que es el estudio de algoritmos sobre grafos queresuelven el problema. Uno de los algoritmos mas conocidos, es el algoritmo de Kruskal (1956),que resuelve el problema buscando soluciones optimas locales que resultan en una solucion global.Es lo que se conoce como un algoritmo goloso.

El objetivo de este proyecto es investigar y entender diferentes algoritmos que han sido disenadospara resolver el problema. Ademas, se quiere entender la complejidad computacional de estos, eimplementarlos para verificar los resultados teoricos.

El trabajo se divide en cuatro partes principales. En el primer capıtulo se estudia el algoritmo deKruskal que permite resolver el problema en tiempo O(m log n). En el segundo, se muestra una for-ma de resolver el problema cuyo tiempo de ejecucion es O(m log logn). Luego, en el tercer capıtulo,se estudia otro algoritmo que se puede implementar de forma tal que el tiempo de ejecucion sealineal para grafos densos y planares. Posteriormente, en el capıtulo cuatro, se introduce el problemadel calculo de medidas de similaridad entre superficies, y se explica la forma en la que se debenencontrar arboles generadores de peso mınimo para resolverlo. Se finaliza con algunas conclusionesy comentarios finales. Los apendices sobre teorıa de grafos y complejidad computacional se puedenutilizar como referencia para entender la notacion del trabajo, y consultar resultados conocidos enestas areas.

1Ver las notas sobre teorıa de grafos para la definicion formal de arbol generador

3

Capıtulo 1

Algoritmo de Kruskal

Este algoritmo puede ser tal vez el mas encontrado en la bibliografıa [3, 4, 5]. Fue propuesto porJoseph Kruskal en 1956 [6]. Al utilizar estructuras de datos apropiadas el algoritmo puede resolverel problema en tiempo O(m log n) donde m y n son respectivamente el numero de arcos y verticesdel grafo.

Recordemos la formulacion del problema de encontrar el Arbol Mınimo Generador (AMG) de ungrafo conexo. Dado G = (V,E) y una funcion peso c : E → R≥0 en sus arcos, se quiere encontrarun arbol generador1 T = (V,E′) tal que el peso total

∑vw∈E′ c(vw) sea mınimo.

De forma general el algoritmo se puede describir facilmente de la siguiente forma [3]. En primerlugar se deben ordenar los arcos de forma no decreciente de acuerdo a su peso. Luego se vaneligiendo los arcos en orden y se incluyen en el AMG si estos no generan ciclos. Ası, se recorrentodos los arcos y al final se obtiene un AMG. Tambien se puede parar sin necesidad de recorrertodo el conjunto de arcos, pues una vez se hayan elegido n− 1 arcos se obtiene un AMG 2.

Mas formalmente el algoritmo se puede describir ası [3, 4]:

Data: A weighted graph G = (V,E, c).Result: A Minimum Spanning Tree T .Sort edge set E in nondecreasing order according to weight ;T := ∅;Create one set for each vertex;for each edge (u, v) in sorted list do

x := FIND(u);y := FIND(v);if x 6= y then

T := T ∪ {u, v};UNION(x, y)

end

endAlgorithm 1: Kruskal Algorithm

El algoritmo FIND funciona como una subrutina que se utiliza para poder verificar que el arcoque se esta considerando no genera un ciclo en T , es decir, con las aristas que ya se han elegido.Es importante que al comienzo del algoritmo cada vertice se representa con un conjunto. Estorepresenta un subgrafo de G, que es un bosque en el que inicialmente todos los vertices estanaislados. A partir de esta inicializacion, y utilizando los algoritmos UNION y FIND se puedenrastrear los vertices y cuales pertenecen a una misma componente conexa (arbol) del bosque T .Por un lado, el algoritmo FIND(u) permite encontrar el conjunto en el que se ubica el elemento

1Ver las notas sobre teorıa de grafos para la definicion formal de arbol generador2Ver las notas sobre Teorıa de Grafos

4

que ingresa por parametro. En el algoritmo, si los vertices u y v pertenecen al mismo conjunto(componente conexa) quiere decir que el arco que se esta considerando debe ser descartado puesgenera un ciclo en T . En caso contrario, se debe anadir el arco, y unir dos componentes conexascon el algoritmo UNION. Al final, T sera el AMG del grafo G[3]. La implementacion de estosalgoritmos, y las estructuras de datos utilizadas para tal fin se explicaran mas adelante al mostrarla implementacion realizada.

Ejemplo:

El siguiente ejemplo paso a paso ayuda a entender el funcionamiento del algoritmo y la forma en laque va cambiando el bosque T y sus componentes conexas hasta llegar a un AMG. Consideremosel siguiente grafo conexo con pesos G:

En el primer paso se debe ordenar el conjunto de arcos {e1, e2, e3, e4, e5, e5}. El resultado es:{e4, e5, e1, e2, e3, e6}. Ahora se consideran los vertices en orden, y se obtiene la siguiente serie depasos, cada uno representa el bosque en una iteracion intermedia:

Figura 1.1: Paso 1. Bosque inicial. Componentes conexas: {v1}, {v2}, {v3}, {v4}

5

Figura 1.2: Paso 2. Componentes conexas: {v1}, {v2, v4}, {v3}

Figura 1.3: Paso 3. Componentes conexas: {v1, v2, v4}, {v3}

Figura 1.4: Paso 4. Componentes conexas: {v1, v2, v3, v4}

En el paso anterior se obtuvo un AMG con peso total 13 del grafo G. En este caso se paro elalgoritmo al haber seleccionado n− 1 = 3 aristas. Se puede verificar que considerar cualquiera delos arcos restantes {e1, e3, e6} hubiera resultado en la creacion de ciclos. Finalmente se muestra elresultado del algoritmo:

6

Figura 1.5: Paso 4. El arco e1 es rechazado por generar un ciclo. Se acepta el siguiente arco e2, yse obtiene el resultado del algortimo de Kruskal

Correctitud del algoritmo:

Es importante probar que el algoritmo de Kruskal es correcto. Es decir que siempre construye unAMG para cualquier grafo conexo G que ingresa por parametro. Vamos a demostrar la correctituddel algortimo como en [3].

Definicion 1.1: Sea G = (V,E) un grafo. Un bosque generador para G es una coleccion de arbolesdisyuntos por vertices Ti = (Vi, Ei), 1 ≤ i ≤ k, que satisface V =

⋃1≤i≤k Vi y Ei ⊆ E para

1 ≤ i ≤ k. donde k es un numero entero.

Lema 1.1: Sea Ti = (Vi, Ei), 1 ≤ i ≤ k, k > 1 un bosque generador del grafo conexo con pesosG = (V,E, c). Dado un j, 1 ≤ j ≤ k fijo, sea e = (u, v) un arco con peso mınimo que satisface quesi u ∈ Vj , entonces v /∈ Vj . Sea E′ =

⋃1≤i≤k Ei. Entonces existe un AMG para G que incluye los

arcos E′ ∪ {e} y tiene peso mınimo entre todos los arboles para G que incluyen a E′.

Demostracion. Supongamos para llegar a una contradiccion, que no existe dicho arbol generador.Entonces como el grafo es conexo, debe existir un arbol generador T = (V,E′′) para G, que incluyea E′ pero no a e. Ademas, T tendrıa menor peso que el arbol generador para G que incluye E′∪{e}.

Siendo un arbol, T es conexo, por lo que existe un camino entre u y v. Como T no contiene a e,al considerar el grafo T ∪ {e}, se genera un ciclo. Ası, existe otro arco e′ = (u′, v′) que satisfaceu′ ∈ Vj , pero v′ /∈ Vj y ademas por hipotesis c(e) ≤ c(e′).

Ahora se puede considerar el arbol T ′ = T ∪ {e} − {e′}. El resultado es un arbol generador deG que contiene a E ∪ {e′}. Este arbol tiene peso menor o igual que T , pues c(e) ≤ c(e′). Ası, seobtiene una contradiccion. Se concluye que dicho T no existe y el lema queda demostrado.

Teorema 1.1. El algoritmo de Kruskal es correcto. Es decir que dado un grafo conexo G, siemprese retorna un arbol generador de peso mınimo al alplicar el algoritmo.

Demostracion. Recordemos que al iniciar, el algoritmo de Kruskal comienza con un bosque genera-dor sin arcos en el que los arboles son los vertices aislados del grafo G. En una iteracion intermediase cuenta con un bosque generador. Por el lema anterior se puede considerar el siguiente arco demenor peso que no genere ciclos, y el bosque resultante estara contenido en un AMG de G.

Luego de saber que el algoritmo funciona de manera correcta, se puede comenzar a discutir suimplementacion.

La primera parte importante del algoritmo consiste en organizar el conjunto de arcos en orden nodecreciente. Esto se puede hacer de manera eficiente. Una forma de hacerlo se explica a continua-cion.

7

Ordenamiento por Montıculos [3]

En general dada una lista E = (e1, ..., em) con m elementos, esta lista se puede representar con lasiguiente estructura de arbol.

Es importante notar que la enumeracion de la lista determina la posicion de un elemento dentrode la estructura que representa la lista E. Ası, dado un elemento con subındice i, su padre estaraen la posicion bi/2c, y sus hijos en las posiciones 2i, y 2i+ 1 (en caso de existir).

Para llevar a cabo el proceso de ordenar la lista, el primer caso es convertir la anterior estructuraen un montıculo. La estructura de montıculo se utiliza para poder ordenar la lista E de formaeficiente.

Definicion 1.2: Un montıculo, es un arbol binario cuyos nodos se ubican de acuerdo a la enume-racion presentada, y que ademas satisface la siguiente propiedad: el valor de un nodo (por ejemploel peso de un arco) es mayor o igual que el valor de sus hijos.

Nota: como los nodos de un montıculo se ubican en orden de acuerdo a la enumeracion de laimagen, un montıculo resulta ser un arbol balanceado, es decir que sin contar el ultimo nivel, elarbol tiene el mismo numero de nodos en cada una de las ramas que se estienden desde la raız.

Utilizando los siguientes algoritmos3 se puede convertir cualquier lista en un montıculo, y poste-riormente ordenar de forma no decreciente. En este caso, el conjunto a ordenar es el conjunto dearcos de un grafo. Para representar este conjunto se utilizo una lista de 3-tuplas. Las primeras dosposiciones de la tupla son los extremos de un arco, y la tercera, su peso. En los algoritmos, estaestructura corresponde al objeto Edges.

3Los algoritmos se pueden encontrar por ejemplo en [3]. No obstante la implementacion es del autor. Se utilizo ellenguaje de programacion Python, y se programo en SageMathCloud [7]: https://cloud.sagemath.com. En Python2//j = b2/jc.

8

Figura 1.6: Algoritmo ADJUST

El algoritmo ADJUST es una subrutina del algoritmo final HSORT que ordena la lista y que semostrara mas adelante. Dado un nodo de la lista con ındice i, y el maximo numero de nodos nque contiene el subarbol cuya raız es i, el algoritmo ADJUST modifica la lista de forma tal que elsubarbol con raız i satisfaga la propiedad de los montıculos. Como condicion para que el algoritmofuncione, se debe saber que los dos subarboles del nodo i, satisfacen la propiedad.

Lema 1.2: El tiempo de ejecucion de ADJUST es O(k), donde k es la profundidad del subarbolcuya raız es i.

Demostracion. La complejidad del algoritmo esta dominada por el ciclo while. Si el subarbol tienea lo sumo n nodos y profundidad k, entonces n ≤ 2k.

Ahora bien, el ciclo while tiene condicion de parada j ≤ n. Y el aumento de j es j = 2 · j.Supongamos que l cuenta el numero de veces que se ha realizado el ciclo while. Entonces j = 2l. Apartir de lo anterior se concluye que el ciclo while se realiza a lo sumo l veces donde 2l ≤ n ≤ 2k.Por lo tanto l ≤ log 2k = k. El tiempo de ejecucion de ADJUST es entonces O(k).

Utilizando ADJUST se puede ordenar la lista Edges de n elementos con HSORT:

9

Figura 1.7: Algoritmo HSORT

El primer ciclo while se encarga de convertir la lista en un montıculo. Se comienza con el padredel ultimo nodo (ındice bn/2c), y se ajustan todos los subarboles para que satisfagan la propiedaddel montıculo hasta terminar con el arbol completo.

El segundo ciclo se encarga de modificar la lista Edges para que al final resulte ordenada en ordenno decreciente. Este ciclo debe ajustar arboles cada vez mas pequenos, e ir guardando al final deEdges los arcos con mayor valor.

Lema 1.3: El tiempo de ejecucion de HSORT es O(m logm), donde m es el tamano de la listaque se esta ordenando.

Demostracion. El algoritmo HSORT contiene dos ciclos. Se puede analizar la complejidad de cadaciclo por separado.

Primer ciclo: sea k el numero de niveles que tiene el arbol que representa la lista. Entonces2k−1 ≤ m ≤ 2k. Ademas, el numero de nodos en un nivel i es menor o igual a 2i−1. Para un nodoen el nivel i, el subarbol que contiene a ese nodo como raız tiene profundidad k − i + 1. En elprimer ciclo se realiza a lo sumo ADJUST para todos los nodos de todos los niveles, es decir quela complejidad es:

O(

k∑i=1

2i−1(k − i+ 1))

Ahora, haciendo la sustitucion en la suma l = k − i+ 1, se obtiene:

k∑i=1

2i−1(k − i+ 1) =

k∑l=1

2k−l · l

Y se puede analizar la siguiente cadena de desigualdades:

10

k∑l=1

2k−l · l =

k∑l=1

2k/2l · l

=

k∑l=1

2k−1/2l−1 · l

≤ mk∑

l=1

l

2l−1pues 2k−1 ≤ m

≤ mk∑

l=1

k

2l−1

≤ m∞∑l=1

k

2l−1

≤ m · k

1− 1/2

= 2nk

≤ 2m(logm+ 1) pues k ≤ logm+ 1

= 2n logm+ 2n

= O(m logm)

Segundo ciclo: Este ciclo se recorre m−1 veces, y en cada iteracion se llama ADJUST que es O(k),y k ≤ logm+ 1. Luego la complejidad de este ciclo es:

O((m− 1) · (logm+ 1)) = O(m logm+m− logm− 1) = O(m logm)

Es decir la complejidad de todo el algoritmo es:

O(m logm) +O(m logm) = 2 ·O(m logm) = O(n logm)

Manejo de Componentes Conexas:

Como vimos antes, el algoritmo de Kruskal requiere hacer un manejo de conjuntos que representancomponentes conexas. Este manejo se puede hacer mediante los algoritmos FIND y UNION. Paraentender estos algoritmos, es necesario explicar primero que un conjunto se puede representar conuna estructura de arbol. Por ejemplo los conjuntos {1, 2, 3} y {4, 5, 6, 7} se pueden representar ası:

Figura 1.8: Los conjuntos {1, 2, 3} y {4, 5, 6, 7}

11

Y su union {1, 2, 3, 4, 5, 6, 7}, por ejemplo, ası 4:

Figura 1.9: La union {1, 2, 3} ∪ {4, 5, 6, 7} = {1, 2, 3, 4, 5, 6, 7}

Es importante notar que un conjunto no vacıo siempre tiene una raız, y cada elemento (diferente dela raız) siempre tiene un padre (el nodo padre en la estructura de arbol). Ası, un conjunto se puedeidentificar con la raız del arbol que lo representa y para cada nodo se puede guardar referencia asu nodo padre. Como el nodo raız no tiene padre, para implementar los alogritmos necesarios seutilizara la convencion de que la referencia de la raız sera el numero de nodos que tiene el conjunto(arbol) por menos uno. Tambien note que el algortimo UNION se utiliza solo para unir conjuntos(componentes conexas) disyuntos.

En este sentido, el algoritmo FIND(i) consiste en encontrar la raız del arbol que contiene el elementoi, y el algoritmo UNION(i, j) junta los conjuntos (arboles) que tengan raices i y j.

La implementacion de estos algoritmos se muestra a continuacion5:

Figura 1.10: Algoritmo UNION

4Note que los conjuntos son disyuntos y por lo tanto es facil representar la union. De hecho, todos los conjuntosque se manejan en el algoritmo de Kruskal son componentes conexas (disyuntos), y por lo tanto no es necesariopreocuparse por otro caso

5Nuevamente se puede ver por ejemplo [3], la implementacion es del autor.

12

Figura 1.11: Algoritmo FIND

Los siguientes comentarios importantes se deben hacer sobre las implementaciones anteriores. Enprimer lugar V es una estructura de datos que representa el conjunto de vertices del grafo G. Masaun, la estructura de datos implementada permite almacenar la informacion de las componentesconexas en cada iteracion, teniendo en cuenta las estructuras de arboles planteadas. Esto funcionade la siguiente forma. Se utilizo la estructura de datos diccionario en el lenguaje de programacionPython. Esta estructura permite asignar a cada elemento de una lista (los nodos del grafo) unvalor. Para implementar estos algoritmos de forma eficiente se sigue la siguiente convencion: Elvalor de un nodo es su padre si este nodo no es una raız. Si el nodo es una raız, su valor es −1por numero de nodos que contiene el conjunto. Finalmente el algoritmo UNION sigue la siguienteregla: Asignar como padre del arbol (conjunto) con menos nodos la raız del arbol con mas nodos.

Ası, en el ejemplo presentado anteriormente, se deberıa inicializar la estructura:

V = {1 : −1, 2 : −1, 3 : −1, 4 : −1}

,donde se supone que los vertices del grafo estan numerados de 1 a 4. Note que inicialmente haycuatro componentes conexas, cada una con un solo vertice, y por lo tanto todos los nodos tienenel valor −1. De igual forma, por ejemplo en el paso 4, la estructura tendrıa la siguiente forma:

V = {1 : −4, 2 : 1, 3 : 1, 4 : 2}

Que corresponde al arbol:

Finalmente se obtiene la complejidad de cada uno de los algoritmos:

Lema 1.4: El tiempo de ejecucion de UNION es O(1).

Demostracion. Este algoritmo no depende del tamano del problema, sin importar el tamano de lainstancia, el tiempo de ejecucion esta acotado por una constante, es decir es O(1).

13

Lema 1.5: Sea T un arbol con n nodos creado a partir del algoritmo UNION. Entonces la profu-nididad de T es a lo sumo blog2 nc+ 1.

Demostracion. La prueba es por induccion (fuerte) en n.

Si n = 1, entonces el arbol tiene 1 nivel, y 1 ≤ blog2 1c+ 1 = 1.

Supongamos ahora que la propiedad se cumple para todos los arboles con n− 1 nodos o menos. Yveamos que es cierto para los arboles con n nodos:

Sea T un arbol con n nodos creado por el algoritmo UNION. Supongamos que T se obtuvo a partirde unir los arboles T1 y T2 con m y n−m nodos respectivamente. Sin perdida de generalidad, sepuede asummir que T1 era el arbol con menor numero de nodos, y ası: 1 ≤ m ≤ n/2, y se tienen−m ≥ m. De esta forma, la profundidad del arbol T2 es mayor o igual a la maxima profundidad deT1, pues utilizando la hipotesis de induccion: profundidad(T1) ≤ blog2mc+1 ≤ blog2 (n−m)c+1.Se pueden manejar dos casos para la profundidad resultante del arbol T :

Caso 1: profundidad(T1) < blog2 (n−m)c+1. En este caso, profundidad(T ) ≤ blog2 (n−m)c+1 ≤blog2 nc+ 1. Y se obtiene el resultado.

Caso 2: profundidad(T1) = blog2 (n−m)c+1. En este caso la profundiad de T puede ser a lo sumoun nivel mas que la del arbol T1. Y se tiene: profundidad(T ) ≤ blog2mc+ 1 + 1 ≤ blog2 n/2c+ 2 =blog2 nc − log2 2 + 2 = blog2 nc+ 1. Y tambien se obtiene el resultado.

En cualquier caso profundidad(T ) ≤ blog2 nc+ 1 y la demostracion queda completa.

Lema 1.6: Si un arbol es construido utilizando el algoritmo UNION, el tiempo de ejecucion deFIND es O(log n), donde n es el numero de nodos que tiene el arbol en el que se esta buscando.

Demostracion. Por el lema anterior, cualquier arbol con n nodos construido con el algoritmoUNION tiene profundidad a lo sumo blog2 nc + 1. El algoritmo FIND(i) consiste en partir delnodo i y recorrer sus antecesores hasta llegar a la raız del arbol. Es decir que el ciclo while serecorre a lo sumo O(blog2 nc+ 1) = O(log n) veces.

Implementacion del Algoritmo de Kruskal:

Finalmente se tiene la siguiente implementacion final del algoritmo de Kruskal:

Figura 1.12: Implementacion algoritmo de Kruskal

El analisis final de la complejidad del algoritmo se hace en el siguiente teorema:

14

Teorema 1.2. El tiempo de ejecucion del algoritmo de Kruskal es O(m log n). Donde m y n sonrespectivamente el numero de arcos y vertices del grafo que se recibe por entrada.

Demostracion. El algoritmo de Kruskal se divide en los siguientes dos pasos importantes:

Paso 1: Ordenar el conjunto de arcos.

En este paso la complejidad es O(m logm) utilizando el algoritmo de ordenamiento por montıculospropuesto anteriormente.

Paso 2: Recorrer el conjunto de arcos ordenado, y aceptar aquellos que no generen ciclos.

En este paso se recorre un ciclo que toma tiempoO(m). En este ciclo se realiza dos veces la subrutinaFIND cuyo tiempo de ejecucion es O(log n). El resto del algoritmo, incluyendo al algoritmo UNIONes O(1). Luego el tiempo total es:

O(m) · (O(2 log n)) = O(m log n)

Ası, el tiempo total esta determinado por el Paso 1 6:

O(m logm) +O(m log n) = O(m logm)

Finalmente, se puede notar que m ≤ n2, pues la definicion propuesta admite unicamente grafossimples7. Entonces,

O(m logm) = O(m log n2) = O(2m log n) = O(m log n)

Y la demostracion queda terminada.

Resultados:

La implementacion propuesta del algoritmo, fue probada con el siguiente experimento: Los AMGde los grafos en la tabla fueron calculados. Se asignaron pesos aleatorios entre 1 y 50 a cada arco.Y se realizo una unica corrida por cada instancia. Se obtuvieron los siguientes resultados:

Notacion: Kn es el grafo completo en n vertices y Kn,n es el grafo completo bipartito n vertices.

Para realizar este experimento se implemento un contador, que permitiera contar el numero depasos que se requerıan para resolver una instancia dada, luego se comparo este dato contra m log npara obtener un valor experimental de la constante de proporcionalidad C. La idea era verificarexperimentalmente que la complejidad del algoritmo implementado era la demostrada teoricamen-te.

Graph Constante Calculada

K4 9.92K5 9.39K6 8.48K7 8.48K10 7.75K3,3 7.35K5,5 6.84K7,7 6.44K10,10 6.34K50,50 5.93

6Al menos que m = n− 1 en cuyo caso el tiempo de ejecucion es O(m logn) y se tiene el resultado. Note que engeneral m ≥ n− 1 para que exista un arbol generador.

7En cualquier caso, note que sin importar si el grafo es simple, o un multigrafo, se podrıa establecer el tiempode ejecucion del algoritmo de Kruskal como O(m logm).

15

Para las instancias evaluadas, se puede ver que la constante de proporcionalidad calculada noaumenta con el tamano de las instancias. Mas aun, parece que la constante disminuye para pro-blemas de tamano cada vez mayores. Si bien es cierto que esta no es una prueba formal paracalcular la constante de proporcionalidad del algoritmo implementado, sı es interesante ver que losresultados nos muestran que el algoritmo parece estar funcionando con la complejidad propuestateoricamente.

16

Capıtulo 2

Algoritmo de Tarjan y Cheriton

En esta seccion se estudia un algoritmo por Tarjan y Cheriton [2] que se puede implementar entiempo O(m log log n). Para comenzar, se puede enunciar el siguiente algoritmo general que resuelveel problema.

Paso Uno: Elegir cualquier vertice de G y el arco incidente a este con menor peso. Este sera elprimer arco del AMG.

Igual que en el algoritmo de Kruskal, en una iteracion intermedia se han elegido algunos arcos queconstituyen el AMG del grafo. Dichos arcos, junto con todos los vertices forman un subgrafo de Gque ademas es un bosque. En este bosque los vertices aislados son arboles con un solo vertice.

Paso Dos: Seleccione un arbol T del bosque1 y el arco no elegido con el menor peso que seaincidente a T y a otro arbol diferente T ′, llamemoslo xy. Ademas elimine todos los arcos cuyo pesosea menor que el de xy y cuyos dos extremos sean incidentes a T , pues estos arcos forman ciclos.Aceptar(seleccionar) el arco xy en el AMG y unir los arboles T y T ′.

El paso dos se puede repetir hasta encontrar el AMG. Es decir hasta que el bosque contenga ununico arbol, o lo que es equivalente, que se hayan sleccionado n− 1 vertices.

El siguiente paso es opcional, y se puede realizar en cualquier momento. Como se mostrara masadelante, realizar el paso tres puede ser util para encontrar un AMG de grafos con ciertas propie-dades.Paso Tres: Para todos los arboles, elimine los arcos no seleccionados cuyos dos extremos seanincidentes al mismo arbol. Ademas, para cada par de arboles diferentes conectados por arcos noseleccionados, elimine todos los arcos, menos el de menor peso.

Para obtener la complejidad O(m log log n) deseada se utiliza el algortimo anterior, y se divide suejecucion en distintas etapas que se explicaran mas adelante.

Validez del algoritmo:

La validez de este algoritmo sigue del siguiente lema:

Lema 2.1: Sean X ⊆ V , vw ∈ E tales que v ∈ X, w ∈ V −X y c(vw) = min{c(xy)|xy ∈ E, x ∈X, y ∈ V −X}. Entonces algun AMG contiene a vw.

Demostracion. Este es un caso particular del lema 1.1. Es el caso en el que el bosque generadorcontiene solo dos arboles con conjuntos de vertices X y V −X.

1En la version general del algoritmo la eleccion es arbitraria, se puede seleccionar arbitrariamente un arbol T yen cualquier caso el algoritmo retornara un AMG.

17

Teorema 2.1. Dado un grafo conexo G = (V,E, c), El algoritmo propuesto encuentra correcta-mente un AMG para G.

Demostracion. En cualquier iteracion del algoritmo se selecciona un arbol T . Tomando X como elconjunto de vertices de T , y aplicando el lema anterior, se tiene que existe un AMG que contieneel arco que selecciona el algoritmo.

El caso particular del algoritmo anterior en el que la seleccion de T es siempre la misma, se conocecomo algoritmo de Prim [8]. Este caso particular tambien se puede implementar de forma tal quesu tiempo de ejecucion sea O(m log n) [2].

El Algoritmo:

Para implementar el algoritmo propuesto se deben tener en cuenta dos aspectos importantes.En primer lugar, se debe tener informacion sobre los arboles en cada iteracion, los vertices quecontienen, y realizar operaciones sobre estos, tal como se hizo en el algoritmo de Kruskal. Ensegundo lugar, se debe tener una lista de todos los arcos incidentes a cada arbol. Para lograrresolver el problema de encontrar un AMG en tiempo O(m log log n) se implementa el algoritmogeneral prestando atencion principalmente a:

1. La seleccion del arbol T que se considera en cada iteracion del algoritmo.

2. La implementacion de las listas de arcos incidentes a cada arbol. En esta parte, la listas sevan a considerar como filas de arcos que esperan ser admitidos o rechazados en el AMG.

En esta seccion se describe detalladamente la implementacion eficiente del algoritmo de acuerdo alos puntos mencionados anteriormente [2].

Arboles y componentes conexas: Recordamos las siguientes operaciones importantes sobrelas componentes conexas de los arboles del bosque en una iteracion del algoritmo:

FIND(x): Retorna la raız del conjunto que contiene al elemento x.

UNION(i, j): Junta los conjuntos con raıces i y j.

Adicionalmente se puede implementar:

INIT(i, L): Inicializa un conjunto i con los vertices de la lista L.

Filas de arcos adyacentes: Al igual que las operaciones sobre los vertices, tambien se necesitanoperaciones sobre las filas (listas) de arcos adyacentes a un arbol:

QUNION(i, j): junta las filas i y j formando una unica nueva fila.

MIN(i): Retorna el arco mas pequeno en la fila del arbol i que tiene un extremo fuera de i.Ademas, elimina de la fila el arco retornado, y todos los arcos mas pequenos que este (losque generan ciclos) 2.

QINIT(i, L): Inicializa la fila i con los arcos de la lista L.

Algoritmo FIND: Con el fin de obtener la complejidad deseada, es necesario realizar una nuevaimplementacion del algoritmo FIND. La primera parte del algoritmo es igual que el algoritmoFIND utilizado en la implementacion del algoritmo de Kruskal. No obstante se anade una parteadicional para mejorar la complejidad cuando el algoritmo se usa repetitivamente.

2Como es de esperar, este algoritmo debe utilizar como subrutina el algoritmo FIND para verificar si un arcotiene un extremo fuera del arbol i.

18

Figura 2.1: Algoritmo FIND

Las ventajas de este nuevo algoritmo se enuncian a continuacion:

Lema 2.2: El tiempo de ejecucion de este algoritmo FIND tambien es O(log n), donde n es elnumero de nodos que tiene el arbol en el que se esta buscando.

Demostracion. Por un lema visto anteriormente, cualquier arbol con n nodos tiene profundidada lo sumo blog2 nc + 1. La primera parte del algoritmo FIND(i) consiste en partir del nodo i yrecorrer sus antecesores hasta llegar a la raız del arbol. Es decir que el primer ciclo while se recorrea lo sumo O(blog2 nc+ 1) = O(log n) veces. Lo mismo sucede con el segundo ciclo while. Entoncesel tiempo de ejecucion total es O(log n+ log n) = O(log n).

Definicion 2.1: La funcion de Ackermann se define recursivamente por:

A(p, q) =

2q p = 0

0 q = 0 y p ≥ 1

2 p ≥ 1 y q = 1

A(p− 1, A(p, q − 1)) p ≥ 1 y q ≥ 2

Definicion 2.2: Se define el funcional inverso a la funcion de Ackermann, como:

α(m,n) := min{z ≥ 1|A(z, 4dm/ne) > log2 n}

Mientras que la funcion de Ackerman es una funcion que crece muy rapido, su funcional inverso sedefine de forma tal que el crecimiento sea muy lento.

De acuerdo a lo anterior se tiene el siguiente teorema [2, 3]:

Teorema 2.2. El tiempo de ejecucion para una secuencia de O(m) ejecuciones de FIND y O(n)ejecuciones de UNION es O(mα(m,n)). Ademas, O(mα(m,n)) = O(n log∗ n+m) donde log∗ n :=min{i| log log ... log n ≤ 1 El logaritmo se toma i veces}.

Algoritmo:Antes de mostrar el algoritmo general, se discuten los siguientes detalles sobre la inicializacion delos arboles y las listas de adyacencia. En primer lugar se considera I(v) = {(v, w)|{v, w} ∈ E}, elconjunto de arcos adyacentes a v. Aquı es importante tener en cuenta que los elementos de I(v)son parejas ordenadas, es decir que un arco no dirigido {v, w} estara tanto en el conjunto I(v),como en el conjunto I(w). Nuevamente, se inicializa el algoritmo con los vertices aislados siendo lascomponentes conexas (arboles) del bosque inicial. Finalmente, cada arbol del bosque, en cualquieriteracion, consiste de un conjunto de vertices, y de una fila de adyacencia.

19

El algoritmo que se enuncia a continuacion es el mismo explicado al comienzo de este capıtulo.Nuevamente es importante aclarar que el algortimo que dara la compllejidad deseada utiliza estealgoritmo y divide su ejecucion en etapas.

Data: A weighted graph G = (V,E, c).Result: A Minimum Spanning Tree T .for i=1 to n do

INIT(i, i);QINIT(i, I(i));

endT := ∅;while There is more than one tree do

Optional: cleanup step;Choose a tree k;(i, j) := MIN(k);T := T ∪ {(i, j)};x := FIND(j);UNION(x, k);QUNION(x, k);

endAlgorithm 2: Tarjan and Cheriton, MINSPAN Algorithm [2].

Reglas utilizadas:El algoritmo anterior funciona independientemente de la eleccion del arbol k. No obstante paralograr una mayor eficiencia se implementa la siguiente regla de seleccion y procesamiento de losarboles en el algoritmo: inicialmente todos los arboles son vertices aislados, se toman esto arbolesordenados en una lista. En una iteracion del algoritmo se elije el primer arbol T de la lista quese juntara con un arbol T ′. Ambos arboles son eliminados de la lista, y el resultado de unirlos sepone al final.

Las listas de adyacencia para los diferentes arboles se implementan de la siguiente forma: Recor-demos que la lista de adyacencia de un arbol i consiste en todos los arcos adyacentes a este arbol.Dicha lista se puede dividir en b|L|/kc subconjuntos cada uno de tamano k, mas otro subconjuntode tamano menor a k, en donde cada subconjunto esta ordenado de manera no decreciente. Auna lista de adyacencia representada de esta forma se le llama fila de subconjuntos ordenados detamano k.

Ahora, paso por paso se puede analizar la complejidad de la implementacion del algoritmo con lasreglas establecidas. Comencemos con las operaciones sobre las filas de adyacencia:

Notacion: m(i) es el numero de arcos en la fila i. s(i) es el numero de subconjuntos en la fila i,y l(i) es el numero de arcos eliminados de la fila i como resultado de utilizar el algoritmo MIN(i).

Lema 2.3: El tiempo de ejecucion del algoritmo QINIT (i, L) es O(m(i) log k) = O(|L| log k).

Demostracion. Dada la lista L, el algoritmo tiene dos pasos:

1. Dividir la lista en b|L|/kc subconjuntos de tamano k, mas 1 subconjunto de tamano menor ak. A lo sumo se debe recorrer toda la lista una vez, luego el tiempo de ejecucion esta acotadopor O(|L|).

2. Ordenar cada subconjunto. En total hay b|L|/kc + 1 subconjuntos. Cada uno puede ser or-denado en tiempo O(k log k) (utilizando, por ejemplo, el algoritmo por montıculos propuestoen el algoritmo de Kruskal). Luego el tiempo total es:

O((b|L|/kc+ 1)k log k) = O(|L| log k)

20

Ası, el tiempo de ejecucion esta dominado por el paso 2, y el algoritmo se puede implementar enO(|L| log k)

Lema 2.4: El tiempo de ejecucion del algoritmo QUNION(i, j) es O(1).

Demostracion. Dadas dos filas de adyacencia i y j, lo unico que hace el algoritmo QUNION(i, j)es unirlas en una nueva fila de adyacencia. Esto no depende del tamano del problema, luego eltiempo de ejecucion del algoritmo esta acotado por una constante, es decir, es O(1).

Lema 2.5: El tiempo de ejecucion del algoritmo MIN(i) es O(s(i)+l(i)) mas el tiempo de ejecucionde realizar s(i) + l(i)− 1 veces el algoritmo FIND.

Demostracion. El procedimiento para encontrar el arco con peso mınimo en la fila de adyacencia,es tomar el primer arco de cada conjunto. Si este arco no tiene un extremo afuera del arbol T quese esta examinando, entonces debe ser eliminado, y se toma el siguiente arco. Al final se comparael mınimo encontrado de cada conjunto y se toma el mınimo final. Para esto es necesaio analizarO(s(i) + l(i)) arcos. Finalmente, por cada arco analizado, se debe realizar el algoritmo FIND. Noobstante, como el algoritmo tambien elimina el arco mınimo encontrado, el algoritmo realiza FINDs(i) + l(i)− 1 veces.

Antes de mencionar como implementar el algoritmo para obtener la complejidad O(m log log n)deseada, se necesitan una serie de definiciones y resultados [2]. Se supone que G es el grafo conexocon n vertices y m arcos al que se le quiere calcular el AMG:

Recordemos que un arbol generador contiene exactamente n − 1 vertices 3. Ası, el ciclo en elalgoritmo MINSPAN se ejecuta n− 1 veces, por lo que MIN(i) se ejecuta exactamente n− 1 veces,cada vez con un arbol i diferente 4. Ademas, al inicializar el algoritmo se pueden tomar los arboles(vertices aislados) ordenados de tal forma que la i-esima ejecucion de MIN se lleve a cabo con elarbol {i} para i = 1, .., n − 1. Se denota por Ti al arbol que contiene el vertice i justo antes deejecutar MIN(i), de tal forma que Tn es el AMG que retorna el algoritmo.

Definicion 2.3: Para cualquier arbol T que ocurra alguna vez durante el algoritmo, se define elnumero de etapa de T :

Etapa(T ) =

{0, Si T consiste en un unico vertice.min{Etapa(T ′),Etapa(T ′′)}+ 1, Si T proviene de unir los arboles T ′ y T ′′.

Lema 2.6: Para cualquier arbol T , si Etapa(T )= j, entonces T tiene al menos 2j vertices.

Demostracion. La prueba es por induccion (fuerte) en el numero de etapa j.

Si j = 0, entonces entonces T consiste de un unico vertice y contiene al menos 20 = 1 vertices.

Ahora supongamos que cualquier arbol C con Etapa(C)≤ j tiene al menos 2j vertices. Y sea T unarbol con Etapa(T )= j + 1. Por definicion del numero de etapa, T proviene de juntar dos arbolesT1 y T2, de los cuales uno tiene numero de etapa j. Sin perdida de generalidad se puede suponerEtapa(T1)= j. Ademas, por la regla de procesamiento de los arboles, el numero de vertices de T2

es mayor o igual al numero de vertices de T1. Ası, |T | ≥ 2j + 2j = 2 · 2j = 2j+1. Como se querıademostrar.

3Ver notas sobre teorıa de grafos4Utilizando la regla de seleccion de arboles mencionada anteriormente

21

Definicion 2.4: Si se esta utilizando el algoritmo MINSPAN, la Etapa del algoritmo es el mınimonumero de etapa dentro de los arboles que se encuentran en ese momento.

Corolario 2.1: Un arbol T tiene a lo sumo (log n) + 1 etapas. Y por lo tanto el algoritmo tambientiene a lo sumo (log n) + 1 etapas. Aca, n es el numero de vertices del grafo al que se le estacalculando el AMG.

Demostracion. Sea T un arbol que se crea al correr el algoritmo MINSPAN. Si T consiste de soloun vertice, su numero de etapa es 0 ≤ log n+ 1.

Si T proviene de unir los arboles T ′ y T ′′. Entonces, Etapa(T )= min{Etapa(T ′),Etapa(T ′′)}+ 1.Sin perdida de generalidad, supongamos que min{Etapa(T ′),Etapa(T ′′)} se alcanza en T ′ y quemin{Etapa(T ′),Etapa(T ′′)} = j. Por el lema anterior, 2j ≤ |T ′|. No obstante tambien se puedenotar que |T | ≤ n, pues un subgrafo nunca tiene mas vertices que el grafo original. Entonces 2j ≤ ny por lo tanto j ≤ log n. Ası, se concluye:

Etapa(T ) = j + 1 ≤ log n+ 1

Lema 2.7: Al comienzo de la p-esima etapa del algoritmo no hay mas de n/2p filas de adyacencia(una para cada arbol).

Demostracion. Supongamos que en el comienzo de la primera etapa hay x arboles. Sean T1, ..., Txdichos arboles. Como es la p-esima etapa del algoritmo, cada uno de ellos tiene etapa de al menosp, por lo que cada uno tiene al menos 2p vertices (Ver lema arriba). Luego,

x · 2p =

x∑l=1

2p ≤x∑

l=1

|Tl| ≤ n

La ultima desigualdad se tiene, pues los arboles son disyuntos por construccion. Y como sonsubgrafos de G, no puede haber mas de n vertices en total. Entonces x ≤ n/2p.

Lema 2.8: Al comienzo de la p-esima etapa del algoritmo no hay mas de 2m/k+n/2p subconjuntos(contando los subconjuntos de todas las filas).

Demostracion. Sean x el numero de filas de adyacencia (arboles), y el numero de subconjuntos entodas las filas, y El el numero de arcos en la fila l (l = 1, ..., x). Y recordemos que en cada filahay bEl/kc + 1 subconjuntos y que cada arista puede estar en a lo sumo dos filas de adyacencia.Entonces:

y =

x∑l=1

(bEl/kc+ 1)

≤x∑

l=1

((El/k) + 1)

=1

k

x∑l=1

(El + k)

=1

k(

x∑l=1

El + k

x∑l=1

1)

≤ 1

k(2m+ k

n

2p) por que cada arista esta en a lo sumo dos filas de

adyacencia y por el lema anterior.

=2m

k+n

2p

22

Lema 2.9: El tiempo de ejecucion de una etapa j ≥ p del algoritmo, es O(m/k + n/2p + L(j)).Donde L(j) es el numero de arcos eliminados de todas las filas de adyacencia durante la j-esimaetapa.

Demostracion. Durante una etapa se debe analizar la complejidad de realizar el algoritmo MIN.Como se mostro anteriormente, la complejidad de este es O(s(i) + l(i)), donde s(i) es el numero desubconjuntos en la fila i y l(i) es el numero de arcos eliminados. Pero utilizando el lema anterior,se puede acotar el numero de subconjuntos en todas las filas por 2m

k + n2p y si L(j) es el numero de

arcos eliminados de todas las filas de adyacencia, al sumar la realizacion de todos los algoritmosMIN durante la j-esima etapa, se obtiene la complejidad:

O(m/k + n/2p + L(j))

Hasta aca no se ha considerado la complejidad de la realizacion de a lo sumo m/k+n/2p +L(j)−1veces el algoritmo FIND, no obstante, por el Teorema 2, el tiempo de ejecucion de este numero dealgoritmos FIND es:

O(m/k + n/2p + L(j)− 1)

Ası, se puede concluir que el tiempo de ejecucion de una etapa j del algoritmo esta dominada porla realizacion de los algoritmos MIN, y por lo tanto el tiempo de ejecucion total es O(m/k+n/2p +L(j)).

Lema 2.10: El tiempo de ejecucion de inicializar5, y ejecutar de la p-esima a la q-esima etapa es:O((m/k + n/2p)(q − p) +m).

Demostracion. En primer lugar, notamos que la inicializacion de las filas de adyacencia es O(m),pues solo se requiere recorrer el conjunto de arcos una vez, dado que por ahora no se estan orga-nizando los conjuntos.

Ahora, por el lema anterior, el tiempo de ejecucion de las etapas p y q es respectivamente: O(m/k+n/2p + L(p)) y O(m/k + n/2p + L(q)). En el peor de los casos, se puede suponer que tanto L(p)como L(q) son m. Luego la realizacion de las (q − p) etapas toma tiempo:

O([m/k + n/2p](q − p) + 2m+m) = O([m/k + n/2p](q − p) +m)

A partir de todos los resultados anteriores, Tarjan y Cheriton [2] proponen finalmente el siguienteprocedimiento para encontrar un AMG:

Algoritmo de Tarjan y Cheriton:

1. Inicializar todas las filas de adyacencia como conjuntos no organizados.

2. Correr el algoritmo MINSPAN hasta la etapa blog log nc.

3. Inicializar todas las filas de adyacencia como listas de subconjuntos ordenados de tamanok = blog nc.

4. Terminar de correr el algoritmo MINSPAN.

Teorema 2.3. El tiempo de ejecucion del algortimo de Tarjan y Cheriton es O(m log log n).

5Aquı, se supone que la incializacion de las filas de adyacencia se hace con conjuntos no organizados.

23

Demostracion. Para demostrar que el algoritmo tiene este tiempo de ejecucion, se analiza la com-plejidad de los diferentes pasos:

Para los pasos 1 y 2: Cuando los conjuntos no estan ordenados, es equivalente a tomar k = 1. Y eneste caso, p = 0 y q = blog log nc. Entonces por el lema anterior, la complejidad de estos pasos es:

O([m+ n]blog log nc+ n) = O(m log log n)

El paso 3 toma tiempo O(m log log n) (Ver tiempo de inicializacion de QINIT con k = blog nc).Finalmente, al recordar que el algoritmo tiene a lo sumo log n+1 etapas, utilizando el lema anteriorse obtiene el tiempo de ejecucion del paso 4 (k = blog nc, p = blog log nc, q = log n+ 1):

O([m

blog nc+

n

2log log n](log n+ 1− log log n)) = O((

m

log n+

n

log n)(log n)) = O(m+ n) = O(m)

Como todos los pasos toman tiempo a lo sumo O(m log log n). El tiempo de ejecucion total de larutina propuesta es: O(m log log n).

Intuitivamente el algoritmo propuesto por Tarjan y Cheriton funciona eficientemente por las si-guientes razones: Ordenar todos los arcos desde el comienzo, como en el algoritmo de Kruskal, esmuy ineficiente debido a que en las primeras etapas del algoritmo es mas facil aceptar arcos, pueshasta ahora se esta comenzando a construir el AMG. Por el contrario, a medida que se avanza enel algoritmo, es mas difıcil encontrar arcos para aceptar, razon por la cual es eficiente ordenar lasfilas de adyacencia para elegir arcos mas rapido.

Implementacion del Algoritmo:

El algoritmo propuesto por Tarjan y Cheriton se implemento con el fin de obtener algunos resul-tados que permitieran ilustrar que el algoritmo funciona con la complejidad teorica demostrada.Los detalles de la implementacion son los siguientes:

Figura 2.2: Implementacion del algoritmo de Tarjan y Cheriton

Aca es importante comentar que se usan dos procedimientos distintos MINSPAN y MINSPAN2,pues como las filas de adyacencia cambian durante el algoritmo (primero son conjuntos no ordena-dos, y luego se utilizan subconjuntos de tamano blog nc), se deben utilizar diferentes estructuras

24

de datos para representar cada paso del algoritmo. Ası, los algoritmos MIN y QUNION cambiansegun la etapa en la que se encuentra el algoritmo. Los demas detalles de la implementacion son:

25

Resultados:

La implementacion anterior fue puesta a prueba para verificar experimentalmente que el algorit-mo funciona con la complejidad teorica demostrada. Se realizo el mismo experimento que en elalgoritmo de Kruskal. Mas aun, en esta oportunidad se incluyen resultados de ambos algoritmos.

Con la implementacion del algoritmo de Tarjan y Cheriton se incluyeron los siguientes resultados:

26

Graph Constante Calculada

K10 19.96K100 18.77K200 18.97K300 19.17K500 18.57

Por otro lado, con el algoritmo de Kruskal, se obtuvo:

Graph Constante Calculada

K10 7.96K100 6.54K200 6.41K300 6.29K500 6.21

En ambos casos se evidencia que el tiempo de ejecucion del algoritmo es proporcional a m log ny a m log log n para el algoritmo de Kruskal y Tarjan respectivamente. Aunque la constante deproporcionalidad del algoritmo de Tarjan y Cherition sea mas grande, esto no quiere decir que elalgoritmo sea menos rapido, pues asintoticamente, el tiempo de ejecucion va a estar dominado porel termino m log log n y no por la constante.

27

Capıtulo 3

Grafos Densos y Planares

Recordemos que en el algoritmo general propuesto por Tarjan y Cheriton [2] para encontrar elarbol mınimo generador de un grafo se propone el siguiente paso opcional, que puede realizarse encualquier iteracion.

Paso Tres: Para todos los arboles, elimine los arcos no seleccionados cuyos dos extremos seanincidentes al mismo arbol. Ademas, para cada par de arboles diferentes conectados por arcos noseleccionados, elimine todos los arcos, menos el de menor peso.

Al implementar dicho algoritmo teniendo en cuenta este paso, llamado paso de limpieza, es posibleobtener tiempo de ejecucion lineal para grafos con ciertas propiedades. En esta parte se demuestracomo implementar un algoritmo para resolver el problema en tiempo O(n) y O(m) para grafosplanares y densos respectivamente.

Ordenamiento Lexicografico de Aristas:

Para implementar el paso de limpieza, es necesario estudiar la siguiente forma de ordenar unconjunto de arcos de forma lexicografica[9].

Para comenzar, se considera una forma para ordenar numeros enteros. Si a1, a2, ..., am son mnumeros enteros con valores entre 0 y N − 1, es decir 0 ≤ ai ≤ N − 1 para todo i = 1, ...,mentonces estos numeros se pueden ordenar de la siguiente forma:

1. Inicializar N listas vacıas. Una para cada numero entero entre 0 y N .

2. Recorrer los enteros a1, a2, ..., am, y ubicar el numero ai en la ai-esima lista.

3. Unir el contenido de todas las listas para obtener la secuencia de enteros ordenada.

Note que este algoritmo solo funciona para ordenar numeros enteros. Ademas, el algoritmo conduceal siguiente lema:

Lema 3.1: Si N = O(m), los enteros a1, a2, ..., am se pueden ordenar en tiempo O(m).

Demostracion. El primer paso toma tiempo O(N). Para el segundo paso, solo hay que recorrer losm enteros e insertarlos en cada lista. Para insertar un elemento en una lista, solo hay que hacerreferencia a la lista que tiene el valor de dicho numero, luego esto se puede hacer en tiempo O(1),e insertar todos los numeros en tiempo O(m). Finalmente las N listas se pueden unir en tiempoO(N) (hay que recorrerlas todas).

El tiempo total de ejecucion es O(N) +O(m) +O(N) = O(N). Finalmente, si N = O(m) entoncesO(N) = O(m).

28

Ahora se introduce el orden lexicografico de tuplas:

Definicion 3.1: Dadas dos tuplas (a1, a2) y (b1, b2). El orden lexicografico ≤lex se define: (a1, a2) ≤lex

(b1, b2) si a1 < b1 o si (a1 = b1 y a2 ≤ b2).

Entonces, es posible ordenar tuplas de numeros enteros con el orden lexicografico, utilizando dospasadas del algoritmo de ordenamiento anterior:

Algoritmo de ordenamiento lexicografico de tuplas: Sean (a11, a12), ..., (am1, am2) m tuplasde numeros enteros entre 0 y N − 1.

1. En la primera pasada, ordene las tuplas de acuerdo a la segunda componente.

2. En la segunda pasada, ordene la lista resultante del paso 1 de acuerdo a la primera compo-nente.

La secuencia resultante esta ordenada lexicograficamente. Mas aun, si N = O(m), el ordenamientotoma tiempo O(2m) = O(m).

Paso de Limpieza:

Ahora se puede explicar como implementar el paso de limpieza propuesto [2]. Recordemos que enuna iteracion intermedia del algoritmo de Tarjan, se cuenta con un bosque, y que cada componenteconexa se puede representar con un conjunto de vertices. Se considera el conjunto E de las m aristasdel grafo. Cada arista vw se puede remplazar por una arista v′w′ en donde v′ y w′ corresponden alnumero del conjunto en el que se encuentran los vertices v y w respectivamente. Luego se puedenordenar las aristas v′w′ lexicograficamente. Finalmente, de la lista resultante, eliminar todos losarcos v′w′ tales que v′ = w′ (Generan ciclos en el mismo conjunto), y quedarse con una unica copia(la de menor peso) de las aristas v′w′ con v′ 6= w′.

Lema 3.2: El procedimiento descrito anteriormente para el paso de limpieza se puede implementaren tiempo O(m).

Demostracion. Vamos a dividir el procedimiento en tres pasos. Siempre se tiene en cuenta que encualquier iteracion la lista de aristas tiene a lo sumo m elementos.

Paso 1: En el primer paso se debe recorrer una vez la lista de arcos, para modificarlos en los arcosque consisten en los numeros del conjunto en el que esta cada vertice. Esto toma tiempo O(m).

Paso 2: Organizar los arcos resultantes en el orden lexicografico toma tiempo O(m).

Paso 3: Dado que los arcos estan en orden lexicografico. Para eliminar las aristas necesarias soloes necesario recorrer la lista una vez. Luego este proceso tambien toma tiempo O(m).

En conclusion todo el proceso toma tiempo O(3m) = O(m).

Debido al lema anterior, es posible implementar el algoritmo de Tarjan, incluyendo el paso delimpieza en cada etapa, en tiempo O(m log n). Al recordar que la realizacion del algoritmo tomaa lo sumo log n + 1 etapas, el tiempo de ejecucion total para todos los pasos de limpieza esO(m·(log n+1)) = O(m log n). Dado que el resto de pasos se pueden implementar en O(m log logn),como se mostro antes, el tiempo de ejecucion del algoritmo estarıa dominado por los pasos delimpieza y por lo tanto serıa O(m log n). Ası que en general, el paso de limpieza no produce buenosresultados. No obstante, hay una forma de utilizarlo, de forma que se obtengan resultados rapidospara grafos denso y planares:

29

Algoritmo:

Finalmente se puede describir el siguiente algoritmo que permite encontrar un arbol mınimo gene-rador de un grafo. Este sera el algoritmo que da el tiempo de ejecucion deseado para grafos densosy planares.

Algoritmo: Para el grafo conexo G = (V,E) con n vertices y m aristas, realizar el paso delimpieza n− 1 veces. En cada iteracion, despues del paso de limpieza, aceptar en el arbol mınimogenerador T un arco de la lista actual de peso mınimo. Note que despues del paso de limpieza,todos los arcos de la lista actual conectan arboles diferentes.Nota: Al implementar este algoritmo, es muy importante tener en cuenta que al hacer la sustituciondel arco vw por v′w′ se debe guardar siempre referencia al arco original vw. Dicho arco, sera elincluido en el arbol mınimo generador.

Para entender mejor como funciona este algoritmo se cuenta con el siguiente ejemplo. Nuevamente,se considera inicialmente el siguiente grafo:

Y se muestran las iteraciones que resultan de aplicar el algoritmo porpuesto:

Iteracion 1:

T = ∅Lista actual: {(1, 2, 5), (2, 4, 2), (3, 4, 8), (1, 3, 7), (1,4,4), (2, 3, 9)}Lista numero de conjuntos: {(1, 2, 5), (2, 4, 2), (3, 4, 8), (1, 3, 7), (1,4,4), (2, 3, 9)}Lista ordenada: {(1, 2, 5), (1, 3, 7), (1, 4, 4), (2, 3, 9), (2, 4, 2), (3, 4, 8)}No hay eliminaciones.Se acepta (2, 4, 2) y se elimina de la lista.

Iteracion 2:

30

T = {(2, 4, 2)}. Los vertices 4 y 2 forman el conjunto numero 2.Lista actual: {(1, 2, 5), (1, 3, 7), (1, 4, 4), (2, 3, 9), (3, 4, 8)}Lista numero de conjuntos: {(1, 2, 5), (1, 3, 7), (1, 2, 4)↔ (1, 4, 4), (2, 3, 9), (3, 2, 8)↔ (3, 4, 8)}La notacion (1, 2, 4) ↔ (1, 4, 4) se utiliza para indicar que el arco actualizado (1, 2, 4) corres-

ponde al arco original (1, 4, 4).Lista ordenada: (1, 2, 5), (1, 2, 4)↔ (1, 4, 4), (1, 3, 7), (2, 3, 9), (3, 2, 8)↔ (3, 4, 8)Se elimina (1, 2, 5).Se acepta (1, 2, 4) se elimina de la lista, y se anade a T el arco original (1, 4, 4).

Iteracion 3:

T = {(2, 4, 2), (1, 4, 4)}. Los vertices 1, 2 y 4 forman el conjunto numero 1. (Por convencion setoma como numero del conjunto el vertice mas pequeno).

Lista actual: {(1, 3, 7), (2, 3, 9), (3, 2, 8)↔ (3, 4, 8)}Lista numero de conjuntos: {(1, 3, 7), (1, 3, 9), (1, 3, 8)↔ (3, 4, 8)}Lista ordenada: {(1, 3, 7), (1, 3, 9), (1, 3, 8)↔ (3, 4, 8)}Se eliminan (1, 3, 9) y (1, 3, 8).Se acepta (1, 3, 7) y se elimina de la lista.

Iteracion 4:

T = {(2, 4, 2), (1, 4, 4), (1, 3, 7)}

31

Lista actual: ∅Fin del algoritmo

Resultado: Se obtiene el AMG T = {(2, 4, 2), (1, 4, 4), (1, 3, 7)} con peso total de 13.

Finalmente se demuestra que el ultimo algoritmo enunciado se puede implementar en tiempo O(m)y O(n) para grafos densos y planares respectivamente.

Lema 3.3: Al aplicar el algoritmo anterior, luego de la j-esima etapa, hay a lo sumo n/2j+1 arbolesen el grafo que esta guardando el AMG que retorna el algoritmo.

Demostracion. La prueba formal se hace por induccion en el numero de etapa j.

Al comienzo del algoritmo, cuando j = 0 hay n arboles (uno para cada vertice). Despues de laetapa 0, cada arbol debe haber sido juntado con otro. Luego el numero de arboles se reduce almenos a la mitad, y se obtiene n ≤ n/2.

Supongamos que en una etapa j hay x arboles y x ≤ n/2j+1. Es decir que entre esos x arboles,hay al menos uno cuyo numero de etapa es j. En el peor de los casos todo ellos tienen el mismonumero de etapa j. Para alcanzar la etapa j + 1, cada uno de esos arboles se debe unir conotro. Es decir que nuevamente el numero de arboles se reduce a la mitad: si y es el numerode arboles en la (j + 1)-esima etapa, entonces utilizando la hipotesis de induccion se obtieney ≤ x/2 ≤ n/(2j+1 · 2) = n/2(j+1)+1.

Corolario 3.1: Al aplicar el algoritmo anterior, luego de la j-esima etapa, hay a lo sumo n/2j+1

vertices nuevos 1.

Demostracion. El resultado se obtiene directamente del lema, pues cada arbol se representa me-diante un unico vertice (El numero del conjunto en el cual se encuentra). Note que esto es equiva-lente a contraer todos los vertices de un arbol a un unico vertice.

Corolario 3.2: Al aplicar el algoritmo anterior, luego del paso de limpieza realizado despues dela j-esima etapa, hay a lo sumo (n/2j+1)2 aristas.

Demostracion. Por el corolario 1, luego de la j-esima etapa hay a lo sumo n/2j+1 vertices. Despuesdel paso de limpieza se conserva a lo sumo una arista entre cualquier par de arboles (verticesnuevos). Luego se obtiene a lo sumo un grafo simple completo en n/2j+1 vertices cuyo numero dearistas esta acotado superiormente por (n/2j+1)2.

Consideramos ahora las siguientes definiciones y resultados sobre grafos densos y planares comoen [10]:

Definicion 3.2: Suponga que {Gn} es una familia de grafos donde cada Gn tiene n vertices, yel numero m de aristas se puede expresar como una funcion en terminos de n. Es decir m = f(n).La familia se llama densa, si n2 = O(f(n)). Un grafo es denso si pertenece a una familia de grafosdensa.

1Se llaman vertices nuevos a los vertices v′ y w′ obtenidos luego de cambiar los vertices originales, por el numerodel conjunto en el cual se encuentran.

32

Intuitivamente, un grafo es denso, si el numero de aristas que tiene es al menos de orden cuadraticocon respecto a su numero de vertices. Para aclarar esta definicion se cuenta con el siguiente ejemplo:

Ejemplo: Sea {Kn} la familia de grafos completos. Esta familia es densa pues cada Kn tiene nvertices y m aristas donde:

m = f(n) =

(n

2

)=n2 − n

2

Y entonces,

n2 = 2m+ n = O(m)

Definicion 3.3: Un grafo es planar si se puede dibujar en el plano sin que sus arcos se intersectenen puntos diferentes a los vertices. Mas formalmente:

G = (V,E) es planar si existe una sumersion de G en R2 tal que:

1. V ⊆ R2

2. El interior de un arco no contiene vertices ni puntos de otros arcos.

Para probar la complejidad del algoritmo en grafos planares se utiliza el siguiente resultado [10]:

Teorema 3.1. Si n ≥ 3, un grafo planar con n vertices tiene a lo sumo 3n− 6 arcos.

Finalmente se enuncian los resultados de importancia para este capıtulo:

Teorema 3.2. La complejidad del algoritmo propuesto es O(m) para grafos densos.

Demostracion. Recordemos que el algoritmo consiste en realizar el paso de limpieza n − 1 vecesen la lista actual de arcos de una iteracion. El tamano de esta lista cambia dado que el pasode limpieza elimina aristas. Sea m(i) el numero de arcos que tiene la lista en el i-esimo paso delimpieza. Luego el i-esimo paso de limpieza toma tiempo O(m(i)). Y entonces la ejecucion de todo

el algoritmo toma tiempo O(∑n−1

i=1 m(i)). Ahora, utilizando el corolario 2:

n−1∑i=1

m(i) ≤∞∑j=0

(n/2j)2 = n2∞∑j=0

1/4j =3

4n2 = O(n2)

Si el grafo es denso entonces n2 = O(m) y el tiempo de ejecucion serıa:

O(

n−1∑i=1

m(i)) = O(O(m)) = O(m)

Teorema 3.3. La complejidad del algoritmo propuesto es O(n) para grafos planares.

Demostracion. Se sigue la misma idea que en la prueba del teorema anterior, pero esta vez, comoel grafo es planar, se tiene m ≤ 3n − 6. Mas aun, como el grafo es planar, despues del paso delimpieza, los grafos resultantes tambien son planares. Y utilizando el corolario 1, en una etapa jdel algoritmo hay a lo sumo n/2j+1 vertices. Se obtiene:

n−1∑i=1

m(i) ≤∞∑j=0

(3 · (n/2j)− 6) ≤∞∑j=0

(3 · (n/2j)) = 3n

∞∑j=0

1/2j = 6n

Finalmente el tiempo de ejecucion total es:

O(

n−1∑i=1

m(i)) = O(6n) = O(n)

33

Capıtulo 4

Medidas de Similaridad entreSuperficies

En este capıtulo se describe una aplicacion en la que es necesario resolver el problema de encontrarel arbol mınimo generador de un grafo. La idea es mostrar casos en los que se han implementadolos algoritmos mostrados en este trabajo. Mas aun, se quiere justificar la importancia de poderresolver el problema en orden O(n) en grafos planares, debido a que la reduccion de la complejidadde O(m log n) (Algoritmo de Kruskal) a O(n) (Algoritmo de Tarjan para grafos planares) podrıaparecer insignificativa.

Una necesidad que aparece en diversos problemas, por ejemplo el de identificacion biometrica, escalcular medidas de similaridad entre superficies representadas como nubes de puntos. El problemageneral, es el de programar algoritmos para analizar, comparar y clasificar superficies. Para poneruna situacion concreta, se puede tener el problema de comparar dos modelos de una cara obtenidosa partir de metodos de escaneo en 3D, actualmente desarrollados [11].

Veamos un enunciado detallado del problema:

Definicion 4.1: Una malla irregular en el plano es un subconjunto finito de puntos en R2. Sedenotara G = {(xi, yi)|i = 1...N}. En el contexto de este problema se debe elegir N ≥ 3.

Utilizando la definicion anterior, se decide representar una superficie como una nube de puntos,esto es, una funcion F : G→ R. Note que el dominio de la funcion es discreto. Mas aun, F es unafuncion en dos variables, y asume valores reales. La informacion de dicha representacion se puedeobtener, por ejemplo, con metodos de escaneo 3D.

Nota: Una funcion F : G → R definida sobre una malla irregular G se puede representar comouna secuencia finita de puntos, pues como el dominio es discreto, se pueden especificar unicamentelos valores que asume la funcion en la malla G. Es decir, F = (f1, ..., fN ). Siendo N el numero depuntos de la malla y f i := F (xi, yi) para i = 1, ..., N .

Enunciado del Problema[11]: Dadas dos nubes de puntos (superficies) F1 = (f11 , ..., f

N11 ) y

F2 = (f12 , ..., f

N22 ) definidas en diferentes mallas irregulares1 G1 y G2 con N1 y N2 puntos respec-

tivamente, se quiere introducir una medida de similaridad para estas superficies (determinar quetan parecidas son) e implementar un algoritmo para calcularla.

A continuacion se presentan posibles medidas de similaridad que se pueden utilizar para resolver elproblema. Se tienen en cuenta las siguientes consideraciones y su notacion [11]: Dadas F1 y F2, comoantes, se consideran funciones continuas F1 y F2 tales que F1|G1

= F1 y F2|G2= F2. Por ejemplo,

F1 y F2 pueden ser interpolaciones lineales a trozos de las funciones F1 y F2 respectivamente.

1Note que los puntos y la cantidad de estos pueden ser diferentes en cada malla.

34

Considereamos la siguiente definicion de triangulacion:Definicion 4.2: Dada una malla G = {(xi, yi)|i = 1...N} ⊆ R2, una triangulacion de G, es unacoleccion T de triangulos R2, que satisfacen:

1. Propiedad de la Union: ∪T∈T T = conv(G). Donde conv(G) es la clausura convexa de lospuntos de G.

2. Propiedad de la interseccion: La interseccion de cualquier par de triangulos de T es vacıa,un punto, o un lado de ambos triagnulos.

3. La triangulacion es completa: cada punto de G es un vertice de algun triangulo de T .

Dada una malla G, existe una triangulacion de G, que es conocida en la bibliografıa, y de especialimportancia para calcular medidas de similaridad entre superficies. A saber, la triangulacion deDelaunay [12]:

Definicion 4.3: Dada una triangulacion T de una malla G, y dos puntos p, q ∈ G que forman unaarista pq de la triangulacion, la arista pq se llama localmente Delaunay si la suma de los angulosopuestos a pq es menor o igual a 180 grados (ver figura abajo). La triangulacion es de Delaunay sitodas sus aristas son localmente Delaunay.

Figura 4.1: La arista pq es localmente Delaunay. Imagen tomada de [12].

El siguiente es un ejemplo de una triangulacion de Delaunay:

Figura 4.2: Una Triangulacion de Delaunay. Imagen tomada de [12].

El circulo en la imagen, permite ejemplificar una propiedad que satisfacen las triangulaciones deDelaunay: Ningun punto de la triangulacion se ubica en el interior del cırculo circumscrito de untriangulo de la triangulacion [12].

Tambien se cuenta con la siguiente caracterizacion para triangulaciones de Delaunay[12]:

Lema 4.1: Una triangulacion de Delaunay de puntos en R2 es una solucion optima del problemade encontrar una triangulacion que maximice el angulo mas pequeno de la triangulacion.

35

Notamos que debido a la caracterizacion anterior, las triangulaciones de Delaunay balancean elarea de los triangulos, evitando los de area pequena. Dicha triangulacion se utiliza para construirlas interpolaciones lineales F1 y F2. Las razones de esta eleccion se explicaran mas adelante. Masaun, el lema anterior garantiza la existencia de una triangulacion de Delaunay para una malla Gcon tres o mas puntos.

Se considera la triangulacion de Delaunay TD de los puntos G1 ∪ G2. Y se denota ∆ABC a untriangulo de TD. Luego se pueden proponer las siguientes medidas de disimilitud [11]:

1. Primera medida de disimilitud:

ρd(F1, F2) :=∑

∆ABC∈TD

V (A,B,C, F1, F2)

donde,

V (A,B,C, F1, F2) :=

∫∫∆ABC

|F1(x, y)− F2(x, y)|µ(x, y)dxdy

Y µ(x, y) es una funcion que se puede utilizar para anadir mas peso a determinadas partes deuna superficie al momento de medir su similaridad. Note que la medida ρd(F1, F2) provienede calcular la suma de la diferencia de volumenes de distintas superficies.

2. Tambien se puede proponer:

ρ′d(F1, F2) :=∑

(xi,yi)∈G1∪G2

|F1(xi, yi)− F2(xi, yi)|

A partir de las anteriores medidas de disimilitud se propone la siguiente medida de similitud :

ρs :=

{1/ρd, ρd 6= 0

1, ρd = 0

A primera vista, las medidas de similaridad ya estan listas. No obstante, al momento de calcularlassurge un problema: las funciones F1 y F2 podrıan tener dominios diferentes. Mas aun, aunque lasmedidas se calculan utilizando las interpolaciones lineales F1 y F2, persiste el problema de quedado un punto (x, y) en la malla G1, se debe saber en que triangulo de la triangulacion de G2 selocaliza este punto para poder calcular F2(x, y), que es el valor en (x, y) de la interpolacion linealde la funcion F2 con respecto a los puntos G2. Es decir, se tiene un problema de localizacion de lospuntos de la malla G1 en la triangulacion de G2 y viceversa.

Teniendo en cuenta lo anterior, se pueden enunciar los pasos generales del algoritmo que permitesolucionar el problema mencionado y calcular las medidas de similaridad. Se describen principal-mente los paso de interes para este proyecto: donde se utiliza la construccion de arboles generadoresde peso mınimo.

Algoritmo [11]:

1. Construir las triangulaciones de Delaunay T 1D y T 2

D de las mallas G1 y G2 respectivamente.

2. Resolver el problema de localizacion de los puntos de cada malla en la triangulacion de laotra.

3. Una vez se han localizado los puntos de una malla en la otra triangulacion, se puede calcularel valor de la interpolacion de un punto en la otra malla.

4. Construir la triangulacion TD de la malla G1∪G2. Dicha triangulacion se llama triangulaciongeneral de Delaunay.

36

5. Comparar los valores de las funciones en cada triangulo de TD para poder calcular la medidaρd.

Los pasos 1 a 3 bastan para calcular la medida ρ′d, mientras que los pasos 1 a 5 se deben realizarpara calcular ρd.

A continuacion se enuncia una definicion y un resultado importante para este proyecto [12]. Pos-teriormente se explica la relacion de los arboles generadores con el algoritmo enunciado, y laimportancia del resultado.

Definicion 4.4: Dada una malla de puntos G en R2, el arbol mınimo generador euclideano dedicha malla es el AMG del grafo completo cuyos vertices son los puntos de G, y el peso de un arcoes la distancia euclideana entre los puntos que lo componen.

Teorema 4.1. Dada una malla de puntos G en R2, todo arbol mınimo generador euclideano dedicha malla es un subgrafo de una triangulacion de Delaunay de la malla G.

Demostracion. Sea G = {p1, ..., p2}. Se considera el algoritmo de Prim2 para calcular el AMGde G. En una iteracion intermedia del algoritmo, se elige la arista (s, u) de peso (en este casodistancia) mınimo que conecta los conjuntos T y G \ T .

Con esta configuracion, la interseccion de los cırculos de radio ||s−u|| centrados en s y u respecti-vamente, no contienen vertices de G, pues en caso contrario, no se cumplirıa que (s, u) es la aristade menor distancia conectando los conjuntos T y G\T . Como se muestra en la figura 4.3, donde lostres puntos de la izquierda hacen parte de T , y los de la derecha de G \ T . Ası, el cırculo centradoen q = s+u

2 (El punto q no es un vertice del grafo G. Solo se usa para denotar el punto medio dela arsita que conecta los puntos s y u) de radio ||q− s|| = ||q− u|| tampoco contiene puntos de G,lo que quiere decir que el arco (s, u) es localmente delaunay

Figura 4.3: La arista (s, u) es localmente delaunay.

Por esta discusion, vemos que cualquier arista que se acepta en un MST para G es localmenteDelaunay, y por lo tanto esta contenida en una triangulacion de dicho tipo.

Finalmente, se lleva a cabo una descripcion mas elaborada del paso 2 (paso de localizacion) delalgoritmo propuesto. La idea es la siguiente: dado que en el paso 1 ya se han calculado las triangu-laciones T 1

D y T 2D, se pueden hallar los arboles mınimos generadores euclideanos para cada malla

G1 y G2. Note que al tener las triangulaciones T 1D y T 2

D que son grafos planares, y teniendo encuenta el teorema anterior, los AMG se pueden calcular a partir de las triangulaciones en tiempoO(N1) y O(N2), para las mallas G1 y G2 respectivamente.

Posteriormente se utilizan los AMG obtenidos de cada triangulacion para resolver el problema delocalizacion. Tomemos los puntos de la malla G1. Queremos localizarlos en T 2

D. Se toma un punto

2Recordamos que este no es mas que un caso particular del algoritmo de Tarjan y Cheriton en el que la elecciondel arbol T es siempre la misma.

37

cualquiera de G1, y supongamos que se conoce la ubicacion de ese punto inicial. El siguiente paso,es recorrer todas las aristas del AMG de G1 identificando las transiciones que se dan entre lostriangulos de T 2

D. Y al llegar a cada vertice se guarda la ubicacion de este. Dado que el AMGconecta todos los puntos de G1, se puede conocer la ubicacion de todos los puntos. Para conocerla ubicacion del punto inicial, se parte de un punto conocido en T 2

D y se traza el segmento de rectade este puno al punto inicial y se realiza el mismo procedimiento de ubicacion. Finalmente se hacela aclaracion de que un punto no necesariamente se encuentra ubicado dentro de la triangulacionT 2D. En dicho caso se considera el punto perteneciente a un triangulo artificial fuera de T 2

D, y se lepuede dar el valor de cero en la interpolacion. El problema de localizacion de G2 en T 1

D se solucionade forma analoga [11].

Las siguientes imagenes ayudan a entender este procedimiento:

Figura 4.4: Localizacion del punto Q en una triangulacion, partiendo del punto M y utilizando elsegmento MQ. Imagen tomada de [11].

Figura 4.5: Localizacion de una malla de puntos en una triangulacion utilizando un AMG.Imagentomada de [11].

Finalmente, se cita el experimento computacional realizado en [11] sobre la contruccion de AMGa partir de la triangulacion de Delaunay de una malla G con N puntos. El AMG fue construidoimplementando el algoritmo de Tarjan y Cheriton para grafos planares, estudiado anteriormenteen este proyecto, cuya complejidad teorica es O(N). Ellos obtuvieron los siguientes resultados:

38

Se pueden comentar los siguientes aspectos de los resultados anteriores. En primer lugar, se puedenotar que la cantidad de puntos N varıa entre 10,000 y 100,000. Esto muestra que en la practica,para instancias con determinado tamano, es importante identificar las propiedades de los grafosque representan dichas instancias y encontrar algoritmos con menor complejidad computacionalque ayuden a resolver el problema de una forma mas eficiente. La columna N/t sirve para verificarque el algoritmo implementado en [11] corre con la complejidad teorica O(N).

39

Conclusiones:

En este proyecto se estudiaron los siguientes resultados sobre algoritmos que permiten solucionarel problema de encontrar el arbol generador de peso mınimo de un grafo:

El algoritmo de Kurskal, que puede ser implementado en tiempo O(m log n).

Un algoritmo propuesto por Tarjan y Cheriton, cuyo tiempo de ejecucion es O(m log log n).

Otro algoritmo por Tarjan y Cheriton que corre en tiempo O(m) y O(n) para grafos densosy planares respectivamente.

Las implementaciones realizadas de los primeros dos algoritmos permitieron realizar experimentosque ayudaron a ilustrar que la complejidad computacional de los algoritmos es la demostradateoricamente. En ambos casos se obtuvieron resultados satisfactorios.

Ademas, se planteo una aplicacion en la que surge el problema de encontrar arboles mınimosgeneradores de grafos. Dicha aplicacion es la de calcular medidas de similaridad de superficiesrepresentadas como nubes de puntos. Experimentos realizados en esta aplicacion implementaron elalgoritmo de Tarjan y Cheriton para grafos planares. Los resultados mostrados en ese caso ayudana ver la importancia de encontrar algoritmos mas rapidos para resolver el problema.

Finalmente, es importante mencionar que el problema estudiado en este proyecto es un ejemplode un caso en el que se ha intentado reducir al maximo la complejidad de un problema. El mejorresultado conocido, se debe a Bernard Chazelle, quien propone un algoritmo que corre en tiempoO(mα(m,n)) donde α(m,n) es el funcional inverso de la funcion de Ackerman [13].

40

Apendice A

Teorıa de Grafos

Definiciones Basicas

Estas notas son un resumen de los conceptos necesarios sobre Teorıa de Grafos para entender elproyecto de grado. Contiene las definiciones y resultados mas importantes y la notacion que seutilizara cuando se habla sobre grafos. La referencia para estas notas es [14].

Se denota por [A]2 al conjunto de todos los 2-subconjuntos, es decir los subconjuntos de A quetienen exactamente 2 elementos.

Un grafo (no dirigido)1 es una pareja G = (V,E) de conjuntos que satisfacen E ⊆ [V ]2. El conjuntoV es el conjunto de vertices, mientras que el conjunto E es el conjunto de arcos o de aristas. Elarco {x, y} ∈ E se denota tambien xy. El orden del grafo se denota |G| y es el numero de verticesdel grafo.

Dos vertices x, y de un grafo G son adyacentes o vecinos si xy es un arco de G. Dado un arco xyse dice que el arco es incidente a los vertices x y y. Se define el conjunto de arcos incidentes a unvertice v como: I(v) := {{v, w}|{v, w} ∈ E}. El grado de un vertice es d(v) := |I(v)|.

Definicion A1: Sea G un grafo tal que todos sus vertices son adyacentes por pares. Entonces elgrafo se llama completo. Un grafo completo en n vertices se denota Kn.

Sean G = (V,E) y G′ = (V ′, E′) grafos.

Definicion A2: Se dice que los grafos son isomorfos si existe una biyeccion φ : V → V ′ quesatisface xy ∈ E si y solo si φ(x)φ(y) ∈ E′ para todas las elecciones de x y y.

Se define la union de dos grafos G y G′ como G ∪G′ := (V ∪ V ′, E ∪E′). Y su interseccion comoG ∩G′ := (V ∩ V ′, E ∩ E′).

Definicion A3: Si V ′ ⊆ V y E′ ⊆ E, se dice que G′ es un subgrafo de G, se escribe G′ ⊆ G.

Definicion A4: Si G′ ⊆ G y G′ contiene todos los arcos xy ∈ E tales que x,y ∈ V ′. Entonces sedice que G′ es un subgrafo inducido de G. Igualmente se dice que V ′ genera G′ en G. En el casoespecial en el que V = V ′ se dice que G′ es un subgrafo generador de G. Ademas, si U ⊆ V , sedenota G[U ] al grafo en los vertices U con las aristas de G que tienen ambos extremos in U .

1En este proyecto se consideran unicamente grafos no dirigidos al menos que se diga lo contrario.

41

Caminos y Conexidad

Definicion A5: Un camino es un grafo P = (V,E) cuyos conjuntos de vertices y arcos tienenla forma V = {x0, x1, ., xk} y E = {x0x1, x1x0, ..., xk−1xk}, donde todos los xi son distintos. Losvertices x0 y xk son los extremos del camino. Tambien se puede llamar a P un camino entre losvertices x0 y xk. |E| es la longitud del camino. Un camino de longitud k se denota P k. Si se hace laexcepcion de que los extremos sean iguales, el grafo se convierte en un ciclo. Un ciclo de longitudk se llama k-ciclo y se denota Ck.

Definicion A6: Un grafo G no vacıo es conexo si existe un camino P ⊆ G entre cualquier par devertices. Una componente conexa, o simplemente componente, del grafo es un subgrafo maximal2

conexo.

Arboles y Bosques

Definicion A7: Un grafo que no contiene ciclos se llama bosque. Si ademas es conexo se llamaarbol. Note que las componentes conexas de un bosque son arboles.

Los siguientes resultados se utilizaran para demostrar un teorema importante.

Lema A1: Los vertices de un grafo conexo G con n vertices se pueden enumerar v1, ..., vn de talforma que Gi := G[v1, ..., vi] es conexo para todo i = 1, ..., n.

Demostracion. Esta prueba se hace por induccion. Para i = 1, la enumeracion es simplemente v1,y G1 = G es conexo.

Supongamos que para i < |G| se ha elegido la enumeracion v1, ..., vi de tal forma que Gi es conexo.Se elige el vertice vi+1 de la siguiente forma: sea v ∈ G−Gi. Como G es conexo existe un caminoP en G que comienza en v y termina en v1. Se elige a vi+1 como el ultimo vertice del camino Pque esta contenido en G−Gi. Note que con esta eleccion vi+1 tiene un vecino en Gi.

Veamos que Gi+1 es conexo. Sean x, y ∈ Gi+1. Si x = y el camino es el trivial. Si x, y ∈ Gi, porhipotesis de induccion Gi es conexo y por lo tanto existe un camino entre x, y. Si alguno de los dosvertices esta en Gi y el otro no, es decir el otro es vi+1, por eleccion, vi+1 tiene un vecino en Gi ypor conexidad de Gi existe un camino entre ambos vertices.

Definicion A8: Sea G un grafo, y sea T ⊆ G. Si T es un arbol, y ademas tiene exactamente losvertices de G, se dice que T es un arbol generador de G.

Lema A2: Sea G un grafo conexo con n vertices. Entonces G tiene un arbol generador.

Demostracion. Se utiliza la contruccion de la enumeracion del lema anterior. En cada paso seconstruye un arbol Ti+1 que contiene a los vertices v1, ..., vi+1 de la siguiente forma: recordamosque la eleccion de vi+1 se hacıa de tal forma que este vertice tuviera un vecino en {v1, ..., vi} luegose elige una unica arista e que conecta a vi+1 con {v1, ..., vi}. Y tome como Ti+1 el arbol que resultade anadir a Ti el vertice vi+1 y el arco e.

Veamos por induccion que Ti es un arbol para todo i = 1, ..., n. Si n = 1, Ti tiene solo un verticey por lo tanto es conexo y no contiene ciclos.

Supongamos ahora que Ti es un arbol, y veamos que Ti+1 tambien lo es. De la construccion es claroque Ti+1 es conexo. Si Ti+1 contuviera ciclos, dicho ciclo contendrıa a vi+1 porque por hipotesis deinduccion Ti no los contiene. Esto implica que vi+1 es de grado mayor o igual a 2, lo que contradicela construccion del unico vecino de vi+1. Por lo tanto Ti+1 es un arbol.

El resultado se sigue tomando i = n. Tn es un arbol generador para G.

2Maximal en el sentido de inclusion de grafos.

42

El siguiente es el teorema importante al que se hara referencia durante el trabajo.

Teorema A1. Un grafo conexo con n vertices es un arbol si y solo si tiene n− 1 aristas.

Demostracion. En primer lugar veamos que un arbol T con n vertices tiene n− 1 aristas.

Los vertices de T se pueden enumerar v1, ..., vn de forma tal que para i ≥ 2, vi+1 tenga un unicovecino en {v1, ..., vi}. Esto viene del lema anterior en el caso particular en el que G es el arbol T .

Ahora veamos por induccion que el subgrafo de T generado por los primeros i vertices, es decirT [v1, ..., vi], tiene exactamente i− 1 arcos. Si i = 1, T [vi] contiene solo un vertice y 0 arcos. Ahorasupongamos que T [v1, ..., vi] tiene i− 1 arcos y veamos que T [v1, ..., vi+1] tiene i arcos. Basta verque solo se agrega una arista. Note que si se agregaran dos, T [v1, ..., vi+1] contendrıa un ciclocontradiciendo el hecho de que T es un arbol. Tomando i = n se concluye que T tiene n-1 aristas.

Ahora supongamos que G es un grafo conexo con n vertices y n− 1 aristas. Veamos que G es unarbol. Por el lema anterior, G contiene un arbol generador G′. Por la discusion anterior G′ tienen− 1 aristas y por lo tanto G = G′, un arbol.

A partir de todos los resultados anteriores se concluye que el arbol generador de un grafo conexoG con n vertices tiene exactamente n− 1 aristas.

r-Particiones

Definicion A9: Sea r ∈ Z≥2. Un grafo G = (V,E) es r-partito si existe una particion de V en rclases tal que cada arco tiene extremos en diferente clase. Los grafos 2-partitos se llaman bipartitos.Sin un grafo es r-partito y ademas cumple que cualquier par de vertices de clases diferentes sonadyacentes, entonces se llama completo. Tambien se usa la notacion Kr

s para referirse al grafocompleto r-partito en el que cada clase tiene exactamente s vertices. O tambien se usa por ejemplola notacion K3,3 = K2

3 .

43

Apendice B

Complejidad Computacional

Las siguientes son algunas notas sobre la notacion O-grande para describir la complejidad y eltiempo de ejecucion de algoritmos. En particular, se hace enfasis en algoritmos en los que laentrada es un grafo, y por lo tanto el tamano de la instancia se describe por n y m, el numero devertices y arcos respectivamente del grafo.

En general, el tiempo de ejecucion de un algoritmo depende del tamano de la instancia que elalgoritmo esta resolviendo. Cuando se trata de grafos, el tamano de la instancia consiste en dosnumeros enteros n y m que son el numero de vertices y arcos respectivamente. Al resolver cualquierproblema, se podrıa pensar en la funcion f(n,m),

f : N× N −→ N+

que mide el numero de pasos, en el peor de los casos, necesarios para resolver el problema. Noobstante, medir el tiempo de ejecucion exacto puede ser muy difıcil en la practica. Por esta razon seutilizan estimaciones basadas en un analisis asintotico que buscan entender el tiempo de ejecucionen instancias grandes [15].

Para esto, se considera el termino de orden mayor en la expresion para f(n,m) pues este terminodomina a los demas. Ademas, al medir la complejidad de un problema, se acostumbra medir lacantidad de pasos, en el peor de los casos, necesarios para resolver el problema. Ası, se introducela siguiente notacion O-grande.

Definicion B1: Sean f, g : N −→ R+ funciones. Se dice que f(n) es O(g(n)) (O-grande de g(n)),si existen constantes c, n0 ∈ Z+ tales que para todo n ≥ n0 se tiene:

f(n) ≤ c · g(n)

En este caso se dice que g(n) es un cota superior asintotica para f(n).

La generalizacion de esta definicion al caso multivariado, es un poco mas complicada para que secumplan todas las propiedades deseadas (ver [16]). Sin embargo tambien se puede enunciar:

Sea f : Nk −→ R+. Se considera la siguiente funcion f : Nk −→ R+ dada por:

f(n1, ..., nk) = max{f(i1, ..., ik)|0 ≤ ij ≤ nj ,para todo j, 1 ≤ j ≤ k}

Entonces se puede enunciar la definicion:

Definicion B2: Sean f, g : Nk −→ R+ funciones. Entonces f(n1, ..., nk) es O(g(n1, ..., nk)) siexisten constantes c,N ∈ Z+ tales que para todo n1 ≥ N, ..., nk ≥ N se cumplen las siguientes doscondiciones:

f(n1, ..., nk) ≤ c · g(n1, ..., nk)

44

f(n1, ..., nk) ≤ c · g(n1, ..., nk)

Esta definicion se puede tomar como la definicion final, pues satisface todas las propiedades im-portantes que se mencionan mas adelante, y ademas resulta ser equivalente a la primera definicioncuando se toma el caso univariado.

Note que para funciones crecientes f = f y por lo tanto solo es necesario verificar la primeracondicion.

Propiedades:

Las siguientes son las propiedades importantes que satisface la notacion O-grande. Estas propie-dades se utilizaran para mostrar y explicar la complejidad de los algoritmos en el proyecto degrado.

1. O(f(n1, ..., nk)) = O(cf(n1, ..., nk)) para todo c ∈ R+

2. O(f1(n1, ..., nk)) +O(f2(n1, ..., nk)) = O(max(f1(n1, ..., nk), f2(n1, ..., nk)))

3. O(f1(n1, ..., nk))O(f2(n1, ..., nk)) = O(f1(n1, ..., nk)f2(n1, ..., nk))

O-grande y Logaritmos

Es comun que al analizar algoritmos se exprese la complejidad del problema en terminos de funcio-nes logarıtmicas. Como loga(n) = logb(n)/ logb(a), el estudio de la complejidad no depende de labase del logaritmo. Por esta razon se acostumbra a escribir, por ejemplo, O(m log n) sin especificarla base.

45

Bibliografıa

[1] Jaroslav Nesetril. A few remarks on the history of mst-problem. Archivum mathematicum,33(1):15–22, 1997.

[2] David Cheriton and Robert Endre Tarjan. Finding minimum spanning trees. SIAM Journalon Computing, 5(4):724–742, 1976.

[3] Ellis Horowitz and Sartaj Sahni. Fundamentals of data structures. Pitman, 1983.

[4] Bang Ye Wu and Kun-Mao Chao. Spanning trees and optimization problems. CRC Press,2004.

[5] H Bernhard, BH Korte, and J Vygen. Combinatorial optimization: Theory and algorithms,2008.

[6] Joseph B Kruskal. On the shortest spanning subtree of a graph and the traveling salesmanproblem. Proceedings of the American Mathematical Society, 7(1):48–50, 1956.

[7] Random Link. Sage is a free open-source mathematics software system licensed under thegpl. it combines the power of many existing open-source packages into a common python-based interface. mission: Creating a viable free open source alternative to magma, maple,mathematica and matlab. Sage, 4:7, 2011.

[8] Robert Clay Prim. Shortest connection networks and some generalizations. Bell systemtechnical journal, 36(6):1389–1401, 1957.

[9] Alfred V Aho and John E Hopcroft. Design & Analysis of Computer Algorithms. PearsonEducation India, 1974.

[10] Reinhard Diestel. Graph theory (graduate texts in mathematics). 2005.

[11] NF Dyshkant. An algorithm for calculating the similarity measures of surfaces represented aspoint clouds. Pattern Recognition and Image Analysis, 20(4):495–504, 2010.

[12] A Jesus, Santos Francisco, and Jorg Rambau. Triangulations. structures for algorithms andapplications. 2010.

[13] Bernard Chazelle. A minimum spanning tree algorithm with inverse-ackermann type comple-xity. Journal of the ACM (JACM), 47(6):1028–1047, 2000.

[14] Reinhard Diestel. Graph theory {graduate texts in mathematics; 173}. Springer-Verlag Berlinand Heidelberg GmbH & amp, 2000.

[15] Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, 2012.

[16] Rodney R Howell. On asymptotic notation with multiple variables. Technical report, Citeseer,2008.

46