universidad politÉcnica de madrid facultad de … · en 1736 y versaba sobre el problema de los...

UNIVERSIDAD POLITÉCNICA DE MADRID

FACULTAD DE INFORMÁTICA

TRABAJO FIN DE CARRERA

RECUBRIMIENTO POR VÉRTICES, RECUBRIMIENTO A DISTANCIA E INDEPENDENCIA EN GRAFOS

Julio 2013

AUTOR: Oscar Díaz Martín TUTOR: Gregorio Hernández Peñalver

iii

A mis padres y mi hermana, por dármelo todo, por ser quien soy y porque sin ellos no habría podido escribir estas líneas. A mi niña, Mª Pilar, por su paciencia, su empuje y su constante apoyo y ánimo para no rendirme. A Gregorio Hernández por darme la oportunidad de realizar este proyecto, por su tiempo, dedicación y enseñanzas.

Recubrimiento por Vértices, Recubrimiento a Distancia e Independencia en Grafos

vii

INDICE 1.INTRODUCCIÓN ......................................................................................................... 1

2.TEORÍA DE GRAFOS .................................................................................................. 3

2.1.INTRODUCCION ............................................................................................... 3

2.2.HISTORIA ........................................................................................................... 3

2.3.NOCIONES PREVIAS GENERALES ............................................................... 4

2.3.1.Grafo .......................................................................................................... 4

2.3.2.Clases de grafos ......................................................................................... 6

2.4.VERTEX COVER ............................................................................................... 9

2.4.1.Conceptos generales .................................................................................. 9

2.4.2.Heurísticas ................................................................................................. 9

2.4.2.1.Vértice de mayor grado ................................................................. 9

2.4.2.2.Arista optima ............................................................................... 11

2.4.2.3.Arista aleatoria............................................................................. 13

2.4.2.4.Refinamiento ............................................................................... 15

2.4.2.5.Óptimo mediante fuerza bruta ..................................................... 16

2.4.2.6.K-Camaras ................................................................................... 18

2.5.VERTEX COVER A DISTANCIA ................................................................... 21

2.5.1.Conceptos Generales ............................................................................... 21

2.5.2.Heurísticas ............................................................................................... 22

2.5.2.1.Vértice de mayor grado con distancia 2 ...................................... 22

2.5.2.2.Vértice de mayor grado con distancia 3 ...................................... 23

2.5.2.3.K-Camaras con distancia 2 y distancia 3 ..................................... 24

2.6.INDEPENDENCIA ........................................................................................... 25

2.6.1.Conceptos Generales ............................................................................... 25

2.6.2.Heurísticas ............................................................................................... 26

2.6.2.1.Vértice de menor grado ............................................................... 26

3.DISEÑO DE LA APLICACIÓN ................................................................................. 29

3.1.INTRODUCCIÓN ............................................................................................. 29

3.2.DISEÑO DE ALTO NIVEL .............................................................................. 31

3.2.1.Definición de los límites del sistema ....................................................... 31

3.2.2.Diagrama de casos de uso........................................................................ 33

3.2.3.Descripción de los actores ....................................................................... 36

3.2.4.Modelo conceptual del sistema ............................................................... 36

3.2.5.Casos de uso en formato de alto nivel ..................................................... 37


viii

3.2.6.Casos de uso en formato expandido ........................................................ 52

3.3.DISEÑO DE BAJO NIVEL ............................................................................. 107

3.3.1.Diagramas de Colaboración .................................................................. 107

3.3.1.1.Crear un nuevo grafo ................................................................. 108

3.3.1.2.Abrir un grafo ............................................................................ 109

3.3.1.3.Guardar un grafo ....................................................................... 110

3.3.1.4.Dibujar un nuevo vértice ........................................................... 111

3.3.1.5.Dibujar una nueva arista ............................................................ 111

3.3.1.6.Editar un vértice ........................................................................ 112

3.3.1.7.Editar una arista ......................................................................... 113

3.3.1.8.Borrar un vértice ........................................................................ 114

3.3.1.9.Borrar una arista ........................................................................ 115

3.3.1.10.Dibujar un grafo predefinido ................................................... 115

3.3.1.11.Calcular Vertex Cover mediante el algoritmo Voraz .............. 120

3.3.1.12.Calcular Vertex Cover mediante el algoritmo Arista Optima . 122

3.3.1.13.Calcular Verter Cover mediante el algoritmo K-Camaras ...... 123

3.3.1.14.Calcular el conjunto Independiente ......................................... 125

3.3.1.15.Establecer peso de las aristas aleatorio .................................... 126

3.3.1.16.Cambiar color de los elementos seleccionados ....................... 127

3.3.2.Diagramas de Clases ............................................................................. 128

3.3.2.1.Aplicación-Interfaz .................................................................... 129

3.3.2.2.Grafo .......................................................................................... 132

3.3.2.3.Algoritmos ................................................................................. 136

3.3.2.4.Funcionalidades ......................................................................... 139

4.ESTUDIO COMPARATIVO .................................................................................... 143

4.1.Comparativa 1: Número de vértices fijo. ......................................................... 144

4.2.Comparativa 2: Probabilidad de las aristas fija. ............................................... 150

5.MANUAL DE USUARIO ......................................................................................... 157

5.1.PANTALLA PRINCIPAL ............................................................................... 157

5.2.BARRA DE MENÚ ......................................................................................... 158

5.2.1.Archivo .................................................................................................. 158

5.2.2.Edición................................................................................................... 158

5.2.3.Grafo ...................................................................................................... 159

5.2.4.Calcular ................................................................................................. 162

5.2.5.Configuración ........................................................................................ 163

5.2.6.Ayuda .................................................................................................... 164

5.3.BARRA DE HERRAMIENTAS ..................................................................... 164


ix

5.4.PANEL DE DIBUJO ....................................................................................... 165

5.5.PANEL DE INFORMACIÓN ......................................................................... 166

5.6.PANEL DE EJECUCIÓN ................................................................................ 168

6.CONCLUSIONES ..................................................................................................... 169

7.BIBLIOGRAFÍA ....................................................................................................... 171


x


xi


xii


1

1. INTRODUCCIÓN

El objetivo de este proyecto es el desarrollo de una aplicación software que permita al usuario trabajar con grafos, sobre los cuales podrá aplicarles una serie de algoritmos.

El usuario podrá generar grafos de forma manual, dibujando sus vértices y sus

aristas, así como dibujar una serie de grafos predefinidos. Estos grafos podrán ser editados y modificados a voluntad del usuario.

Los algoritmos que el usuario podrá aplicar sobre los grafos los podemos dividir en

dos grupos: Algoritmos de recubrimientos de vértices o Vertex Cover y algoritmos de Independencia. Para encontrar soluciones “próximas” a las soluciones óptimas de este tipo de problemas se han implementado una serie de algoritmos de aproximación que siguen distintos enfoques, desde búsquedas voraces hasta elecciones aleatorias de candidatos.

Para varios de estos algoritmos, se ha añadido la opción de poder refinar la solución

encontrada de manera que nos podamos acerca lo máximo posible a una de esas soluciones óptimas. Para otros se han incluido la opción de calcular la solución óptima mediante fuerza bruta, de tal manera que podamos comparar los resultados de los distintos algoritmos.

El usuario podrá ejecutar los distintos algoritmos paso a paso para comprobar los

resultados parciales encontrados o ir directamente al resultado final de la ejecución. En ambos casos, se mostrará al usuario información visual del avance del algoritmo.

Al final de esta memoria se incluye un estudio que permite comparar los resultados

experimentales obtenidos al aplicar cada uno de los algoritmos implementados sobre un amplio conjunto de grafos generados por la aplicación.

Los problemas de Recubrimiento de Vértices los podemos encontrar en distintos

campos de la vida real como son la ingeniería civil, las comunicaciones o la bioinformática. Un caso típico lo encontramos en problemas de vigilancia: ¿Cuántas cámaras son necesarias para vigilar una serie de calles y dónde situarlas?, ¿Cómo podemos vigilar todos los pasillos de un supermercado de tal manera que el número de cámaras sea el mínimo posible? ¿Dónde situar un número determinado de cámaras de vigilancia de tal manera que el área a vigilar sea máximo? A estos problemas y otros muchos más los podremos dar solución con los algoritmos Vertex Cover.


2


3

2. TEORÍA DE GRAFOS

2.1. INTRODUCCION Los grafos son estructuras matemáticas utilizadas para modelizar relaciones entre

objetos de un conjunto. Del estudio de estas estructuras, los grafos, se encarga la Teoría de Grafos.

En este contexto, podemos definir un grafo como un conjunto no vacío de vértices o

nodos y una serie de aristas, dirigidas o no, que conectan pares de vértices. Para la representación gráfica de un grafo se utilizan una serie de puntos que

representan los vértices. Las aristas se representan por líneas que conectan los vértices del grafo.

2.2. HISTORIA El primer trabajo relativo a grafos fue escrito por el matemático suizo Leonard Euler

en 1736 y versaba sobre el problema de los puentes de Königsberg. El problema dado era el siguiente:

“La ciudad de Kaliningrado, originalmente Königsberg, es famosa por sus siete

puentes que unen ambas márgenes del río Pregel con dos de sus islas. Dos de los puentes unen la isla mayor con el margen oriental y otros dos con el margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. ¿Es posible, partiendo de un lugar arbitrario, regresar al lugar de partida cruzando cada puente una sola vez?

Figura 2.1: Problema de los puentes de Köningsberg


4

Euler recurre a una abstracción del mapa, fijándose exclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente lo representó mediante una línea que unía dos puntos, cada uno de los cuales representaba una de las zonas de Königsberg. Con este esquema, Euler consigue demostrar que este problema no tiene solución, es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces.

En 1847, Gustav Kirchhoff utilizó la teoría de grafos para el análisis de redes

eléctricas publicando sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos, conocida como Leyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería.

En 1852 Francis Guthrie planteó El problema de los cuatro colores el cual afirma

que es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken en 1976, puede ser considerado como el nacimiento de la Teoría de Grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.

El término “grafo”, proviene de la expresión “graphic notation” usada por primera

vez por Edward Frankland y posteriormente adoptada por Alexander Crum Brown en 1884, y hacía referencia a la representación gráfica de los enlaces entre los átomos de una molécula.

El primer libro sobre teoría de grafos fue escrito por Dénes König y publicado en

1936.

2.3. NOCIONES PREVIAS GENERALES

A continuación se exponen los conceptos básicos relativos a la Teoría de Grafos necesarios para la realización de este proyecto.

2.3.1. Grafo Un grafo G = (V, A) consiste en un conjunto no vacío y finito V, cuyos miembros

se llaman vértices y una familia finita A de pares no ordenados de vértices a cuyos elementos llamaremos aristas o arcos y que denotaremos por (u, v), donde u y v Є V.


5

El número de vértices, es decir, la cardinalidad del conjunto V se denomina orden del grafo y se denota por |V|. Por lo general, se utiliza n para denotar el orden de G.

El número de aristas, es decir, la cardinalidad del conjunto A se denomina tamaño

del grafo y se denota por |A|. Por lo general, se utiliza m para denotar el tamaño de G. Dado un grafo G = (V, A) podemos dar las siguientes nociones: • Se dice que dos vértices son adyacentes si tienen una arista en común.

• Se dice que una arista y un vértice son incidentes si el vértice es extremo a la arista.

• Se llama grado de un vértice al número de aristas incidentes con él, contando los bucles como dos aristas. Se denota por d(v) al grado del vértice v.

Llamaremos subgrafo de G = (V, A) a un grafo G’ = (V’, A’) tal que V’ЄV y A’ЄA. Un camino en un grafo es un recorrido en el que no se repiten vértices ni aristas. Un

recorrido es una sucesión de vértices y aristas de la forma v0 a1 v1 a2 ......vk-1 ak vk donde la arista ai une los vértices vi-1 y vi. . Éste es un recorrido de v0 a vk, de longitud k. Si v0

= vk se dice que el recorrido es cerrado.

Figura 2.2: Ejemplo de grafo


6

Figura 2.3: Ejemplo de grafo

2.3.2. Clases de grafos Un grafo simple es un par G = (V, A) donde V es un conjunto finito, no ordenado y

no vacío y A es un conjunto finito de pares no ordenados de vértices distintos de V, es decir, no debe haber aristas múltiples ni bucles.

Donde una arista múltiple es una arista que aparece repetida en A, o lo que es lo

mismo, existen dos aristas que tienen el mismo origen y el mismo destino y un bucle es una arista que tiene como origen y destino el mismo vértice de A.

Un grafo regular es un grafo simple donde todos sus vértices tienen el mismo

grado, es decir, todos los vértices tienen el mismo número de aristas que parten de él.

Figura 2.4: Grafo regular

Un grafo es conexo si para cada par de vértices u ,v existe un camino entre ellos.


7

Figura 2.5: Ejemplos de grafos conexo y no conexo

Un grafo ciclo es un grafo que consiste en un camino cerrado en el que no se repite

ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino.

• Un grafo ciclo de n vértices se presenta como Cn. • El número de vértices es el igual al de aristas.

• Es un grafo regular en el que el grado de todos los vértices es dos.

Figura 2.6: Grafo ciclo

Un grafo completo es un grafo simple en el que todo par de vértices está unido por

una arista, es decir, todos los vértices están unidos entre sí. • Un grafo completo de n vértices se representa como Kn.

• Un grafo completo tiene n vértices y n(n-1)/2 aristas. • Es un grafo regular en el que el grado de todos los vértices es n-1.


8

Figura 2.7: Grafo completo

Un grafo bipartido G = (V, A) es bipartido si existe un partición de V, V = X ∪ Y,

tal que cada arista uv ∈ A une un vértice de X con otro de Y. • Un grafo bipartido se denota por Kr, s donde r sería el número de vértices de X y

s el número de vértices de Y. • El número de vértices del grafo es r + s y el número de aristas es variable pero

siempre menor a r * s. Un grafo bipartido completo G = (V, A) es un grafo en el que existe una partición

de V, V = X ∪ Y en el que para todo vértices u∈ X y para todo vértice v ∈ Y existe una

arista uv ∈ A, es decir, hay una arista que conecta cada vértice de X con cada vértice de Y y viceversa.

• Un grafo bipartido se denota por Kr, s donde |X| = r e |Y| = s.

• El número de vértices del grafo es r + s y el número de aristas es r * s. • El grado de los vértices de X será s y el grado de los vértices de Y es r.

Figura 2.8: Grafo bipartido completo


9

2.4. VERTEX COVER En 1972, Karp presentó una lista de veintiún problemas NP-Completos, uno de los

cuales era el problema de encontrar el conjunto Vertex Cover de un grafo. Dado un grafo, hay que encontrar el conjunto más pequeño de vértices tal que cada arista tenga al menos un vértice en ese conjunto. Tal conjunto de vértices se llama mínimo Vertex Cover, y en general, puede ser muy difícil de encontrar.

2.4.1. Conceptos generales Dado un grafo G = (V, A), un conjunto de vértices K ⊂ V se dice que es un

recubrimiento por vértices de G si toda arista de G tiene algunos de sus extremos en K.

Un recubrimiento es minimal si ninguno de sus subconjuntos propios es un

recubrimiento. El mínimo número de vértices en un recubrimiento K del grafo G se denomina

número de recubrimiento de G y se indica con la notación α (G).

2.4.2. Heurísticas Para solucionar computacionalmente los problemas de recubrimientos con un valor

de complejidad aceptable, se utilizan algoritmos aproximados que consiguen soluciones buenas que no difieren mucho de las óptimas.

Para el caso de Vertex Cover se han implementado los siguientes algoritmos:

2.4.2.1. Vértice de mayor grado La heurística de este algoritmo es una heurística voraz. Sea un grafo G = (V, A) y C el conjunto solución Vertex Cover inicialmente vacío.

Los pasos del algoritmo son:

1. Elegir el vértice v ϵ V de mayor grado.


10

2. Seleccionar ese vértice y añadirlo al conjunto solución C. 3. Marcar las aristas que salen del vértice v como cubiertas. 4. Repetir los pasos 1, 2 y 3 hasta que no queden aristas por cubrir y sin tener

en cuenta los vértices y aristas ya seleccionados. A continuación se muestra un ejemplo de ejecución de este algoritmo:

1. Este el grafo en su estado inicial sobre el que se va a ejecutar el algoritmo:

2. Primer paso: Se selecciona el vértice de mayor grado. En este caso el vértice número 7 con grado 5:

3. En el siguiente paso se selecciona el vértice número 3 con grado 4:


11

4. En los siguientes pasos se siguen seleccionando vértices hasta que se cubren todas las aristas del grafo. El resultado final es el siguiente:

El conjunto Vertex Cover para este grafo tendría una cardinalidad |C| = 8.

2.4.2.2. Arista óptima Sea un grafo G = (V, A) y C el conjunto solución Vertex Cover inicialmente vacío.


1. Elegir en cada paso la arista tal que la suma de los grados de sus vértices sea el mayor de todos.

2. Seleccionar los vértices u y v de la arista y añadirlos al conjunto solución C. 3. Marcar la arista seleccionada como cubierta. 4. Marca las aristas que salen de los vértices u y v como cubiertas. 5. Repetir los pasos 1, 2, 3 y 4 hasta que no queden aristas por cubrir y sin tener

en cuenta los vértices y aristas ya seleccionados. Veamos un ejemplo de funcionamiento de este algoritmo:


12

1. Tenemos el grafo inicial.

2. En el primer paso, seleccionamos la arista que tiene como extremos los

nodos 0 y 7, que es la que tiene mayor grado. Seleccionamos los dos vértices extremos de la arista, y marcamos todas sus aristas incidentes.

3. En la segunda iteración, se selecciona la arista con extremos en los vértices 3

y 10.

4. Seguiríamos ejecutando el algoritmo, hasta que se cubrieran todas las aristas

del grafo, con el siguiente resultado:


13

Observamos que la cardinalidad del conjunto solución es |C| =10.

2.4.2.3. Arista aleatoria Sea un grafo G = (V, A) y C el conjunto solución Vertex Cover inicialmente vacío.


1. Elegir en cada paso una arista de manera aleatoria. 2. Seleccionar los vértices u y v de la arista y añadirlos al conjunto solución C. 3. Marcar la arista seleccionada como cubierta. 4. Marcar las aristas que salen de los vértices u y v como cubiertas. 5. Repetir los pasos 1, 2, 3 y 4 hasta que no queden aristas por cubrir y sin tener

en cuenta los vértices y aristas ya seleccionados. A continuación se muestra un ejemplo de ejecución:

1. Grafo inicial:

2. En el primer paso se selecciona de manera aleatoria una arista.


14

La arista seleccionada es la que tiene como extremos los nodos 4 y 11. Se marcan estos dos nodos así como las aristas incidentes en ellos.

3. En el segundo paso se vuelve a seleccionar otra arista también de manera aleatoria. En este caso la arista seleccionada tiene como extremos los vértices 8 y 9.

4. Se sigue con la ejecución del algoritmo hasta que no queden más aristas por cubrir.


15

El conjunto Vertex Cover de la solución está formado por 10 vértices, |C| = 10, muy lejos de la solución óptima que más tarde mostraremos que es 7.

2.4.2.4. Refinamiento Con los algoritmos anteriores encontramos soluciones aproximadas a la óptima.

Para mejorar el resultado del algoritmo se le puede añadir un paso siguiente que sería refinar la solución encontrada.

Para poder refinar tenemos que partir de una solución encontrada y a partir de ella

buscaremos los vértices que están en la solución y se puede eliminar. El procedimiento será el siguiente:

Sea C una solución Vertex Cover del grafo G = (V, A).

1. Se elige en cada paso un vértice v de C, el cual todos sus nodos adyacentes también estén en el conjunto solución C.

2. Se elimina ese vértice v del conjunto solución C. 3. Se repiten los pasos 1 y 2 hasta que no se puedan eliminar más nodos de la

solución encontrada. Este refinamiento no siempre es posible debido a que la solución encontrada no

permita eliminar ningún vértice de la misma. Veamos un ejemplo de este refinamiento:

1. Partimos de una solución encontrada, por ejemplo la solución encontrada para el algoritmo Arista Aleatoria, que tenía una cardinalidad |C| = 10.


16

2. Para el primer paso, podemos ver que se saca del conjunto solución el nodo

número 3, ya que todos sus adyacentes están seleccionados y lo podemos eliminar sin perder aristas recubiertas.

3. En el siguiente paso se puede volver a refinar y podemos eliminar de la solución el vértice número 8 sin perder recubrimiento.

Ya no podríamos seguir refinando y la ahora la solución refinada tendría una cardinalidad |C´| = 8. Aunque no hemos encontrado una solución óptima, vemos que hemos mejorado respecto a la solución inicial |C| = 10.

2.4.2.5. Óptimo mediante fuerza bruta Para el cálculo de un solución óptima (de todas las que puede haber), utilizaremos la

fuerza bruta.


17

Para optimizar el tiempo de cálculo, partiremos de una solución voraz encontrada y a partir de ella haremos una búsqueda binaria.

Supongamos el ejemplo anterior. Tenemos un grafo con 12 nodos y hemos encontrado una solución refinada tal que

|C´| = 8 Desechamos todas las soluciones con más de ocho nodos y buscamos a ver si existe

una solución de 4 nodos. Con 4 nodos no hemos podido encontrar ninguna solución, así que desechamos

todas las soluciones de cuatro vértices o menos y buscamos a ver si existe una solución óptima con 6 nodos.

Con seis nodos tampoco podemos encontrar una solución óptima, así que

desechamos todas las soluciones de seis o menos vértices y probamos con soluciones de siete nodos.

En este caso sí encontramos una solución C* con |C*| = 7 que es la que se muestra a

continuación:

1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8 9 10 11 12


18

En cada paso calcularíamos combinaciones sin repetición de m elementos tomados

de n en n.

Cm, n = [(m!) / (n! · (m-n)!) ]

Para el caso de la solución óptima se habrían calculado sólo para 7 elementos:

C12, 7 = [(12!) / (7! (12-7)!) ] = [(479001600) / (5040 · (120))] =

= [479001600 / 604800] = 792 combinaciones sin repetición de 12

elementos tomadas de 7 en 7.

2.4.2.6. K-Cámaras Para este tipo de algoritmo es necesario que el grafo sea ponderado, es decir, que

cada arista del grafo tenga un peso numérico asociado. También es necesario el parámetro k, que determina la cardinalidad máxima que

puede tener el conjunto solución, es decir, que este parámetro nos puede limitar que no sean cubierta todas las aristas del grafo como en algoritmos anteriores.

La estrategia de este algoritmo es muy similar a la de seleccionar el vértice de

mayor grado. Sea G = (V, A) un grafo ponderado, C el conjunto solución Vertex Cover

inicialmente vacío y k el número máximo de vértices del conjunto solución. Los pasos del algoritmo son:


19

1. Elegir el vértice v ϵ V de mayor peso. 2. Seleccionar ese vértice y añadirlo al conjunto solución C. 3. Marcar las aristas que salen del vértice v como cubiertas. 4. Repetir los pasos 1, 2 y 3 hasta que no queden aristas por cubrir y no se

haya superado el valor de k, y sin tener en cuenta los vértices y aristas ya seleccionados.

Este tipo de heurística es muy útil para resolver problemas de aplicación como el

siguiente: “Se desea vigilar los pasillos que forman un supermercado, pero con un número

determinado de cámaras, de tal manera que el área a vigilar sea máxima conforme a una prioridad que se otorga a los distintos pasillos. Cada intersección entre los pasillos será un vértice del grafo en el cual se podrá colocar una cámara. A las aristas del grafo, que representarán los pasillos, se le asignará un peso conforme a la importancia o prioridad que tiene ese pasillo a la hora de ser vigilado. Una vez que tenemos definido el grafo, consiste en buscar el conjunto Vertex Cover de tamaño k que cumpla con los requisitos especificados y maximice el valor de los pasillos vigilados”.

A continuación veamos un ejemplo de ejecución, en el que el grafo podría

representar el ejemplo anterior y para un número de cámaras k = 5.

1. Grafo inicial ponderado:

2. En cada iteración buscamos el nodo con mayor peso. En este caso se selecciona el vértice 8 con peso 250. Se selecciona el vértice 8 y sus aristas incidentes.


20

3. En el segundo paso del algoritmo el mayor peso es 238 y corresponde al

vértice número 6.

4. En los siguientes pasos se seleccionan los vértices 10, 12 y 16 con pesos 193, 188 y 173 respectivamente. El resultado final para este algoritmo con k = 5 sería el que se muestra en la siguiente figura:


21

En este caso no se ha encontrado un recubrimiento para todo el grafo, sino que se ha encontrado el mayor recubrimiento para un número k = 5.

2.5. VERTEX COVER A DISTANCIA

2.5.1. Conceptos Generales Dado un grafo G = (V, A), un conjunto de vértices C ⊂ V se dice que es un

recubrimiento (Vertex Cover) a distancia k si para toda arista de G existe un camino P de longitud a los sumo k, que contiene la arista y a un vértice de C.

Al cardinal mínimo de un conjunto recubiertos a distancia k se le llama número de

recubrimiento k-distante (por vértices) del grafo y se designa por ββββ≤≤≤≤k(G) o ββββkd(G). El recubrimiento a distancia se generaliza a Broadcast Cover, cuando el

recubrimiento de cada vértice puede tener diferente alcance. Esta variante fue introducida por Erwin en 2004. Veamos la definición de Broadcast.

Dado un grafo G = (V, A), definimos una transmisión (o broadcast) como función

f: V → N ∪{0}. El coste de una transmisión f sobre un conjunto de vértices S es

∑∈

=Su

)u(f)S(f .

Así f (V) es el coste total de la función de transmisión f. Una transmisión (o broadcast) f es recubridora del grafo G = (V, A) si para cada

arista xy existe un camino P en G que incluya a la arista xy y tal que uno de sus extremos es un vértice u con f(u) ≥ long(P).

Un transmisión recubridora f es óptima si f (V) es mínima con respecto a todas las

posibles emisiones recubridoras del grafo G. El problema “Broadcast Cover Problem” consiste en construir esta función óptima. Designamos el coste óptimo por ββββb(G).


22

2.5.2. Heurísticas Las heurísticas que utilizaremos para resolver estos problemas de recubrimiento a

distancia derivan de las heurísticas de Vertex Cover.

2.5.2.1. Vértice de mayor grado con distancia 2 Sea un grafo G = (V, A) y C el conjunto solución Vertex Cover inicialmente vacío.

Los pasos son:

1. Elegir el vértice v ϵ V tal que la suma de su grado más el de sus adyacentes sea el máximo.

2. Seleccionar ese vértice y añadirlo al conjunto solución C. 3. Marcar los vértices adyacentes como cubiertos por distancia 2. 4. Marcar las aristas que salen del vértice v y de sus nodos adyacentes como

cubiertas. 5. Repetir los pasos 1, 2, 3 y 4 hasta que no queden aristas por cubrir y sin tener

en cuenta los vértices y aristas ya seleccionados. Veamos un ejemplo de este algoritmo:

1. Tenemos el siguiente grafo en estado inicial:

2. Ejecutamos el algoritmo y en el primer paso es seleccionado el nodo número 7. Se puede observar en color rojo el vértice y las aristas seleccionadas con distancia 1 y en color azul, los vértices y las aristas con distancia 2.


23

3. En el segundo paso observamos que el nodo seleccionado es el número 10 y que el algoritmo finalizaría ya que habríamos cubierto todas las aristas del grafo.

2.5.2.2. Vértice de mayor grado con distancia 3 Sea un grafo G = (V, A) y C el conjunto solución Vertex Cover inicialmente vacío.

Los pasos son:

1. Elegir el vértice v ϵ V tal que la suma de su grado más el de sus adyacentes más el de los adyacentes de estos últimos sea el máximo.

2. Seleccionar ese vértice y añadirlo al conjunto solución C. 3. Marcar los vértices adyacentes como cubiertos por distancia 2. 4. Marcar los vértices adyacentes de los adyacentes como cubiertos por

distancia 3 5. Marcar las aristas que salen del vértice v, de sus nodos adyacentes y de los

adyacentes de los adyacentes como cubiertas.


24

6. Repetir los pasos 1, 2, 3, 4 y 5 hasta que no queden aristas por cubrir y sin tener en cuenta los vértices y aristas ya seleccionados.

2.5.2.3. K-Cámaras con distancia 2 y distancia 3 En este caso, al igual que para el algoritmo “Vértices de mayor grado”, se han

implementado las variantes con distancia 2 y con distancia 3. Veamos a continuación un ejemplo de “distancia 2” con un número máximo de

cámaras de 2.

1. Grafo inicial:

2. En esta primera iteración del algoritmo, el vértice cuyo peso más el de sus adyacentes es máximo es el vértice número 11 con un peso de 1017.

3. En la segunda y última iteración, ya que k = 2, el vértice seleccionado sería

el número 8 con un peso de 960 y acabaría la ejecución del algoritmo.


25

2.6. INDEPENDENCIA Otro problema de los 21 problemas NP-Completos que presentó Karp es el de

encontrar un conjunto independiente máximo en un grafo. Dado un grafo, hay que encontrar el conjunto más grande de vértices tales que no hay dos vértices en ese conjunto que estén conectados por una arista. Este conjunto de vértices se denomina conjunto independiente máximo y al igual que el caso de Vertex Cover es muy difícil de encontrar.

2.6.1. Conceptos Generales Dado un grafo G = (V, A), un conjunto de vértices I ⊂ V se dice que es

independiente si no existen aristas con los dos extremos en el conjunto I, es decir, si el subgrafo generado por I carece de aristas.

El máximo número de vértices de un conjunto independiente se llama número de

independencia de G y se indica con β (G). Un conjunto independiente I es máximal si para cualquier elemento x de V, el

conjunto I + {x} no es independiente. Sea G (V, A) un grafo y S un subconjunto de V, entonces S es un conjunto

independiente si y sólo si V – S es un recubrimiento por vértices. Si g es un grafo simple de n vértices, entonces se cumple que: α (G) + β (G) = n.


26

2.6.2. Heurísticas Para solucionar computacionalmente los problemas de independencia con un valor

de complejidad aceptable, se utilizan algoritmos aproximados que consiguen soluciones buenas que no difieren mucho de las óptimas.

Para este caso utilizaremos un algoritmo voraz, el cual, proporciona soluciones

“buenas”.

2.6.2.1. Vértice de menor grado Sea un grafo G = (V, A) e I el conjunto Independiente solución inicialmente vacío.


1. Elegir el vértice v ϵ V de menor grado. 2. Seleccionar ese vértice y añadirlo al conjunto solución I. 3. Marcar los vértices adyacentes a v como descartados. 4. Repetir los pasos 1, 2 y 3 hasta que no queden más vértices por seleccionar,

sin tener en cuenta los vértices ya añadidos a I y los descartados. Un ejemplo práctico de uso podría ser el siguiente: “Supongamos que queremos almacenar n productos químicos Q1, Q2,…, Qn.

Algunos de estos productos no se pueden almacenar en el mismo depósito pues reaccionan entre sí. ¿Cuál es el mínimo número de depósitos que son necesarios para almacenar estos productos químicos de forma que sustancias que reaccionan entre sí se almacenen en diferentes depósitos? Podemos modelar esta situación con un grafo G cuyos vértices sean los productos químicos. Dos vértices se unen por una arista si las correspondientes sustancias reaccionan. Así productos en el mismo depósito corresponden a un conjunto independiente de vértices G.”


27

A continuación se muestra un ejemplo de ejecución de este algoritmo:

1. Grafo inicial.

2. En cada iteración buscamos el nodo con menor grado. Para este grafo todos los nodos tienen grado igual a 3, por lo que se cogerá el nodo cuyo número de identificación es menor, que en este caso es el nodo 0.

3. En la siguiente iteración el nodo seleccionado es el número 2.


28

4. En los siguientes pasos se siguen seleccionando vértices hasta que ya no quedan más por seleccionar.


29

3. DISEÑO DE LA APLICACIÓN

3.1. INTRODUCCIÓN Para el desarrollo de la aplicación se ha elegido JAVA como lenguaje de

programación. Java es un lenguaje de programación orientado a objetos desarrollado por Sun

Microsystems a principios de los años 90. El lenguaje en sí toma mucha de su sintaxis de C y C++, pero tiene un modelo de objetos más simple y elimina herramientas de bajo nivel, que suelen inducir a muchos errores, como la manipulación directa de punteros o memoria.

Una de la características principales de Java es la portabilidad, lo que significa que

los programas escritos en este lenguaje deben ejecutarse de manera similar en cualquier plataforma hardware o sistema operativo. Esto se logra mediante un código intermedio denominado bytecode. Este código intermedio, muy similar al código máquina, debe interpretarse a través de una máquina virtual específica para la máquina que lo va a ejecutar.

Un elemento muy importante que introduce Java es el Recolector de basura. El

programador es el que determina cuándo se crean los objetos, pero es este elemento el responsable de liberar de la memoria estos objetos cuando ya no están en uso.

Es un lenguaje muy robusto ya que realiza verificaciones de problemas tanto en

tiempo de compilación como en tiempo de ejecución. El diseño de Java, su robustez, el respaldo de la industria y su fácil portabilidad han

hecho de Java uno de los lenguajes de mayor crecimiento y amplitud de uso en distintos ámbitos de la informática como:

• Dispositivos móviles y sistemas empotrados. • Navegación web, como son los Applets.

• Sistemas servidores como son los Servlets, JSP, Java Beans, etc…


30

Otras características importantes de Java son: • Robustez

• Seguridad • Distribuido

• Multithreaded o Multi-Hilo Para el desarrollo de la aplicación se ha elegido Eclipse ya que es una plataforma de

desarrollo de código abierto basada en Java. Eclipse fue desarrollado originalmente por IBM y ahora es desarrollado por la Fundación Eclipse, que es una organización independiente sin ánimo de lucro.

Para la representación y la documentación del diseño se empleará el estándar UML

(Unified Modeling Language) que es el lenguaje gráfico de modelado de sistemas software más conocido y utilizado en la actualidad. Este estándar nos permite visualizar, especificar, construir y documentar los elementos que forman el sistema software.


31

3.2. DISEÑO DE ALTO NIVEL El objetivo de este apartado es explicar el diseño empleado en la construcción de la

aplicación. Como su nombre indica, no consiste en un diseño exhaustivo de cada una de las líneas de código del programa, sino una visión general del proceso realizado.

Este proceso viene determinado por los siguientes puntos:

• Definición de los límites del sistema. • Diagrama de casos de uso.

• Descripción de los actores del diagrama de casos de uso. • Modelo de dominio o conceptual

• Descripción de los casos de uso en formato de alto nivel. • Descripción de los casos de uso en formato extendido.

3.2.1. Definición de los límites del sistema El proyecto consiste en una aplicación desarrollada en Java, la cual se ejecuta

mediante un Applet, y que permite calcular el conjunto Vertex Cover y la Independencia de un grafo.

Para ello el sistema permite crear un grafo desde cero, añadiendo los nodos y las

aristas que se deseen, generar aleatoriamente uno, indicándole el nº de nodos y la probabilidad de las aristas, o elegir entre unos tipos predefinidos de grafos indicándole el nº de nodos que contienen. También permite cambiar en cualquier momento el tipo de peso de las aristas.

A su vez, el sistema permite modificar los grafos creados añadiendo nuevos

elementos, o editar y eliminar otros existentes. Permite guardar el grafo generado en un fichero que posteriormente podrá ser

abierto e interpretado por la aplicación mostrando el grafo guardado. El área de trabajo está formado por distintos paneles: Un panel principal o área de

dibujo nos permitirá dibujar y visualizar el grafo con el que estamos trabajando, así como diversos paneles laterales en los que se muestra información referente al grafo dibujado (Número de nodos y aristas del grafo) así como al nodo (Identificador, posición y grado) o arista (Identificador, origen y destino y peso) seleccionado. Además


32

se incluye un panel en el que se muestra distinta información de interés, como por ejemplo, detalles de los pasos que efectúa el algoritmo seleccionado.

Una barra de estado en el inferior de la aplicación mostrará la posición del puntero

así como los botones de control que servirán para poder avanzar paso a paso, finalizar o salir del algoritmo que se está ejecutando en ese momento.

En todo momento el sistema proporcionará ayuda al usuario mediante un menú al

efecto. El acceso a todas estas funciones y opciones se realizará tanto desde un menú como

de una barra de herramientas, situadas ambas en la parte superior del espacio de trabajo.


33

3.2.2. Diagrama de casos de uso En el diagrama de casos de uso identificamos los procesos principales del sistema

(casos de uso) y los elementos primarios (actores) que interactúan con el sistema. Cada caso de uso expresa una unidad coherente de funcionalidad.

Los diagramas de casos de uso se utilizan para ilustrar los requerimientos del

sistema al mostrar cómo reacciona con una respuesta a eventos que se producen en el mismo.

• Nuevo Grafo

• Abrir Grafo

• Guardar Grafo

• Salir

• Dibujar Nodo

• Dibujar Arista

• Editar Nodo

• Editar Arista

• Borrar Nodo

• Borrar Arista

• Dibujar Grafo Nulo

• Dibujar Grafo Ciclo

• Dibujar Grafo Estrella

• Dibujar Grafo Rueda

• Dibujar Grafo Completo

• Dibujar Grafo Malla

• Dibujar Grafo Aleatorio Ciclo

• Dibujar Grafo Aleatorio

• Dibujar Grafo de Petersen

• Calcular Vertex Cover Voraz

• Calcular Vertex Cover Voraz Distancia 2

• Calcular Vertex Cover Voraz Distancia 3


34

• Calcular Vertex Cover Arista Aleatoria

• Calcular Vertex Cover Arista Óptima

• Calcular Vertex Cover K-Cámaras

• Calcular Vertex Cover K-Cámaras Distancia 2

• Calcular Vertex Cover K-Cámaras Distancia 3

• Calcular Independencia de Nodos

• Seleccionar Peso Arista 1

• Seleccionar Peso Arista Usuario

• Seleccionar Peso Arista Aleatorio

• Cambiar Color de Selección

• Cambiar Color de Selección para Vertex Cover

• Abrir Ayuda

• Abrir AcercaDe


35

Figura 3.1: Diagrama de casos de uso


36

3.2.3. Descripción de los actores Dentro de nuestro sistema, el único actor que encontramos es el usuario de la

aplicación. Éste, puede ejecutar todas las operaciones del sistema.

3.2.4. Modelo conceptual del sistema

Figura 3.2: Modelo conceptual del sistema El concepto principal de nuestro modelo será el grafo, que estará compuesto por un

conjunto de nodos o vértices y un conjunto de aristas. El sistema mantendrá en edición un único grafo en cada momento, el cual al

comenzar estará vacío y según se vayan introduciendo vértices y aristas se añadirán al grafo que tenemos en edición. Esta relación entre grafo, vértices y aristas es una agregación fuerte ya que, tanto un vértice como una arista, no tienen sentido si no forman parte de un grafo.

GRAFO

ARISTA VERTICE

CICLO

VERTEX COVER INDEPENDENCIA

1

1

*

*

es origen

es destino

MALLA ALEATORIO CICLO

RUEDA

ESTRELLA NULO CICLO COMPLETO de PETERSEN


37

Existe una relación de herencia entre los distintos tipos de grafos que puede realizar automáticamente la aplicación y la clase grafo, ya que son simplemente un tipo particular de grafos que reúnen unas determinadas características.

Observamos cómo una arista está formada por dos vértices de los cuales uno será el

origen y el otro será el destino. Y que un vértice puede formar parte de varias aristas. El conjunto Vertex Cover está formado por el grafo y un conjunto de vértices que

recubren el grafo conforme al algoritmo seleccionado para el cálculo del mismo. El conjunto de vértices deberá ser un subconjunto de vértices del grafo.

Para el caso de Independencia también estará formado por un grafo y un conjunto de

nodos. Este conjunto de vértices también será un subconjunto de vértices del grafo y serán independientes entre sí.

3.2.5. Casos de uso en formato de alto nivel A continuación se detallan los casos de uso de la aplicación en formato de alto nivel.

En esta aplicación el único actor que se considera es el usuario.

Caso de Uso NuevoGrafo Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema la creación de un nuevo grafo. 2. El sistema pregunta al usuario si desea guardar el grafo que se

está editando y limpia el panel de dibujo. 3. El sistema crea un nuevo espacio de trabajo que no tendrá ni

nodos ni aristas.


38

Caso de Uso AbrirGrafo Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema abrir un grafo previamente guardado.

2. El sistema muestra al usuario el menú de abrir grafo, en el cual el usuario buscará y seleccionará el grafo que desea abrir.

3. El usuario indica al sistema el fichero que desea abrir. 4. El sistema comprueba el formato del archivo. 5. El sistema crea un nuevo espacio de trabajo en el que mostrará el

grafo guardado en el archivo seleccionado por el usuario.

Caso de Uso GuardarGrafo Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema guardar en un fichero el grafo que está editando en el espacio de trabajo.

2. El sistema muestra al usuario el menú de guardar grafo. 3. El usuario indica al sistema el nombre del fichero y la ruta en la

que se guardará. 4. El sistema guarda toda la información del grafo en un fichero en

un formato entendible por la aplicación.

Caso de Uso Salir Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema salir de la aplicación. 2. El sistema pregunta al usuario si desea guardar el grafo que está

editando. 3. Si el usuario quiere guardar el grafo se daría el caso de uso

GuardarGrafo. 4. El sistema pregunta al usuario si desea salir del sistema. 5. Si el usuario contesta afirmativamente el sistema cierra la

aplicación.


39

Caso de Uso DibujarNodo Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema la creación de un nuevo nodo. 2. El sistema muestra al usuario el cuadro de diálogo en el que

introducirá las coordenadas del nuevo vértice. 3. El usuario introduce las coordinadas en las que desea situar el

nuevo nodo. 4. El sistema añade el nodo al grafo existente y actualiza el dibujo

del grafo en el panel de dibujo.

Caso de Uso DibujarArista Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema la creación de una arista nueva. 2. El sistema muestra al usuario el cuadro de diálogo en el que

seleccionará los nodos origen y destino de la nueva arista y el peso de la misma.

3. El usuario selecciona los nodos origen y destino e introduce el peso de la arista.

4. El sistema añade la arista al grafo existente y actualiza el dibujo del grafo en el panel de dibujo.

Caso de Uso EditarNodo Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita modificar las coordenadas en la que está situado el nodo.

2. El sistema muestra al usuario el cuadro de diálogo en el que introducirá las nuevas coordenadas del vértice.

3. El usuario introduce las nuevas coordinadas en las que desea situar el nodo.

4. El sistema modifica las coordenadas del nodo y actualiza el dibujo del grafo en el panel de dibujo.


40

Caso de Uso EditarArista Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita modificar el peso de la arista. 2. El sistema muestra al usuario el cuadro de diálogo en el que

introducirá el nuevo peso de la arista. 3. El usuario introduce el nuevo peso de la arista. 4. El sistema modifica el peso de la arista y actualiza el dibujo del

grafo en el panel de dibujo.

Caso de Uso BorrarNodo Actores Usuario

Tipo Primario

Descripción

1. El usuario selecciona el nodo que desea borrar y solicita al sistema el borrado de dicho nodo.

2. El sistema marca el nodo como seleccionado y pide confirmación de la eliminación por parte del usuario.

3. El usuario confirma la eliminación del nodo seleccionado. 4. El sistema busca todas las aristas incidentes en el nodo. 5. El sistema elimina del grafo tanto el nodo seleccionado como sus

aristas incidentes y actualiza el dibujo del grafo en el panel de dibujo.

Caso de Uso BorrarArista Actores Usuario

Tipo Primario

Descripción

1. El usuario selecciona la arista que desea borrar y solicita al sistema el borrado de dicha arista.

2. El sistema marca la arista como seleccionada y pide confirmación al usuario del borrado de la arista.

3. El usuario confirma la eliminación de la arista seleccionada. 4. El sistema elimina la arista del grafo y actualiza el dibujo del

grafo en el panel de dibujo.


41

Caso de Uso DibujarGrafoNulo Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema crear un nuevo grafo nulo. 2. El sistema pregunta al usuario si desea guardar el grafo que está


GuardarGrafo. 4. El sistema solicita al usuario que introduzca el número de

vértices que contendrá el grafo. 5. El usuario introduce el número de vértices del grafo. 6. El sistema crea un nuevo grafo con el número de nodos

indicados por el usuario y sin ninguna arista.

Caso de Uso DibujarGrafoCiclo Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema crear un nuevo grafo ciclo. 2. El sistema pregunta al usuario si desea guardar el grafo que está




indicados por el usuario y el número de aristas que cumplen las condiciones de un grafo ciclo.


42

Caso de Uso DibujarGrafoEstrella Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema crear un nuevo grafo estrella. 2. El sistema pregunta al usuario si desea guardar el grafo que está




indicados por el usuario y el número de aristas que cumplen las condiciones de un grafo estrella.

Caso de Uso DibujarGrafoRueda Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema crear un nuevo grafo rueda. 2. El sistema pregunta al usuario si desea guardar el grafo que está




indicados por el usuario y el número de aristas que cumplen las condiciones de un grafo rueda.


43

Caso de Uso DibujarGrafoCompleto Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema crear un nuevo grafo completo. 2. El sistema pregunta al usuario si desea guardar el grafo que está




indicados por el usuario y el número de aristas que cumplen las condiciones de un grafo completo.

Caso de Uso DibujarGrafoMalla Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema crear un nuevo grafo completo. 2. El sistema pregunta al usuario si desea guardar el grafo que está


GuardarGrafo. 4. El sistema solicita al usuario que introduzca el alto y el ancho

del grafo malla. 5. El usuario introduce el alto y el ancho del grafo. 6. El sistema crea un nuevo grafo con el número de nodos

indicados por el usuario y el número de aristas que cumplen las condiciones de un grafo malla.


44

Caso de Uso DibujarGrafoAleatorio Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema crear un nuevo grafo aleatorio. 2. El sistema pregunta al usuario si desea guardar el grafo que está



vértices que contendrá el grafo y la probabilidad de las aristas. 5. El usuario introduce el número de nodos y la probabilidad de las

aristas. 6. El sistema crea un nuevo grafo con el número de nodos

indicados por el usuario y el número de aristas que cumplen las condiciones de probabilidad introducidas por el usuario.

Caso de Uso DibujarGrafoAleatorioCiclo Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema crear un nuevo grafo aleatorio ciclo.

2. El sistema pregunta al usuario si desea guardar el grafo que está editando.

3. Si el usuario quiere guardar el grafo se daría el caso de uso GuardarGrafo.

4. El sistema solicita al usuario que introduzca el número de vértices que contendrá el grafo y la probabilidad de las aristas.

5. El usuario introduce el número de nodos y la probabilidad de las aristas.

6. El sistema crea un nuevo grafo con el número de nodos indicados por el usuario y el número de aristas que cumplen las condiciones de probabilidad introducidas por el usuario.


45

Caso de Uso DibujarGrafodePetersen Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema crear un nuevo grafo de Petersen. 2. El sistema pregunta al usuario si desea guardar el grafo que está



vértices que contendrá el grafo y el radio del mismo. 5. El usuario introduce el número de nodos y el radio. 6. El sistema crea un nuevo grafo con el número de nodos y el

radio indicados por el usuario.

Caso de Uso CalcularVertexCoverVoraz Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema el cálculo del conjunto VertexCover del grafo que está en pantalla mediante el algoritmo voraz.

2. El sistema le ofrece la opción al usuario de ejecutar el algoritmo paso a paso o ir directamente al resultado final.

3. En ambos casos, el sistema muestra el resultado final de la ejecución del algoritmo y también ofrece al usuario la posibilidad de refinar la solución encontrada y/o de calcular la solución óptima al problema planteado.

4. El usuario selecciona refinar y/o calcular la solución óptima. 5. El sistema muestra el resultado final tras refinar o calcular la

solución óptima.


46

Caso de Uso CalcularVertexCoverVorazDistancia2 Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema el cálculo del conjunto VertexCover del grafo que está en pantalla mediante el algoritmo voraz con distancia 2.


3. En ambos casos, el sistema muestra el resultado final de la ejecución del algoritmo y también ofrece al usuario la posibilidad de calcular la solución óptima al problema planteado.

4. El usuario selecciona calcular la solución óptima. 5. El sistema muestra el resultado final tras calcular la solución

óptima.

Caso de Uso CalcularVertexCoverVorazDistancia3 Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema el cálculo del conjunto VertexCover del grafo que está en pantalla mediante el algoritmo voraz con distancia 3.


3. En ambos casos, el sistema muestra el resultado final de la ejecución del algoritmo y también ofrece al usuario la posibilidad de calcular la solución óptima al problema planteado.

4. El usuario selecciona calcular la solución óptima. 5. El sistema muestra el resultado final tras calcular la solución

óptima.


47

Caso de Uso CalcularVertexCoverAristaAleatoria Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema el cálculo del conjunto VertexCover del grafo que está en pantalla mediante el algoritmo de selección aleatoria de una arista.


3. En ambos casos, el sistema muestra el resultado final de la ejecución del algoritmo y también ofrece al usuario la posibilidad de refinar la solución encontrada.

4. El usuario selecciona refinar la solución encontrada. 5. El sistema muestra el resultado final tras refinar la solución.

Caso de Uso CalcularVertexCoverAristaOptima Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema el cálculo del conjunto VertexCover del grafo que está en pantalla mediante el algoritmo de selección de la arista óptima.


3. En ambos casos, el sistema muestra el resultado final de la ejecución del algoritmo y también ofrece al usuario la posibilidad de refinar la solución encontrada.

4. El usuario selecciona refinar la solución encontrada. 5. El sistema muestra el resultado final tras refinar la solución.


48

Caso de Uso CalcularVertexCoverK-Camaras Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema el cálculo del conjunto VertexCover del grafo que está en pantalla para un número de cámaras K.

2. El sistema solicita al usuario que introduzca el número de cámaras que desea colocar en el grafo.

3. El usuario introduce el número de cámaras a colocar en el grafo. 4. El sistema le ofrece la opción al usuario de ejecutar el algoritmo

paso a paso o ir directamente al resultado final. 5. En ambos casos, el sistema muestra el resultado final de la

ejecución del algoritmo.

Caso de Uso CalcularVertexCoverK-CamarasDistancia2 Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema el cálculo del conjunto VertexCover con distancia 2 del grafo que está en pantalla para un número de cámaras K.






49

Caso de Uso CalcularVertexCoverK-CamarasDistancia3 Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema el cálculo del conjunto VertexCover con distancia 3 del grafo que está en pantalla para un número de cámaras K.





Caso de Uso CalcularIndependencia Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema el cálculo del conjunto independiente del grafo que está en pantalla.


3. En ambos casos, el sistema muestra el resultado final de la ejecución del algoritmo.

Caso de Uso SeleccionarPesoArista1 Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema que el peso de todas las aristas que se creen a partir de ese momento tengan un peso igual a uno.

2. El sistema solicita al usuario confirmación para realizar el cambio del tipo de peso de las aristas.

3. El usuario confirma el tipo de cambio de peso. 4. El sistema realiza las modificaciones internas necesarias para

que el peso de las nuevas aristas que se dibujen sea igual a uno.


50

Caso de Uso SeleccionarPesoAristaUsuario Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema definir un peso para todas las aristas que se creen a partir de ese momento.

2. El sistema solicita al usuario confirmación para realizar el cambio del tipo de peso de las aristas y le solicita que introduzca el peso que desea.

3. El usuario confirma el tipo de cambio de peso e introduce el nuevo peso para las aristas.

4. El sistema realiza las modificaciones internas necesarias para que el peso de las nuevas aristas que se dibujen sea el especificado por el usuario.

Caso de Uso SeleccionarPesoAristaAleatorio Actores Usuario

Tipo Primario

Descripción

1. El usuario solicita al sistema que el peso de las aristas que se creen a partir de ese momento tengan un peso aleatorio definido por el sistema.

2. El sistema solicita al usuario confirmación para realizar el cambio del tipo de peso de las aristas.

3. El usuario confirma el tipo de cambio de peso. 4. El sistema realiza las modificaciones internas necesarias para

que el peso de las nuevas aristas que se dibujen sea aleatorio.

Caso de Uso CambiarColorSelección Actores Usuario

Tipo Primario

Descripción

1. El usuario selecciona la opción de cambiar el color de los elementos seleccionados del panel de dibujo.

2. El sistema le muestra el cuadro de diálogo de selección de color. 3. El usuario selecciona el color que desea. 4. El sistema realiza el cambio de color de selección.


51

Caso de Uso CambiarColorSelecciónVC Actores Usuario

Tipo Primario

Descripción

1. El usuario selecciona la opción de cambiar el color de los elementos seleccionados para Vertex Cover del panel de dibujo.

2. El sistema le muestra el cuadro de diálogo de selección de color. 3. El usuario selecciona el color que desea. 4. El sistema realiza el cambio de color de selección para Vertex

Cover.

Caso de Uso AbrirAyuda Actores Usuario

Tipo Primario

Descripción 1. El usuario solicita al sistema que le muestre la ayuda de la

aplicación. 2. El sistema muestra la ayuda al usuario.

Caso de Uso AbrirAcercaDe Actores Usuario

Tipo Primario

Descripción 1. El usuario solicita al sistema que le muestre la información

acerca de la aplicación. 2. El sistema le muestra la información al usuario.


52

3.2.6. Casos de uso en formato expandido En este apartado describiremos los casos de uso de la aplicación con un mayor nivel

de detalle.

• Crear un nuevo grafo

� Caso de uso: NuevoGrafo.

� Objetivo:

� Crear un nuevo grafo vacío, sin vértices ni aristas.

� Nivel: Primario.

� Actor Principal: Usuario.

� Precondiciones: Ninguna.

� Escenario Principal de Éxito:

Actor Sistema

1. El usuario selecciona la opción de crear un nuevo grafo vacío.

2. El sistema crea un nuevo espacio de trabajo y nuevo grafo vacío sin nodos ni aristas.

� Escenarios Alternativos: Ninguno.

� Garantías de Éxito:

� El panel de dibujo se limpia y se queda en blanco.

� Se crea un nuevo grafo sin vértices ni aristas.

� Garantías de Fracaso:

� La aplicación permanecerá en el mismo estado en que se encontraba

antes de iniciar el caso de uso.

� Puntos de extensión: Ninguno.


53

� Prioridad: Media.

� Frecuencia: Alta.

• Abrir un grafo

� Caso de uso: AbrirGrafo

� Objetivo:

� Carga en la aplicación los datos de un grafo guardado previamente.



� Precondiciones:

� Es necesario que existe el fichero a abrir, que sea legible y que

cumpla el formato específico de ficheros admitidos por el sistema.


Actor Sistema

1. El usuario selecciona la opción de abrir un grafo.

2. El sistema presenta el menú de selección del fichero.

3. El usuario busca y selecciona el fichero deseado.

4. El sistema lee e interpreta el contenido del fichero y comprueba el formato.

5. Se crea un nuevo espacio de trabajo. Caso de uso: NuevoGrafo

6. Se cargan todos los datos del grafo y se dibujan sus elementos en el área de dibujo.


54

� Escenarios Alternativos:

Actor Sistema

3. El usuario cancela la operación. 4. El sistema cierra el menú de selección de fichero.

5. El sistema vuelve al mismo estado en el que se encontraba antes de iniciar el caso de uso.


� El panel de dibujo se limpia y se dibuja el grafo contenido en el

fichero.

� Se cargan en la aplicación todos los datos relativos al grafo abierto.


� La aplicación muestra un mensaje de error indicando la causa del

fallo.



� Puntos de extensión:

� Caso de uso: NuevoGrafo



• Guardar un grafo

� Caso de uso: GuardarGrafo

� Objetivo:


55

� Guardar en un fichero todos los datos relativos al grafo que está en

ese momento en el panel de dibujo.



� Precondiciones:

� Es necesario que exista un grafo dibujado en el panel de dibujo.


Actor Sistema

1. El usuario selecciona la opción de guardar el grafo

2. El sistema presenta al usuario la ventana para seleccionar la ubicación y el nombre del archivo.

3. El usuario busca la ruta de destino e introduce el nombre del fichero.

4. El sistema crea el fichero de salida con todos los datos relativos al grafo que se encuentra en pantalla.


Actor Sistema

3. El usuario cancela la operación. 4. El sistema cierra el menú de selección de destino del fichero.



� Se han interpretado todos los datos y se ha creado correctamente el

fichero de salida.



56


fallo.






• Salir de la aplicación

� Caso de uso: Salir.

� Objetivo:

� Cerrar la aplicación





Actor Sistema

1. El usuario solicita al sistema salir de la aplicación.

2. El sistema pregunta al usuario si desea guardar el grafo actual.

3. El usuario confirma que desea guardar el grafo actual.

4. El sistema ofrece al usuario la posibilidad de guardar el grafo. Caso de uso: GuardarGrafo.

5. El sistema cierra la aplicación.


57


Actor Sistema

3. El usuario no quiere guardar el grafo actual.

4. El sistema cierra la aplicación.


� Se cerrará la aplicación guardando los datos del grafo actual si el

usuario lo considera necesario



fallo.



� Puntos de extensión:

� Caso de uso: GuardarGrafo.



• Dibujar un nuevo vértice

� Caso de uso: DibujarNodo

� Objetivo:

� Insertar un nuevo vértice en el grafo.



58


� Precondiciones:

� Debe de existir un grafo activo en la aplicación.


Actor Sistema

1. El usuario selecciona la opción de insertar un nuevo vértice en el grafo.

2. El sistema muestra al usuario un cuadro de diálogo en el que el usuario introducirá las coordenadas del nuevo vértice.

3. El usuario introduce las coordenadas del vértice.

4. El sistema añade el vértice al grafo actual y actualiza el dibujo.


Actor Sistema

3. El usuario cancela la operación. 4. El sistema cierra el cuadro de diálogo.


Actor Sistema

1. El usuario selecciona el punto del área de dibujo donde quiere pintar el vértice.

2. El usuario cliquea dos veces sobre el punto deseado para crear el vértice.

3. El sistema añade el vértice al grafo actual y actualiza el dibujo.


� Se añade el vértice y se actualizan los nuevos datos del grafo.



59




� Prioridad: Alta.


• Dibujar una nueva arista

� Caso de uso: DibujarArista.

� Objetivo:

� Añadir una nueva arista al grafo actual.



� Precondiciones:

� El grafo debe contener al menos dos nodos.


Actor Sistema

1. El usuario selecciona la opción de insertar una nueva arista en el grafo.

2. El sistema muestra al usuario un cuadro de diálogo en el que el usuario seleccionará el nodo origen y el nodo destino e introducirá el peso de la arista.

3. El usuario selecciona el origen y el destino de la arista y establece su peso.

4. El sistema añade la arista al grafo actual y actualiza el dibujo.


60


Actor Sistema



Actor Sistema

1. El usuario selecciona el vértice origen de la arista.

2. El usuario selecciona el vértice destino de la arista.

3. El sistema añade la arista al grafo actual y actualiza el dibujo.


� Se añade la arista y se actualizan los nuevos datos del grafo







• Editar un vértice

� Caso de uso: EditarNodo.

� Objetivo:

� Cambiar la situación del nodo dentro del panel de dibujo.


61



� Precondiciones:

� El grafo debe contener al menos un vértice.


Actor Sistema

1. El usuario selecciona el vértice que quiere editar.

2. El usuario selección la opción de editarlo.

3. El sistema muestra al usuario un

cuadro de diálogo en el que el usuario introducirá las nuevas coordenadas del vértice.

4. El usuario introduce las coordenadas del vértice.

5. El sistema actualiza la información en el grafo actual y actualiza el dibujo.


Actor Sistema




� Se actualizan los nuevos datos del vértice.





62



� Frecuencia: Baja.

• Editar una arista

� Caso de uso: EditarArista

� Objetivo:

� Cambiar el peso de la arista



� Precondiciones:

� El grafo debe contener al menos una arista


Actor Sistema

1. El usuario selecciona la arista que desea editar.

2. El usuario selecciona la opción de editarla.

3. El sistema muestra al usuario un

cuadro de diálogo en el que el usuario introducirá el nuevo peso de la arista.

4. El usuario introduce el nuevo peso de la arista.

5. El sistema actualiza la información en el grafo actual y actualiza el dibujo.


63


Actor Sistema




� Se actualizan los nuevos datos de la arista.







• Borrar un vértice

� Caso de uso: BorrarNodo.

� Objetivo:

� Borrar un nodo del grafo actual.



� Precondiciones:

� El grafo debe contener al menos un nodo.


64


Actor Sistema

1. El usuario selecciona el nodo que dese eliminar.

2. El usuario selecciona la opción de eliminar ese nodo.

3. El sistema pide confirmación del

borrado del nodo. 4. El usuario confirma el borrado

del nodo. 5. El sistema borra el nodo y todas

las aristas incidentes del mismo, actualizando los datos del grafo.


Actor Sistema




� Se borrar el vértice y todas sus aristas incidentes del grafo.








65

• Borrar una arista

� Caso de uso: Borrar Arista

� Objetivo:

� Borrar una arista del grafo actual.



� Precondiciones:

� El grafo debe contener al menos una arista.


Actor Sistema

1. El usuario selecciona la arista que desea eliminar.

2. El usuario selecciona la opción de eliminar la arista seleccionada

3. El sistema pide confirmación al

usuario. 4. El usuario confirma el borrado

de la arista. 5. El sistema borrar la arista

seleccionada y actualiza los datos del grafo


Actor Sistema




� Se borra la arista del grafo.


66







• Dibujar un grafo nulo

� Caso de uso: DibujarGrafoNulo.

� Objetivo:

� Crear un grafo nulo.



� Precondiciones:

� Debe de existir previamente un panel de dibujo activo.


Actor Sistema

1. El usuario solicita al sistema dibujar un grafo nulo.

2. El sistema muestra al usuario un cuadro de diálogo para que el usuario introduzca el número de nodos del grafo.

3. El usuario introduce el número de nodos del grafo.

4. El sistema crea un grafo nuevo con el número de nodos indicado por el usuario.


67


Actor Sistema




� El panel de dibujo se limpia y se crea el grafo nulo.







• Dibujar un grafo ciclo

� Caso de uso: DibujarGrafoCiclo.

� Objetivo:

� Crear un grafo ciclo.



� Precondiciones:



68


Actor Sistema

1. El usuario solicita al sistema dibujar un grafo ciclo.



4. El sistema crea un grafo nuevo ciclo con el número de nodos indicado por el usuario y el número de aristas correspondientes.


Actor Sistema




� El panel de dibujo se limpia y se crea el grafo ciclo.






� Frecuencia: Media.


69

• Dibujar un grafo estrella

� Caso de uso: DibujarGrafoEstrella.

� Objetivo:

� Crear un grafo estrella.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema dibujar un grafo estrella.



4. El sistema crea un grafo nuevo estrella con el número de nodos indicado por el usuario y el número de aristas correspondientes.


Actor Sistema





70

� El panel de dibujo se limpia y se crea el grafo estrella.







• Dibujar un grafo rueda

� Caso de uso: DibujarGrafoRueda.

� Objetivo:

� Crear un grafo rueda.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema dibujar un grafo rueda.



4. El sistema crea un grafo nuevo rueda con el número de nodos indicado por el usuario y el número de aristas correspondientes.


71


Actor Sistema




� El panel de dibujo se limpia y se crea el grafo rueda.







• Dibujar un grafo completo

� Caso de uso: DibujarGrafoCompleto.

� Objetivo:

� Crear un grafo completo.



� Precondiciones:


72



Actor Sistema

1. El usuario solicita al sistema dibujar un grafo completo.



4. El sistema crea un grafo nuevo completo con el número de nodos indicado por el usuario y el número de aristas correspondientes.


Actor Sistema




� El panel de dibujo se limpia y se crea el grafo completo.








73

• Dibujar un grafo malla

� Caso de uso: DibujarGrafoMalla.

� Objetivo:

� Crear un grafo malla.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema dibujar un grafo malla.

2. El sistema muestra al usuario un cuadro de diálogo para que el usuario introduzca el número de nodos horizontales y el número de nodos verticales del grafo.

3. El usuario introduce el número de nodos horizontales y el número de nodos verticales del grafo.

4. El sistema crea un nuevo grafo malla con el número de nodos resultado de multiplicar el número de nodos horizontales por el número de nodos verticales y el número de aristas correspondiente.


Actor Sistema




74


� El panel de dibujo se limpia y se crea el grafo malla.







• Dibujar un grafo aleatorio

� Caso de uso: DibujarGrafoAleatorio

� Objetivo:

� Crear un grafo aleatorio.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema dibujar un grafo aleatorio.

2. El sistema muestra al usuario un cuadro de diálogo para que el usuario introduzca el número de nodos del grafo y la probabilidad de las aristas.

3. El usuario introduce el número de nodos que desea en el grafo y

4. El sistema genera la posición aleatoria de cada uno de los


75

la probabilidad de 0 a 100 de las aristas.

nodos. 5. Se crea un grafo con los nodos

generados. 6. El sistema calcula, en función de

la probabilidad introducida por el usuario, si genera una arista entre cada par de vértices del grafo.

7. El sistema añade al grafo las nuevas aristas


Actor Sistema




� El panel de dibujo se limpia y se crea el grafo aleatorio.







• Dibujar un grafo aleatorio ciclo

� Caso de uso: DibujarGrafoAleatorioCiclo


76

� Objetivo:

� Crear un grafo aleatorio ciclo.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema dibujar un grafo aleatorio ciclo.

2. El sistema muestra al usuario un cuadro de diálogo para que el usuario introduzca el número de nodos del grafo y la probabilidad de las aristas.

3. El usuario introduce el número de nodos que desea en el grafo y la probabilidad de 0 a 100 de las aristas.

4. Se crea un grafo ciclo con el número de nodos indicados por el usuario.

5. El sistema calcula, en función de la probabilidad introducida por el usuario, si genera una arista entre cada par de vértices del grafo.

6. El sistema añade al grafo las nuevas aristas


Actor Sistema




77


� El panel de dibujo se limpia y se crea el grafo aleatorio ciclo.







• Dibujar un grafo de Petersen

� Caso de uso: DibujarGrafodePetersen.

� Objetivo:

� Crear un grafo de Petersen.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema dibujar un grafo de Petersen.

2. El sistema muestra al usuario un cuadro de diálogo para que el usuario introduzca el grado del ciclo y el radio del grafo.


78

3. El usuario introduce el grado del ciclo y el radio del grafo.

4. El sistema crea el grafo de Petersen con los vértices y las aristas según los datos introducidos por el usuario.


Actor Sistema




� El panel de dibujo se limpia y se crea el grafo de Petersen.







• Calcular Vertex Cover mediante el algoritmo voraz

� Caso de uso: CalcularVertexCoverVoraz.

� Objetivo:

� Calcular el conjunto Vertex Cover del grafo mediante la utilización

del algoritmo voraz.



79


� Precondiciones:

� Debe de existir previamente un grafo con al menos una arista.


Actor Sistema

1. El usuario solicita al sistema calcular el Vertex Cover del grafo en pantalla mediante el algoritmo voraz.

2. El sistema ofrece al usuario la opción de ejecutar el algoritmo paso a paso o directamente ir al resultado final en un paso.

3. El usuario selecciona la opción deseada de ejecución el algoritmo.

4. La aplicación realiza en cada paso: a. Busca el vértice que tiene un

mayor número de aristas. b. Selecciona ese vértice y todas

las aristas incidentes en él. c. Repite los pasos a y b hasta

que no queden más aristas por seleccionar, sin tener en cuenta los vértices y las aristas seleccionadas anteriormente.

5. La aplicación muestra un resumen de la ejecución del algoritmo.

6. La aplicación ofrece al usuario la posibilidad de refinar la solución encontrada.

7. El usuario selecciona la opción de refinar, si es posible, la solución encontrada anteriormente.

8. El sistema comienza el proceso de refinar la solución: a. Busca los vértices de la

solución cuyos adyacentes también están en el conjunto de la solución.

b. Elimina esos nodos de la solución encontrada.

c. Repite los pasos a y b hasta que no se pueda seguir


80

refinando. 9. El sistema muestra un resumen

con los resultados del refinamiento de la solución.

10. Se ofrece al usuario la opción de calcular la solución óptima al problema mediante fuerza bruta.

11. El usuario selecciona la opción de calcular la solución óptima.

12. El sistema calcula una solución óptima, de todas las posibles que haya, mediante fuerza bruta y muestra el resultado al usuario.


Actor Sistema

3. El usuario cancela la operación en cualquier momento de la ejecución del algoritmo.

4. El sistema cancela la ejecución, dejando el grafo en su estado inicial.


� El algoritmo Vertex Cover Voraz termina correctamente.

� Los elementos del grafo que componen el resultado se muestran de

un color diferente para mejor visualización por parte del usuario.

� Se muestra al usuario un resumen del resultado del algoritmo.








81

• Calcular Vertex Cover mediante el algoritmo voraz distancia 2

� Caso de uso: CalcularVertexCoverVorazDistancia2.

� Objetivo:


del algoritmo voraz con distancia 2.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema calcular el Vertex Cover del grafo en pantalla mediante el algoritmo voraz con distancia 2.

2. El sistema ofrece al usuario la opción de ejecutar el algoritmo paso a paso o directamente en un paso ir al resultado final.

3. El usuario selecciona la opción deseada de ejecutar el algoritmo.

4. La aplicación realiza en cada paso: a. Busca el vértice cuyo grado

más el de sus nodos adyacentes sea el mayor de todos.

b. Selecciona ese vértice y todas las aristas incidentes en él.

c. Selecciona todos los vértices adyacentes al seleccionado y todas las aristas incidentes de los vértices adyacentes.

d. Repite los pasos a, b y c hasta que no queden más aristas por seleccionar, sin tener en cuenta los vértices y las aristas seleccionadas


82

anteriormente. 5. La aplicación muestra un

resumen de la ejecución del algoritmo.





Actor Sistema




� El algoritmo Vertex Cover Voraz distancia 2 termina correctamente.











83

• Calcular Vertex Cover mediante el algoritmo voraz distancia 3

� Caso de uso: CalcularVertexCoverVorazDistancia3.

� Objetivo:


del algoritmo voraz con distancia 3.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema calcular el Vertex Cover del grafo en pantalla mediante el algoritmo voraz con distancia 3.

2. El sistema ofrece al usuario la opción de ejecutar el algoritmo paso a paso o directamente ir al resultado final en un solo paso.



más el de sus nodos adyacentes más el de los nodos adyacentes de estos, sea el mayor de todos.



d. Selecciona todos los vértices adyacentes a estos últimos y todas las aristas incidentes de los mismos

e. Repite los pasos a, b, c y d


84

hasta que no queden más aristas por seleccionar, sin tener en cuenta los vértices y las aristas seleccionadas anteriormente.






Actor Sistema




� El algoritmo Vertex Cover Voraz distancia 3 termina correctamente.









85



• Calcular Vertex Cover mediante el algoritmo Arista Aleatoria

� Caso de uso: CalcularVertexCoverAristaAleatoria.

� Objetivo:


del algoritmo de selección de una arista aleatoriamente.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema calcular el Vertex Cover del grafo en pantalla mediante el algoritmo de selección aleatoria de una arista.

2. El sistema ofrece al usuario la opción de ejecutar el algoritmo paso a paso o directamente ir al resultado final en un solo paso.


4. La aplicación realiza en cada paso: a. Elegir aleatoriamente una

arista del grafo. b. Seleccionar esa arista, los

vértices de sus extremos y las aristas incidentes en estos dos vértices.

c. Repite los pasos a y b hasta que no queden más aristas por seleccionar, sin tener en


86

cuenta las aristas seleccionadas anteriormente.







c. Repite los pasos a y b hasta que no se puede seguir refinando.

9. El sistema muestra un resumen con los resultados del refinamiento de la solución.


Actor Sistema




� El algoritmo Vertex Cover Arista Aleatoria termina correctamente.




87








• Calcular Vertex Cover mediante el algoritmo Arista Optima

� Caso de uso: CalcularVertexCoverAristaOptima.

� Objetivo:


del algoritmo de selección de la arista óptima.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema calcular el Vertex Cover del grafo en pantalla mediante el algoritmo de selección de la arista óptima.



4. La aplicación realiza en cada paso: a. Elegir la arista tal que la suma

de los grados de los vértices


88

de sus extremos sea máximo. b. Seleccionar esa arista, los

vértices de sus extremos y las aristas incidentes en estos dos vértices.

c. Repetir los pasos a y b hasta que no queden más aristas por seleccionar, sin tener en cuenta las aristas seleccionadas anteriormente.







c. Repite los pasos a y b hasta que no se puede seguir refinando.

9. El sistema muestra un resumen con los resultados del refinamiento de la solución.


Actor Sistema




89


� El algoritmo Vertex Cover Arista Óptima termina correctamente.










• Calcular Vertex Cover mediante el algoritmo K-Cámaras

� Caso de uso: CalcularVertexCoverK-Camaras

� Objetivo:

� Calcular el conjunto Vertex Cover del grafo para el número de

cámaras indicado por el usuario.



� Precondiciones:


� El grafo tiene que estar ponderado.


90


Actor Sistema

1. El usuario solicita al sistema calcular el Vertex Cover del grafo en pantalla para un número determinado de cámaras.

3. El usuario introduce en el número de cámaras que desea colocar.

2. El sistema muestra un cuadro de diálogo en el que solicita al usuario que introduzca el número de cámaras a colocar.

4. El sistema ofrece al usuario la opción de ejecutar el algoritmo paso a paso o ir directamente en un paso al resultado final.


6. La aplicación realiza en cada paso: a. Busca el vértice que tiene el

mayor grado. b. Selecciona ese vértice y todas

las aristas incidentes en él. c. Repite los pasos a y b hasta

que hayamos colocado todas las cámaras o hasta que no queden más aristas por seleccionar, sin tener en cuenta las aristas seleccionadas anteriormente.



Actor Sistema





91

� El algoritmo Vertex Cover K-Cámaras termina correctamente.










• Calcular Vertex Cover mediante el algoritmo K-Cámaras distancia 2

� Caso de uso: CalcularVertexCoverK-CamarasDistancia2.

� Objetivo:

� Calcular el conjunto Vertex Cover con distancia 2 del grafo, para el

número de cámaras indicado por el usuario.



� Precondiciones:




92


Actor Sistema

1. El usuario solicita al sistema calcular el Vertex Cover con distancia 2 del grafo en pantalla para un número determinado de cámaras.






más el de sus nodos adyacentes sea el mayor de todos.



d. Repite los pasos a, b y c hasta que hayamos colocado todas las cámaras o hasta que no queden más aristas por seleccionar, sin tener en cuenta las aristas seleccionadas anteriormente.



Actor Sistema

5. El usuario cancela la operación 6. El sistema cancela la ejecución,


93

en cualquier momento de la ejecución del algoritmo.

dejando el grafo en su estado inicial.


� El algoritmo Vertex Cover K-Cámaras distancia 2 termina

correctamente.










• Calcular Vertex Cover mediante el algoritmo K-Cámaras distancia 3

� Caso de uso: CalcularVertexCoverK-CamarasDistancia3

� Objetivo:

� Calcular el conjunto Vertex Cover con distancia 3 del grafo para el

número de cámaras indicado por el usuario.




94

� Precondiciones:




Actor Sistema

1. El usuario solicita al sistema calcular el Vertex Cover distancia 3 del grafo en pantalla para un número determinado de cámaras.



4. El sistema ofrece al usuario la opción de ejecutar el algoritmo paso a paso o ir directamente en un paso al resultado final.



más el de sus nodos adyacentes más el de los nodos adyacentes de estos sea el mayor de todos.



d. Selecciona todos los vértices adyacentes a estos últimos y todas las aristas incidentes de los mismos.

e. Repite los pasos a, b, c y d hasta que hayamos colocado todas las cámaras o hasta que no queden más aristas por seleccionar, sin tener en cuenta las aristas seleccionadas anteriormente.


95



Actor Sistema




� El algoritmo Vertex Cover K-Cámaras distancia 3 termina

correctamente.










• Calcular el conjunto Independiente

� Caso de uso: CalcularIndependencia.


96

� Objetivo:

� Calcular el conjunto Independiente del grafo mediante la utilización

del algoritmo voraz.



� Precondiciones:



Actor Sistema

1. El usuario solicita al sistema calcular el Conjunto Independiente del grafo en pantalla mediante el algoritmo voraz.



4. La aplicación realiza en cada paso: a. Buscan en cada paso el

vértice de menor grado. b. Selecciona ese vértice, y

elimina para siguientes pasos de la búsqueda los nodos adyacentes al seleccionado.

c. Repite los pasos a y b hasta que no queden más vértices por seleccionar, sin tener en cuenta ni los vértices seleccionados ni lo eliminados en pasos anteriores.



97


Actor Sistema




� El algoritmo de Independencia termina correctamente.










• Establecer el peso de las aristas a 1

� Caso de uso: SeleccionarPesoArista1

� Objetivo:

� Asignar a todas las arista que se generen en el grafo un peso de valor

igual a 1.



98




Actor Sistema

1. El usuario selecciona que todas las aristas que se creen en la aplicación a partir de ese momento tengan un peso igual a 1.

2. El sistema solicita confirmación al usuario para realizar el cambio.

3. El usuario confirma el cambio de peso de las aristas.

4. El sistema realiza las modificaciones internas necesarias para que el peso de las nuevas aristas que se dibujen tengan un valor igual a 1.


Actor Sistema

3. El usuario cancela la operación. 4. El sistema vuelve al mismo estado en el que se encontraba antes de iniciar el caso de uso.


� Todas las aristas que se generen en el grafo a partir de esta selección

tendrán un peso cuyo valor será igual a 1.








99

• Establecer un peso fijo para las aristas

� Caso de uso: SeleccionarPesoAristaUsuario

� Objetivo:

� Asignar a todas las arista que se generen en el grafo un peso

determinado, definido por el usuario.





Actor Sistema

1. El usuario selecciona que todas las aristas que se creen en la aplicación a partir de ese momento tengan un peso determinado definido por él.

2. El sistema solicita confirmación al usuario para realizar el cambio y le solicita que introduzca el nuevo peso para las aristas.

3. El usuario introduce el nuevo peso para las aristas y confirma el cambio.

4. El sistema realiza las modificaciones internas necesarias para que el peso de las nuevas aristas que se dibujen tengan un valor igual al definido por el usuario.


Actor Sistema




100


tendrán un peso cuyo valor será igual al peso definido por el usuario.







• Asignar peso aleatorio a las aristas

� Caso de uso: SeleccionarPesoAristaAleatorio

� Objetivo:

� Asignar pesos aleatorios a las aristas que se generen en el grafo.





Actor Sistema

1. El usuario selecciona la opción para que el peso de todas las aristas que se generen a partir de ese momento sea aleatorio.

2. El sistema solicita confirmación al usuario para realizar el cambio.

3. El usuario confirma el cambio de peso de las aristas.

4. El sistema realiza las modificaciones internas necesarias para que el peso de las nuevas aristas que se dibujen sea aleatorio.


101


Actor Sistema




tendrán un peso aleatorio.







• Cambiar el color de los elementos seleccionados

� Caso de uso: CambiarColorSeleccion.

� Objetivo:

� Cambiar el color que se utilizará para resaltar el elemento

seleccionado (Vértice o Arista) dentro del área de dibujo.





102


Actor Sistema

1. El usuario solicita al sistema cambiar el color de los elementos seleccionados en el área de dibujo.

2. El sistema muestra al usuario el menú de selección de color.

3. El usuario selecciona el nuevo color.

4. El sistema realiza las modificaciones internas necesarias para cambiar el color de los elementos seleccionados dentro del área de dibujo.


Actor Sistema

3. El usuario cancela la operación. 4. El sistema cierra el menú de selección.



� El color de la arista o vértice seleccionado será el elegido por el

usuario.





� Prioridad: Baja.



103

• Cambiar el color de los elementos seleccionados para Vertex Cover

� Caso de uso: CambiarColorSeleccionVC.

� Objetivo:

� Cambiar el color que utilizará para resaltar los elementos

seleccionados (Vértices y Arista) por los algoritmos de la aplicación





Actor Sistema

1. El usuario solicita al sistema cambiar el color de los elementos seleccionados por los algoritmos de la aplicación.

2. El sistema muestra al usuario el menú de selección de color.

3. El usuario selecciona el nuevo color.

4. El sistema realiza las modificaciones internas necesarias para cambiar el color de los elementos seleccionados por los algoritmos.


Actor Sistema

3. El usuario cancela la operación. 4. El sistema cierra el menú de selección.




104

� El color de las aristas y los vértices seleccionados por los algoritmos

de la aplicación será el elegido por el usuario.







• Abrir el fichero de ayuda

� Caso de uso: AbrirAyuda.

� Objetivo:

� Abrir el fichero con el manual de la aplicación.





Actor Sistema

1. El usuario pulsa la ayuda de la aplicación.

2. El sistema abre el fichero con el manual de la aplicación




105

� Se muestra al usuario el manual de la aplicación.







• Mostrar información de la aplicación

� Caso de uso: AbrirAcercaDe.

� Objetivo:

� Mostrar al usuario la información referente a la aplicación.





Actor Sistema

1. El usuario solicita al sistema ver la información de la aplicación

2. El sistema muestra la información de la aplicación con un mensaje emergente.



� Se muestra al usuario la información referente a la aplicación.


106








107

3.3. DISEÑO DE BAJO NIVEL Para el diseño de bajo nivel se ha elegido la representación mediante diagramas de

colaboración en el que se podrán observar las interacciones entre los distintos objetos de las distintas clases que existen en la aplicación. Además de estos diagramas también se utilizarán los diagramas de clases para ilustrar cómo se relacionan las distintas clases entre sí, las operaciones que tiene cada una de ellas y sus atributos.

3.3.1. Diagramas de Colaboración Los diagramas de colaboración son una alternativa para mostrar los escenarios a los

diagramas de secuencia. Un diagrama de colaboración muestra las interacciones entre distintos objetos. No muestra el tiempo como una dimensión aparte, por lo que resulta necesario etiquetar tanto la secuencia de mensajes como los hilos ocurrentes.

Debido a la gran cantidad de operaciones que realiza el sistema y para no realizar

una documentación excesivamente extensa y pesada, sólo se incluyen en esta memoria los diagramas de colaboración de las operaciones más significativas.

Por claridad y para evitar excesivos detalles que puedan dificultar el entendimiento

de los diagramas de colaboración, se han considerado encapsular todos los paneles que forman la interfaz gráfica en una sola clase. Esta clase llamada PanelPrincipal engloba toda la parte gráfica de la aplicación.


108

3.3.1.1. Crear un nuevo grafo

Figura 3.3: Diagrama de colaboración: Crear un nuevo grafo Este diagrama muestra las operaciones que deben realizarse para crear un nuevo

grafo vacío. Este grafo vacío no contendrá ni vértices ni aristas. Si en el panel de dibujo existe algún grafo, se borra y se prepara el área de dibujo

para dibujar el nuevo grafo. Así mismo se limpian los datos que se muestran en el panel de información, dejándolo preparado para mostrar los datos del nuevo grafo.

Una vez que está preparado el entorno de trabajo se crea el nuevo grafo (vacío sin

nodos ni aristas) con el que el usuario podrá trabajar. A continuación se refresca el área de dibujo.


109

3.3.1.2. Abrir un grafo

Figura 3.4: Diagrama de colaboración: Abrir un grafo La operación se inicia cuando el usuario solicita a la aplicación que desea abrir un

fichero con los datos de un grafo guardado previamente. El sistema abre el fichero indicado por el usuario, lo lee línea a línea y analiza e

interpreta su contenido. A continuación se crea un grafo vacío al cual se le van añadiendo los elementos indicados en el fichero. Este fichero tiene que tener un formato correcto y legible por la aplicación, en caso contrario se le indicará el error al usuario.

El grafo obtenido del fichero se muestra en el área de edición, la cual se refresca

para mostrar el grafo y a su vez se muestran los datos del grafo abierto en el panel de información.


110

3.3.1.3. Guardar un grafo

1.2

: ob

ten

erD

ato

s(gra

fo)

2:

gu

ard

arG

:= C

rea

r()

3:

fich

ero

:= e

scri

bir

Da

tos(

gra

fo)

Figura 3.5: Diagrama de colaboración: Guardar un grafo El usuario indica al sistema que desea guardar el grafo que se está editando en el

panel de dibujo en el fichero especificado. El sistema recupera el grafo del área de edición y sus datos del panel de información

y a continuación crea el fichero en el que se guardará la información. Toda la información referente a los vértices y aristas que forman el grafo así como otros datos adicionales se guardan en el fichero en el formato concreto.

Una vez terminado, el usuario puede continuar trabajando con el grafo que tiene en

pantalla.


111

3.3.1.4. Dibujar un nuevo vértice

Principal pPrincipal: PanelPrincipal pDibujo: PanelDibujo

DibujarNodo(coordX, coordY)

1.1: grafo:= obtenerGrafo()

3.1: repintar()

pInfo: PanelInfo

grafo: Grafo

1: pPrincipal:= obtenerPanelPrincipal()

3: dibujarGrafo(grafo)

Figura 3.6: Diagrama de colaboración: Dibujar un nuevo vértice Para añadir un nodo lo primero que hacemos es recuperar del panel de dibujo el

grafo en el cual vamos a añadir el nodo. Una vez recuperado el grafo, se añade el nodo y actualizamos tanto los datos sobre

el grafo y el nodo que aparecen en el panel de información, como el dibujo del propio grafo en el panel de dibujo.

3.3.1.5. Dibujar una nueva arista


DibujarArista(origen,destino,peso )


3.1: repintar()

pInfo: PanelInfo

grafo: Grafo



Figura 3.7: Diagrama de colaboración: Dibujar una nueva arista


112

Para el caso de insertar una nueva arista en el grafo, la manera de proceder será la misma que para el caso de un vértice.

Lo primero que hacemos es recuperar el grafo del área de dibujo y a continuación

añadimos la arista actualizando los datos del panel de información y refrescando el dibujo del grafo del panel de edición.

3.3.1.6. Editar un vértice

Figura 3.8: Diagrama de colaboración: Editar un vértice La edición de un vértice consiste en cambiar sus coordenadas de situación dentro del

panel de dibujo. Para ello recuperamos del panel de dibujo el grafo y de éste el nodo seleccionado

para su edición. A continuación establecemos sus nuevas coordenadas y una vez aceptado el cambio, actualizamos los datos del grafo en el panel de información y refrescamos el dibujo del grafo con el cambio del nodo.


113

3.3.1.7. Editar una arista

Figura 3.9: Diagrama de colaboración: Editar una arista Cuando se edita una arista lo que hacemos es cambiar su peso. Al igual que en el caso de la edición de un vértice, el proceso de la edición pasa

primero por recuperar el grafo que está en el panel de dibujo y a continuación la arista seleccionada. Una vez hecho el cambio del peso de la arista, se actualizan los datos tanto en el panel de información como en el panel de dibujo.


114

3.3.1.8. Borrar un vértice

Figura 3.10: Diagrama de colaboración: Borrar un vértice La operación se inicia cuando el usuario le indica el sistema que desea borrar el

nodo seleccionado y que es pasado como parámetro. Lo primero que hacemos es obtener el grafo del panel de dibujo y buscar el nodo

que se desea borrar. Una vez encontrado el nodo se pueden presentar dos casos:

• El nodo tiene aristas incidentes: En este caso, primero tenemos que buscar todas las aristas incidentes en el nodo y eliminarlas. Una vez hecho esto ya podemos eliminar el vértice seleccionado.

• El nodo no tiene ninguna arista incidente: Solamente habría que borrar el nodo especificado.

En cualquiera de los dos casos, a continuación se refresca el área de edición para ver

cómo queda el grafo y se actualizan los datos del grafo en el panel de información.


115

3.3.1.9. Borrar una arista


BorrarArista(arista)


3.1: repintar()

pInfo: PanelInfo

grafo: Grafo



Figura 3.11: Diagrama de colaboración: Borrar una arista Este caso se inicia cuando el usuario selecciona una arista e indica que desea

borrarla. Para ello se recupera el grafo y se borra la arista indicada por el usuario en el

parámetro de entrada. Una vez borrada la arista se redibuja el grafo para observar cómo queda tras la eliminación de la arista. También se actualizan los datos del grafo que se muestran en el panel de información.

3.3.1.10. Dibujar un grafo predefinido A continuación se muestran los diagramas de colaboración de los nueve tipos de

grafos predefinidos que permite crear la aplicación. Estos tipos de grafo son: Nulo, ciclo, estrella, rueda, completo, malla, aleatorio, aleatorio ciclo y de Petersen.

La creación de estos tipos de grafos sigue el mismo orden ya explicado en el

diagrama de colaboración “Crear un nuevo grafo” con la diferencia de los parámetros pasados y la creación de objetos de cada una de la clases de los grafos indicados.


116

Figura 3.12: Diagrama de colaboración: Dibujar un grafo nulo

Figura 3.13: Diagrama de colaboración: Dibujar un grafo ciclo

Figura 3.14: Diagrama de colaboración: Dibujar un grafo estrella


117

1:

rue

da

:= G

rafo

Ru

ed

a(n

um

_ve

rt)

3.2

: esta

ble

cerD

ato

sGra

fo(ru

ed

a)

Figura 3.15: Diagrama de colaboración: Dibujar un grafo rueda

Figura 3.16: Diagrama de colaboración: Dibujar un grafo completo


118

Figura 3.17: Diagrama de colaboración: Dibujar un grafo malla

Figura 3.18: Diagrama de colaboración: Dibujar un grafo aleatorio


119

Figura 3.19: Diagrama de colaboración: Dibujar un grafo aleatorio ciclo

Figura 3.20: Diagrama de colaboración: Dibujar un grafo de Petersen Como hemos indicado antes y viendo los diagramas de colaboración de los

diferentes tipos de grafos, las diferencias entre ellos son:

• Nulo: Se pasa como parámetro el número de vértices del grafo y se crea un objeto de la clase GrafoNulo.

• Ciclo: Se crea un objeto de la clase GrafoCiclo con el número de vértices pasado como parámetro.

• Estrella: Se pasa como parámetro el número de vértices del grafo y se crea un objeto de la clase GrafoEstrella.


120

• Rueda: El objeto de la clase GrafoRueda creado, tendrá el número de vértices que se le pasa como parámetro.

• Completo: Como parámetro se pasa el número de vértices del grafo y con él se crea el objeto de la clase GrafoCompleto.

• Malla: Para crear el objeto de la clase GrafoMalla se pasa como parámetro el número de nodos horizontales y el número de nodos verticales.

• Aleatorio y Aleatorio Ciclo: Se le pasa como parámetro el número de vértices y la probabilidad (de 0 a 100) de las aristas entre los vértices. Con estos datos se crea el GrafoAleatorio/GrafoAleatorioCiclo.

• De Petersen: Se pasa como parámetro el número de nodos del ciclo y el radio del grafo.

3.3.1.11. Calcular Vertex Cover mediante el algoritmo Voraz

3.2: escribirA

reaTexto(d

atos)

2.1 *: nodo:=buscarVertice()

1.2: establecerPanelVCVoraz()

2.2

*: e

stable

cerSe

leccio

nad

o(n

od

o)

2: a

lgo

ritmo

VC

Vo

raz(g

r afo

)

2.4

*: e

stab

lece

rSel

ecci

onad

a(ar

ista

s)

2.3

*:

ari

sta

s :=

ob

ten

erA

rist

asd

eN

od

o(n

od

o)

Figura 3.21: Diagrama de colaboración: Calcular Vertex Cover mediante algoritmo Voraz


121

Para poder ejecutar el algoritmo sobre el grafo, lo primero que tenemos que hacer es recuperar el grafo del área de edición. Una vez recuperado, se le muestra al usuario el panel de ejecución del algoritmo que ha seleccionado con los botones de navegación.

El grafo es pasado al algoritmo el cual busca en cada paso el nodo que tiene un

mayor número de aristas. Una vez encontrado ese vértice se selecciona. A continuación se buscan todas las aristas incidentes en ese vértice y se marcan también como seleccionadas. Este proceso se repite hasta que se han seleccionado todas las aristas como contiene el grafo.

Toda la información generada por la ejecución del algoritmo se irá mostrando en el

área de texto del panel de información, así como un resumen con el resultado final del algoritmo. Así mismo se refrescará el área de edición para visualizar con mejor claridad los pasos que se han dado.

Este diagrama de colaboración es extensible para el caso “Calculo de Vertex Cover

mediante el algoritmo voraz con distancia 2”. En este caso se selecciona el vértice cuyo grado más el de sus adyacentes es el mayor de todos. Una vez seleccionado el nodo y sus aristas, marcamos también como seleccionados los nodos y las aristas con distancia 2, es decir, marcamos los nodos adyacentes al seleccionado y las aristas de estos.

Para el caso de “Calculo de Vertex Cover mediante el algoritmo voraz con distancia

3” sería igual pero llegaríamos a cubrir hasta una distancia 3, es decir, en cada paso marcaríamos el nodo seleccionado, sus adyacentes como los adyacentes de estos últimos, así como las aristas de todos los vértices seleccionados.


122

3.3.1.12. Calcular Vertex Cover mediante el algoritmo Arista Óptima

2.1 *: arista:=buscarAristaOptima()

2.3 *: establecerSeleccionado(nodoOrg)

2.4 *: establecerSeleccionado(nodoDest)

Figura 3.22: Diagrama de colaboración: Calcular Vertex Cover mediante el algoritmo Arista Optima

Para poder ejecutar el algoritmo, recuperamos el grafo del panel de dibujo y se

muestra al usuario el panel de ejecución del algoritmo en el que estarán los botones con los que el usuario podrá ejecutarlo.

El algoritmo buscará en cada paso la arista tal que la suma de los grados de los

vértices de sus extremos sea máxima. Una vez encontrada la arista, la marcará como seleccionada, así como los vértices de sus extremos. A continuación se obtendrán del grafo las aristas incidentes en los nodos origen y destino de la arista seleccionada y se marcarán como seleccionadas.

Todos los pasos ejecutados en el algoritmo se irán mostrando en el panel de dibujo

cambiando el color de los elementos seleccionados y se irán detallando en el panel de


123

información. Al finalizar la ejecución se mostrará un resumen del algoritmo en el panel de información.

Este diagrama de colaboración es extensible para el caso “Calcular Vertex Cover

mediante el algoritmo Arista Aleatoria”. La única diferencia estriba en el método de selección de la arista en cada paso del algoritmo, que en este caso, elige una arista aleatoriamente.

3.3.1.13. Calcular Verter Cover mediante el algoritmo K-Cámaras

Extensible para el cálculo de Vertex Cover mediante el algoritmo K-Cámaras con distancia 2 y con distancia 3.

2.1 *: nodo:=buscarVertice()

Figura 3.23: Diagrama de colaboración: Calcular Vertex Cover mediante algoritmo K-Cámaras


124

Para el cálculo del conjunto Vertex Cover mediante este algoritmo, tenemos que pasar como parámetro el número de cámaras que se desean colocar.

El proceso de ejecución de este algoritmo es el mismo que para el caso “Calcular

Vertex Cover mediante el algoritmo voraz”: En cada paso del algoritmo buscamos el vértice de mayor grado. Una vez encontrado lo seleccionamos y se obtienen sus aristas incidentes, las cuales también se seleccionan. La diferencia llega en la condición de parada del algoritmo. En este caso el algoritmo finaliza bien cuando se han seleccionado todas las aristas del grafo o cuando se han colocado el número de cámaras especificado por el usuario.

Al finalizar la ejecución del algoritmo se mostrará en el área de texto del panel de

información, el resumen de la ejecución del algoritmo. Al igual que para el caso del algoritmo Voraz, este caso es extensible para el

“Calculo de VertexCover mediante el algoritmo K-Cámaras distancia 2” y para el caso con distancia 3.


125

3.3.1.14. Calcular el conjunto Independiente

Figura 3.24: Diagrama de colaboración: Calcular el conjunto Independiente Para calcular el conjunto independiente, al igual que en el resto de algoritmos, lo

primero que tenemos que hacer es recuperar el grafo en edición y mostrar el panel de ejecución del algoritmo en la parte inferior de la aplicación.

Una vez pasado el grafo al algoritmo, se busca en cada paso el vértice de menor

grado. Una vez encontrado, se selecciona como perteneciente al conjunto independiente y se buscan sus nodos adyacentes, los cuales se marcan como “no seleccionable” para los siguientes pasos.

Este proceso se repite hasta que no queden más vértices por seleccionar. Al finalizar

el algoritmo se mostrará el resultado en el grafo con distintos colores así como en el panel de información se mostrará un resumen de la ejecución.


126

3.3.1.15. Establecer peso de las aristas aleatorio

Figura 3.25: Diagrama de colaboración: Establecer peso de las aristas aleatorio Lo primero que hacemos para poder cambiar el tipo de peso de las aristas del grafo,

es recuperar el grafo del área de edición. Una vez recuperado el grafo le cambiamos el tipo de peso a peso aleatorio y a

continuación recorremos todas las aristas que contiene el grafo haciendo dos cosas: Por un lado modificamos el atributo que especifica el tipo de peso de la arista y por otro se establece el peso aleatorio generado para esa arista.

El siguiente paso es refrescar el área de edición para poder visualizar los cambios y

a continuación actualizamos los datos del grafo en el panel de información. Este diagrama de colaboración es extensible para los casos “Establecer peso de las

aristas igual a uno” y para “Establecer un peso fijo para todas las aristas”.


127

3.3.1.16. Cambiar color de los elementos seleccionados

Figura 3.26: Diagrama de colaboración: Cambiar color de los elementos seleccionados El cambio de color de los elementos seleccionados en el panel de dibujo lo

realizamos haciendo la modificación necesaria en un atributo del grafo. Para ello, lo primero que tenemos que hacer es recuperar el grafo del área de

edición, tras lo cual modificamos ese atributo del grafo con el color con el que queremos que aparezcan los elementos seleccionados.

Una vez hecho el cambio, refrescamos el panel de dibujo para observar los cambios. Este diagrama de colaboración es extensible para el caso “Cambiar el color de los

elementos seleccionados para Vertex Cover”, con el cambio que el atributo que se modifica en el grafo es el que indica el color para los elementos seleccionados para Vertex Cover.


128

3.3.2. Diagramas de Clases Los diagramas de clases son un tipo de diagrama estático que describe la estructura

de un sistema, mostrando sus clases, atributos y relaciones entre ellos. También muestran la visibilidad entre los objetos de las distintas clases.

A continuación se detallan varios diagramas de clases para reflejar con mayor

claridad las relaciones entre las clases y señalaremos los métodos más relevantes de cada una de ellas.


129

3.3.2.1. Aplicación-Interfaz

Figura 3.27: Diagrama de clases: Aplicación-Interfaz


130

La clase Principal contiene la función main que se encarga de poner en funcionamiento todo el entorno de trabajo de la aplicación.

Desde esta clase se crea la clase FramePrincipal. Este frame contiene todo los

elementos que conforma el entorno de trabajo sobre los que interactúa el usuario de la aplicación.

La clase BarraMenu implementa el menú de la aplicación desde el cual podemos

acceder a todas las funcionalidades que se nos ofrecen. A todas estas funcionalidades también podemos acceder de una manera más rápida y cómoda desde una barra de herramientas implementada por la clase BarraHerramientas.

La clase PanelPrincipal engloba las distintas partes que conforma el área principal

de trabajo. Estas partes son:

• Área de Dibujo: Esta área es la zona de dibujo y edición del grafo con el que se está trabajando. En esta área el usuario podrá añadir vértices y aristas, así como moverlos, editarlos y eliminarlos. Esta área de trabajo está implementada por la clase PanelDibujo.

• Área o Panel de Información: En esta parte de la zona de trabajo se muestra

al usuario toda la información relativa al grafo con el que está trabajando. Se muestra información referente al número de vértices y aristas que forman el grafo, así como información del vértice o arista que el usuario tiene seleccionado en un momento puntual. En este panel también se mostrará al usuario información relativa a los algoritmos que se ejecuten sobre el grafo, mostrando al final de cada uno, un resumen con los datos de la ejecución. Esta área de información está implementada por la clase PanelInfo.

• Panel de ejecución de Algoritmos: Este panel será el que utilice el usuario para la ejecución de los algoritmos. Dependiendo del algoritmo que el usuario desee ejecutar, la aplicación mostrará al usuario en este panel, un menú con los pasos y opciones que puede realizar. Este panel está implementado por la clase PanelPie.

El control de estas tres partes que forman el área principal de trabajo se lleva a cabo mediante la clase Dibujar. Esta clase controla todos los eventos de ratón sobre al área de edición del grafo. Con estos eventos de ratón podemos crear vértices y aristas, así como moverlos, editarlos y eliminarlos del grafo. También se controla que la interacción entre


131

estas tres partes sea correcta para que la información mostrada del grafo sea correcta y para que la ejecución de los algoritmos mediante las opciones ofrecidas en el panel de ejecución se haga y se muestre de manera correcta al usuario.


132

3.3.2.2. Grafo

Figura 3.28: Diagrama de clases: Grafo


133

Podemos considerar la clase Grafo como la clase más importante de la aplicación, ya que todo el funcionamiento de la misma gira en torno al grafo que se está dibujando. Entre sus atributos podemos destacar:

• nodos: Lista de nodos que componen el grafo. • numNodos: Nº de nodos del grafo.

• aristas: Lista de las aristas que contiene el grafo. • numAristas: Nº de aristas del grafo.

• color, colorVC y colorVC2: colores personalizables por el usuario para una mejor visualización del grafo y las soluciones a los distintos algoritmos.

• tipoPeso: Tipo de peso de las aristas. El tipo de peso de las aristas puede ser de tres tipos: Igual a 1, peso fijo seleccionado por el usuario o peso aleatorio.

Respecto a los métodos de la clase grafo podemos destacar los siguientes:

• añadirNodo: Añade un nodo al grafo. • añadirArista: Añade una arista al grafo.

• borrarNodo: Borra un nodo del grafo y todas las aristas incidentes en él. • borrarArista: Borrar una arista del grafo. • obtenerAristas: Nos devuelve todas las aristas incidentes en un nodo.

• vaciarGrafo: Vacía el grafo de nodos y aristas. • pintarGrafo: Se encarga de pintar el grafo en el área de edición.

• A su vez la clase dispone de varios métodos “obtener…” u “establecer…” que nos permiten tanto consultar los valores de distintos atributos como poder modificarlos.

La clase Nodo representa los vértices o nodos que contiene u grafo. Entre sus

atributos más importantes están:

• coordX y coordY: Atributos que indican la coordenada X y la coordenada Y, respectivamente, donde se sitúa el nodo en el área de trabajo.

• id: Es el identificador único del nodo.

• grado: Indica el número de aristas incidentes en ese nodo. • seleccionado: Indica si el nodo está seleccionado o no en ese momento. • seleccionadoVC y seleccionadoVC2: Estos atributos indican si el nodo ha

sido seleccionado para la solución de alguno de los algoritmos que se pueden ejecutar.

De entre sus métodos podemos destacar:


134

• establecerCoordX y establecerCoordY: Establece las coordenadas de situación del nodo dentro del área de edición.

• establecerId: Establece el identificador único del nodo. • establecerGrado: Establece el grado del nodo.

• establecerSeleccionado, establecerSeleccionadoVC y establecerSeleccionadoVC”: Con estos tres métodos modificamos el estado de selección del vértice en cada momento.

• De los anteriores métodos tenemos sus respectivos “obtener…” con los que conseguimos recuperar el valor de los atributos deseados.

• pintarNodo: Pinta el vértice en el área de edición. La clase Arista representa las aristas del grafo y sus atributos más importantes son:

• id: Identificador único de la arista.

• origen: Nodo origen de la arista. • destino: Nodo destino de la arista.

• tipoPeso: Tipo de peso de la arista. El tipo de peso de una arista puede ser de tres tipos: Igual a 1, peso fijo seleccionado por el usuario o peso aleatorio.

• peso: Peso de la arista.

• seleccionada: Indica si la arista está seleccionada ese momento. • seleccionadaVC y seleccionadaVC2: Estos atributos indican si la arista ha

sido seleccionada por alguno de los algoritmos de la aplicación. Los métodos más importantes de la clase Arista son:

• establecerOrigen y establecerDestino: Establecen respectivamente, el nodo origen y el nodo destino de la arista.

• establecerId: Establece el identificador único de la arista. • establecerPeso: Asigna el peso determinado por la aplicación a la arista.

• establecerTipoPeso: Establece que tipo de peso va a tener la arista. Pede ser peso aleatorio, peso fijo asignado por el usuario o peso igual a uno.

• establecerSeleccionada, establecerSeleccionadaVC y establecerSeleccionadaVC2: Con estos tres métodos modificamos el estado de selección de la arista tanto en la edición como en la ejecución de los algoritmos.

• Al igual que en la clase Nodo, todos los método “establecer…” tienen su respectivo “obtener…” con los que se nos proporciona la información deseada.

• pintarArista: Pinta la arista en el área de edición.


135

En el gráfico anterior también observamos las clases que representan a los distintos

tipos de grafo predefinidos que puede dibujar la aplicación. Estos grafos por su relación de generalización con la clase Grafo heredan de ella todos sus métodos y atributos.


136

3.3.2.3. Algoritmos

Figura 3.29: Diagrama de clases: Algoritmos


137

La aplicación podrá ejecutar distintos algoritmos tanto para el cálculo de VertexCover como para el conjunto Independiente.

Todos estos algoritmos se ejecutarán a través de las opciones ofrecidas en el panel

inferior de la aplicación. Este panel está representado por la clase PanelPie la cual nos ofrecerá, dependiendo del algoritmo elegido, las distintas opciones de ejecución de dicho algoritmo.

Como se puede ver en el diagrama de clases, la clase PanelPie contiene un atributo

por cada tipo de algoritmo que podemos ejecutar. Cada uno de estos atributos es un panel con las opciones de ejecución disponibles para el algoritmo seleccionado.

La clase PanelPie, dispone de los métodos “esteblecerPanel…” necesarios para

mostrar u ocultar estos paneles de ejecución, así como las llamadas ActionListener a los algoritmos de ejecución. Estos paneles, uno por cada algoritmo distinto que ejecuta la aplicación, contienen los botones de ejecución que se ofrecen para ese algoritmo determinado.

Toda la información generada por la ejecución de los algoritmos se mostrará en un

cuadro de texto del PanelInfo. Todos los cambios realizados en el grafo para una mejor visualización de la

ejecución del algoritmo se harán a través de la clase PanelDibujo y de su método repintar.

El atributo areaTexto representa el área en el cual se mostrará esa información de

ejecución de los algoritmos. Para escribir en esta área se utilizará el método escribirAreaTexto y para limpiarla y dejarla vacía cuando no se esté ejecutando ningún algoritmo utilizaremos el método limpiarAreaTexto.

Cada algoritmo que puede ejecutar la aplicación está representado por una clase.

Estas clases son las siguientes:

• AlgoritmoVCVoraz: Clase que implementa el algoritmo Vertex Cover con una heurística voraz. En cada paso selecciona el vértice de mayor grado no seleccionado en los pasos anteriores del algoritmo.

• AlgoritmoVCVorazDist2: Implementa el algoritmo Vertex Cover voraz con distancia 2. En cada pasado selecciona el vértice, no seleccionado en los pasos anteriores del algoritmo, cuyo grado más el de sus adyacentes sea el mayor de todos.


138

• AlgoritmoVCVorazDist3: Implementa el algoritmo Vertex Cover con heurística voraz y con distancia 3. En cada paso selecciona el vértice, no seleccionado en los pasos anteriores, cuyo grado más el de sus adyacentes más el de los nodos adyacentes de estos últimos sea el mayor de todos.

• AlgoritmoVCAristaAleatoria: Esta clase implementa el algoritmo de selección de una arista aleatoriamente para el cálculo del conjunto Vertex Cover. En cada paso selecciona una arista de manera aleatoria entre las no seleccionadas anteriormente.

• AlgoritmoVCAristaOptima: Esta clase implementa el algoritmo de selección de una arista para el cálculo del conjunto Vertex Cover. En cada paso selecciona la arista de mayor grado entre las no seleccionadas anteriormente.

• AlgoritmoK-Camaras: Clase que implementa el algoritmo que calcula el conjunto Vertex Cover para el número de cámaras indicado por el usuario. En cada paso selecciona el vértice de mayor grado no seleccionado en los pasos anteriores, hasta un número máximo de vértices determinado por el número de cámaras.

• AlgoritmoK-CamarasDist2: Implementa el algoritmo de las K-Cámaras con distancia 2.

• AlgoritmoK-CamarasDist3: Implementa el algoritmo de las K-Cámaras con distancia 3.

• AlgoritmoIndependencia: Clase que implementa el algoritmo de cálculo del conjunto independiente del grafo con una estrategia voraz. El algoritmo selecciona en cada paso el vértice de menor grado de entre los que no se han seleccionado en los pasos anteriores.


139

3.3.2.4. Funcionalidades

Figura 3.30: Diagrama de clases: Funcionalidades


140

Todas las funcionalidades que ofrece la aplicación giran en torno a la clase PanelPrincipal.

La clase AbrirGrafo nos permite abrir en la aplicación un grafo guardado

previamente. Lee línea a línea la información contenida en el fichero y carga la información contenida en la aplicación, que se encargará de mostrarla en la zona de dibujo.

La clase GuardarGrafo nos permite guardar el grafo actual del área de edición en un

archivo. Recoge los datos de todos los nodos y de todas las aristas que forman el grafo y los va escribiendo en el fichero elegido por el usuario de forma que sea legible para la aplicación.

Ambas clases se apoyan en la clase EntradaSalida que se encarga de toda la gestión

de archivos con el sistema operativo. La clase NuevoNodo es la encargada de añadir un nuevo nodo al grafo que está en el

área de edición. La clase NuevaArista añade una nueva arista al grafo entre los dos nodos

seleccionados por el usuario. NuevoGrafo limpia el área de edición dejándolo en blanco para que el usuario pueda

dibujar un nuevo grafo, ya sea predefinido dibujado directamente sobre el panel de dibujo. También limpia los paneles de información inicializando los datos del nuevo grafo.

La clase EditarElemento nos permite modificar el elemento seleccionado, ya sea un

vértice o una arista. Si es un vértice nos permitirá cambiar su situación proporcionando las nuevas coordenadas. Si es una arista nos permitirá cambiar el peso de la misma.

La clase BorrarElemento nos permitirá eliminar el elemento seleccionado del área

de edición. Si es un vértice, borrará ese vértice y todas sus aristas incidentes. Si es una arista, sólo borrará la arista.

La clase PesoArista es la encargada de gestionar el tipo de peso de las aristas del

grafo. Este peso puede ser de tres tipos: Peso aleatorio, peso fijo indicado por el usuario o peso igual a uno.


141

La clase SeleccionarColor nos permite cambiar el color de los elementos seleccionados en el área de dibujo como el color de los elementos del grafo que forman parte de la solución de un algoritmo.

Nota: Para no complicar la representación, se han omitido en los diagramas ciertas

clases de menor importancia.


142


143

4. ESTUDIO COMPARATIVO Para la realización del estudio comparativo se han generado diferentes grafos de

prueba aleatorios con los valores de vértices y aristas descritos a continuación. El número de vértices de las muestras ha ido desde 20 a 120 con un incremento de

20 vértices, es decir, el número de vértices ha tomado los siguientes valores n = {20, 40, 60, 80, 100, 120}.

Para la generación aleatoria de aristas hemos utilizado seis probabilidades p = {0.1,

0.2, 0.3, 0.4, 0.5, 0.6}. Se han generado diez grafos aleatorios para cada combinación del número de

vértices y probabilidad de las aristas, lo que nos lleva a un total de 360 grafos de prueba. Sobre cada grafo se han ejecutado los siguientes algoritmos de la aplicación:

• Vertex Cover, vértice de mayor grado.

• Vertex Cover, vértice de mayor grado con distancia 2. • Vertex Cover, vértice de mayor grado con distancia 3.

• Vertex Cover, arista aleatoria. • Vertex Cover, arista óptima o de mayor grado. • Independencia, vértice de menor grado.

La unidad de medida utilizada en este estudio comparativo es la cardinalidad del

conjunto solución encontrado por cada algoritmo, sin tener en cuenta otros datos como podría ser el tiempo de ejecución empleado.


144

4.1. Comparativa 1: Número de vértices fijo. En esta comparativa se puede comparar los resultados de la ejecución de los

algoritmos para el conjunto de grafos generado, con un valor fijo del número de vértices.

Se incluyen tanto las tablas de resultados como las gráficas de los mismos.

Figura 4.1: Comparativa: Nº de vértices = 20

0,1 0,2 0,3 0,4 0,5 0,6

Vértice Max Grado 7,6 10,2 12,6 13,6 15,4 16

Vértice Max Grado dist 2 4,6 3,8 2,8 2,6 2,2 2

Vértice Max Grado dist 3 2,8 1,8 1,2 1 1 1

Arista Aleatoria 13,2 15,6 17,6 17,6 18,8 18,4

Arista Optima 11,2 13,2 15,2 15,6 16,8 16,4

Independencia 12,4 9 6,6 6,2 4,8 4


145


0,1 0,2 0,3 0,4 0,5 0,6

Vértice Max Grado 21 28,6 30,6 32,6 33,6 35,2


Vértice Max Grado dist 3 3,6 1 1 1 1 1

Arista Aleatoria 30 35,6 38 37,6 38,6 38,8

Arista Optima 27,2 32 33,6 36 36 37,6

Independencia 18,6 12 9,6 7 6,2 4,6


146


0,1 0,2 0,3 0,4 0,5 0,6

Vértice Max Grado 36,8 44,6 49,2 51,6 53,2 54,6

Vértice Max Grado dist 2 8 6,8 5 4,2 3,6 2,8


Arista Aleatoria 50 56 57,2 57,6 58,8 58,4

Arista Optima 45,6 48 54 53,2 56 55,6

Independencia 22,6 14,8 10,2 8,4 6,6 5,4


147


0,1 0,2 0,3 0,4 0,5 0,6


Vértice Max Grado dist 2 10,2 7 5 4,6 3,8 3



Arista Optima 61,2 68,8 72,4 75,2 74,4 76

Independencia 24,4 17 11,4 9 7,2 5,4


148


0,1 0,2 0,3 0,4 0,5 0,6

Vértice Max Grado 71 83,2 88 90,8 92,6 93,4

Vértice Max Grado dist 2 12,8 8,6 6 4,6 3,8 3

Vértice Max Grado dist 3 2 1 1 1 1 1

Arista Aleatoria 91,6 95,6 98 97,2 98,8 98,8

Arista Optima 82 90,8 92 93,6 95,2 96,4

Independencia 28,2 17,2 12,4 9,2 7,6 6


149


0,1 0,2 0,3 0,4 0,5 0,6

Vértice Max Grado 89 102 107,2 109,8 111,8 113,6

Vértice Max Grado dist 2 13,8 8 6,4 5 4 3,2


Arista Aleatoria 109,2 116 117,2 116,4 117,6 118,8

Arista Optima 98,8 109,2 112 114 115,2 115,2

Independencia 31,2 17 12,2 9,8 7,2 6,8


150

4.2. Comparativa 2: Probabilidad de las aristas fija.

En este apartado se comparan los distintos tipos de algoritmos de la aplicación sobre

el conjunto de grafos aleatorios generados, con un valor fijo de la probabilidad de las aristas.

Figura 4.7: Comparativa: Probabilidad de las aristas = 0.1

20 40 60 80 100 120

Vértice Max Grado 7,6 21 36,8 54,8 71 89

Vértice Max Grado dist 2 4,6 6,8 8 10,2 12,8 13,8

Vértice Max Grado dist 3 2,8 3,6 2,4 2,2 2 2

Arista Aleatoria 13,2 30 50 71,6 91,6 109,2

Arista Optima 11,2 27,2 45,6 61,2 82 98,8

Independencia 12,4 18,6 22,6 24,4 28,2 31,2


151


20 40 60 80 100 120

Vértice Max Grado 10,2 28,6 44,6 63,8 83,2 102

Vértice Max Grado dist 2 3,8 5,2 6,8 7 8,6 8


Arista Aleatoria 15,6 35,6 56 74,8 95,6 116

Arista Optima 13,2 32 48 68,8 90,8 109,2

Independencia 9 12 14,8 17 17,2 17


152


20 40 60 80 100 120

Vértice Max Grado 12,6 30,6 49,2 67,8 88 107,2

Vértice Max Grado dist 2 2,8 3,8 5 5 6 6,4


Arista Aleatoria 17,6 38 57,2 76,8 98 117,2

Arista Optima 15,2 33,6 54 72,4 92 112

Independencia 6,6 9,6 10,2 11,4 12,4 12,2


153


20 40 60 80 100 120





Arista Optima 15,6 36 53,2 75,2 93,6 114

Independencia 6,2 7 8,4 9 9,2 9,8


154


20 40 60 80 100 120





Arista Optima 16,8 36 56 74,4 95,2 115,2

Independencia 4,8 6,2 6,6 7,2 7,6 7,2


155


20 40 60 80 100 120

Vértice Max Grado 16 35,2 54,6 74,4 93,4 113,6

Vértice Max Grado dist 2 2 2 2,8 3 3 3,2



Arista Optima 16,4 37,6 55,6 76 96,4 115,2

Independencia 4 4,6 5,4 5,4 6 6,8


156


157

5. MANUAL DE USUARIO La aplicación se ha diseñado como una herramienta para la generación y

visualización de grafos. Esto implica que la estructura de la interfaz se asemeje a un programa típico de edición de gráficos en la que la mayor parte de la pantalla la ocupa el área de dibujo.

5.1. PANTALLA PRINCIPAL Al iniciar la aplicación se muestra la pantalla principal desde la cual el usuario podrá

realizar todas las acciones que permite la aplicación. Esta pantalla principal se compone de los siguientes elementos:

• Barra de menú

• Barra de herramientas • Panel de dibujo

• Panel de información • Panel de ejecución

Figura 5.1: Pantalla principal de la aplicación


158

A continuación describiremos las distintas partes que forma la aplicación.

5.2. BARRA DE MENÚ A continuación se describirán los distintos menús de la aplicación con una breve

explicación de su función.

Figura 5.2: Barra de menú

5.2.1. Archivo Permite gestionar las funciones relacionadas con los documentos así como salir de la

aplicación.

Figura 5.3: Menú archivo

• Nuevo: Limpia el panel de dibujo de cualquier elemento y lo prepara para dibujar un nuevo grafo.

• Abrir: Abre un documento previamente guardado que contiene la información necesaria para poder dibujar el grafo. La extensión de los archivos ha de ser .vc

• Guardar: Guarda en un archivo el grafo que está actualmente en el panel de dibujo en el formato determinado de la aplicación.

• Salir: Finaliza y cierra la aplicación.

5.2.2. Edición En este menú se podrán editar los elementos que componen el grafo.


159

Figura 5.4: Menú edición

• Editar: Permite cambiar información relativa al elemento del grafo que está en ese momento seleccionado en el panel de dibujo.

o Si es un nodo, permite cambiar su posición. o Si es una arista, permite cambiar su peso.

Figuras 5.5 y 5.6: Cuadros de edición

• Borrar: Borra del grafo el elemento seleccionado en ese determinado instante.

o Si es una arista, la borra y actualiza los datos del grafo. o Si es un nodo, borra el nodo y todas sus aristas incidentes y actualiza

los datos del grafo.

5.2.3. Grafo En este menú encontraremos las opciones de poder insertar nodos y aristas al grafo

actual que está en el panel de dibujo. También permite dibujar una serie de grafos predefinidos en los que se le solicita al usuario, dependiendo del tipo de grafo, que introduzca los datos necesarios tales como, número de vértices, probabilidad de las aristas,…


160

Figura 5.7: Menú grafo

• Dibujar nodo: Permite al usuario insertar un nuevo nodo en el grafo actual del panel de dibujo. El usuario debe introducir las coordenadas del nuevo nodo.

Figura 5.8: Cuadro insertar nodo

• Dibujar arista: Permite al usuario insertar una nueva arista entre dos nodos existentes en el grafo del panel de dibujo. El usuario debe seleccionar los nodos origen y destino y el peso de la arista.

Figura 5.9: Cuadro crear arista


161

• Dibujar grafo nulo: Se crea un grafo sin aristas con el número de nodos indicado por el usuario.

• Dibujar grafo ciclo: Crea un grafo ciclo con el número de nodos indicado por el usuario.

• Dibujar grafo estrella: Crea en el panel de dibujo un grafo estrella con el número de nodos introducido por el usuario.

Figura 5.10: Cuadro crear grafo estrella

• Dibujar grafo rueda: Permite al usuario crear un grafo rueda con el número de nodos indicado.

• Dibujar grafo completo: Dibuja en el panel de dibujo un grafo completo con el número de nodos indicado por el usuario y las aristas necesarias para conectar entre si todos los nodos.

• Grafo malla: Permite al usuario crear un grafo malla con el número de nodos resultante de multiplicar el nº de nodos horizontales por el nº de nodos verticales.

Figura 5.11: Cuadro crear grafo malla

• Grafo aleatorio: Crea un grafo aleatorio con el número de vértices indicado por el usuario y con un número aleatorio de aristas según la probabilidad introducida por el usuario.


162

Figura 5.12: Cuadro crear grafo aleatorio

• Grafo aleatorio ciclo: Permite al usuario crear un grafo aleatorio como el anterior, salvo que los vértices están ordenados en círculo para una mejor visualización.

• Grafo de Petersen: Permite al usuario dibujar un grafo de Petersen, para lo cual el usuario tendrá que introducir el número de nodos del ciclo y el radio del grafo.

Figura 5.13: Crear grafo de Petersen

5.2.4. Calcular En este menú encontramos todos los algoritmos que se pueden ejecutar sobre el

grafo del panel de dibujo. No vamos a profundizar sobre este menú debido a que los algoritmos que se pueden

ejecutar están explicados con anterioridad en los puntos 2.4.2 y 2.5.2.


163

Figura 5.14: Menú calcular

5.2.5. Configuración En este menú el usuario encontrará diversas opciones de configuración de la

aplicación que se detallan a continuación:

Figura 5.15: Menú configuración

• Peso de arista: El usuario puede elegir entre tres tipos de pesos para las aristas del grafo:

o Peso arista = 1. Es la opción por defecto, y establece el peso de todas las aristas a 1.

o Peso definido por el usuario: El peso de todas las aristas del grafo es el mismo y fijo, y es definido por el usuario.

o Peso aleatorio: El peso de las aristas es aleatorio y su valor está entre 1 y 100.

Figura 5.16: Tipo de peso de las aristas


164

• Color de selección: El usuario puede seleccionar el color de los elementos

del grafo que se seleccionan para su edición.

Figura 5.17: Cuadro de selección del color de selección

• Color de selección para VC: El usuario puede seleccionar el color que tomarán los elementos del grafo durante la ejecución de alguno de los algoritmos cuando sean solución del mismo.

5.2.6. Ayuda En este menú el usuario puede seleccionar ver la documentación referente a la

aplicación, así como acceder a la información acerca de la aplicación.

Figura 5.18: Menú ayuda

5.3. BARRA DE HERRAMIENTAS La barra de herramientas ofrece la mayoría de las opciones presente en la barra de

menú, de una forma más rápida y más intuitiva, ya que los iconos de representación son los mismos que aparecen en los menús.


165

Figura 5.19: Barra de herramientas

5.4. PANEL DE DIBUJO Es la parte principal de la aplicación ya que sobre ella se podrá dibujar, editar,

borrar y trabajar sobre el grafo.

Figura 5.20: Grafo dibujado en el panel de dibujo

Sobre esta área de dibujo se podrá dibujar directamente un nodo haciendo doble clic

sobre cualquier punto. También es posible añadir aristas. Para ello se selecciona con el ratón el nodo origen y a continuación el nodo destino.

También se ha habilitado un menú contextual cuando se pulsa con el botón derecho

sobre cualquier elemento del grafo. Este menú nos permitirá editar o borrar el elemento seleccionado.


166

Figura 5.21: Menú contextual

5.5. PANEL DE INFORMACIÓN En este panel de información aparece toda la información útil para el usuario de la

aplicación. Se compone de diferentes partes: Por un lado tenemos el área de información referente al grafo.

Figura 5.22: Información del grafo En esta parte se informa del número de nodos y aristas del grafo. Estos datos se

actualizan de manera automática al añadir o borrar elementos del grafo. También tenemos una parte que nos informa del nodo del grafo que está

seleccionado.

Figura 5.23: Información del nodo La información que se nos muestra es el número identificativo del nodo, su posición

en el panel de dibujo y el grado de dicho nodo. Si en el grafo estuviera seleccionada una arista en vez de un nodo, se nos mostraría

la información de dicha arista.


167

Figura 5.24: Información de la arista La información que se muestra de la arista seleccionada es: El identificador de la

arista, los vértices origen y destino y el peso de la misma. También tenemos un área de ejecución donde se muestra toda la información que se

va generando en la ejecución de los algoritmos.

Figura 5.25: Información de ejecución Al finalizar la ejecución de un algoritmo, se mostrará un cuadro resumen con los

datos obtenidos de dicha ejecución.


168

5.6. PANEL DE EJECUCIÓN Este panel situado en la parte inferior de la aplicación, permite al usuario gestionar

la ejecución de los algoritmos. Esta barra se compone de una serie de botones de ejecución, que cambian según el

algoritmo seleccionado y muestran las opciones de cada uno.

Figura 5.26: Panel de ejecución

Estos botones, que no aparecen en todos los algoritmos, son:

• Siguiente: Ejecuta el siguiente paso del algoritmo.

• Final: Completa la ejecución del algoritmo desde el paso actual hasta el final del mismo.

• Refinar: Una vez encontrada una solución, permite refinar la solución encontrada.

• Óptimo: Busca la solución óptima del grafo mediante fuerza bruta.

• Volver: Cancela la ejecución actual del algoritmo.


169

6. CONCLUSIONES El cálculo del conjunto Vertex Cover y del Conjunto Independiente de un grafo son

problemas típicos de la Teoría de Grafos. En este proyecto se ha intentado abordar estos dos temas con la realización de una

aplicación que implementa varios de estos algoritmos de cálculo sobre grafos. En los resultados obtenidos podemos observar que en general se obtienen “buenas”

soluciones, sobre todo para grafos pequeños, en los que la aproximación a la solución óptima es mayor.

En este proyecto se trata principalmente el cálculo del conjunto Vertex Cover y se

introduce el estudio del Conjunto Independiente, tema extenso e interesante, el cual merecería la pena profundizar en proyectos futuros.

También sería interesante continuar el estudio de algoritmos Vertex Cover los

cuales nos puedan seguir acercando a soluciones óptimas, sobre todo para grafos grandes.


170


171

7. BIBLIOGRAFÍA [1] S. Canales, G. Hernandez, M Martins, I. Matos, Distance domination,

guarding and vertex cover for maximal outerplanar graphs, XV Spanish Meeting on Computational Geometry, 2013.

[2] A. Dharwadker, The Vertex Cover Algorithm, http://www.dharwadker.org/vertex_cover/, 2006.

[3] A. Dharwadker, The Independent Algorithm, http://www.dharwadker.org/independent_set/, 2006.

[4] X. Ferré Grau, M. I. Sanchez Segura, Desarrollo Orientado a Objetos con UML, Facultad de Informática, Universidad Politécnica de Madrid, 2001.

[5] J. García de Jalón y otros, Aprenda Java, Escuela Superior de Ingenieros Industriales de San Sebastián, Universidad de Navarra, 2000.

[6] G. Hernández Peñalver, Algoritmos aproximados. Vertex Cover, Facultad de Informática, Universidad Politécnica de Madrid.

[7] G. Hernández Peñalver, Teoría de Grafos, Facultad de Informática, Universidad Politécnica de Madrid, 2005.

[8] D. Moshkovitz, Algoritmos de Aproximación, Universidad del País Vasco. [9] J. Sanchez, Java 2, http://www.jorgesanchez.net, 2004. [10] E. W. Weisstein, Vertex Cover, Wolfram Web Resource,

http://mathworld.wolfram.com/VertexCover.html. [11] E. W. Weisstein, Independence Set, Wolfram Web Resource,

http://mathworld.wolfram.com/IndependenceSet.html.


172


173


174

universidad politÉcnica de madrid facultad de … · en 1736 y versaba sobre el problema de los...

Documents