Software sobre Grafos desarrollado por alumnos

(Si desea algún programa no disponible vía web puede solicitarlo enviando un email a gregoriohpenalver@upm.es)

General

• AlGraf. Herramienta de visualización de algoritmos sobre grafos, desarrollada en Visual Basic. (Fátima Rico, José Luis Santisteban, Abraham Fernández, 2001, Julián Ramírez, 2002)

• ProRouting. Aplicación que permite visualizar muchos grafos de proximidad de conjuntos de puntos del plano, evaluar estrategias de ruteo sobre ellos, calcular su dilación y estudiar sus características de spanners. (David Ramos, julio 2004, José María Gil, julio 2007, Víctor Chavero, 2009, Edgar Méndez, 2014)
  

• IAGraph. Aplicación interactiva para la visualización de algoritmos sobre grafos. Están implementados algoritmos de búsqueda en grafos y digrafos, conectividad, caminos mínimos y coloración. (Juan Carlos Delgado y Abraham Iniesto, mayo 2012). Manual de usuario.

Nociones básicas

• Interfaz grafo simple – matriz de adyacencia. Estudio de la relación entre un grafo simple y su matriz de adyacencia. (Rogerio Carballo da Costa, mayo 2001)
• Sucesiones gráficas y certificados de árboles. Se presentan invariantes numéricos de los grafos: la sucesión de grados para grafos cualesquiera y los certificados de árboles que resuelven el problema de isomorfismo para árboles. (Eugenio Rabadán, junio 2004)
• Sucesiones gráficas. Aplicación que detecta si una sucesión es gráfica y dibuja uno de los grafos simples que la realizan. (Francisco Javier Rodríguez Pascual, 2003)
• Vértices corte. Aplicación que detecta todos los vértices-corte de un grafo. (Alejandro Balcells, 2004)
• Etiquetados garbosos y mágicos. Aplicación interactiva que permite etiquetar grafos para obtener etiquetados garbosos, mágicos, conservativos y consecutivos. (Cristina Ruiz, julio 2008).
• Isomorfismo de grafos. (Pedro Redondo González, 2003)

Árboles

• Visualización interactiva de árboles generadores óptimos. Aplicación interactiva para la construcción de árboles generadores que optimizan los criterios de peso y uniformidad. Se puede trabajar interactivamente con los algoritmos de Prim, Kruskal y Boruvka para el peso total y con diferentes estrategias para la uniformidad y la capacidad máxima. (Daniel Guijarro Enríquez, julio 2009)
• Problemas de optimización en árboles generadores. Aplicación que resuelve, de forma aproximada, diferentes problemas de optimización en árboles generadores, en particular MCRT (Minimum Cost Routing Tree) y árboles de Steiner. También presenta los algoritmos de Prim, Kruskal y Boruvka. (Mª Dolores Rodríguez y Antonio Díaz, enero 2009)
• Código de Prüfer de un árbol etiquetado. Aplicación que construye el código de un árbol etiquetado y el árbol correspondiente a un código dado. (Alberto García, 2003)
• Centro y centroide de un árbol. Aplicación que calcula el centro y el centroide de un árbol con pesos en las aristas. (Carlos Vilas Arias, 2004)
• Visualización de los algoritmos de Prim y Kruskal. Ejemplos de aplicación de los algoritmos de Prim y Kruskal para la obtención del árbol generador de peso mínimo. (Victorino Sanz, 2002)

Caminos y distancias

• Caminos de longitud mínima en grafos y digrafos. Implementación de los algoritmos de Dijkstra, Floyd y Bellman-Ford que construyen los caminos de longitud mínima en grafos y digrafos ponderados. (Rafael Sánchez Bodoque, julio 2001)
• Camino mínimo en un entorno poligonal. Una aplicación del algoritmo de Dijkstra en el campo de la robótica. (Nuria Navarro, sept. 2001)
• Algoritmo de Dijkstra. Programa interactivo para el estudio del algoritmo de Dijkstra. (Manuel Delgado, mayo 2008)
• Medidas de centralidad y excentricidad. Programa interactivo que permite analizar las diferentes medidas de centralidad, excentricidad y periferia para grafos ponderados. (Alejandro Rodríguez, julio 2007)
• Distancia en un grafo ponderado. Excentricidad, centro, radio y diámetro. (Javier Perozo Arza, 2004)
• Dimensión métrica de grafos. Una aplicación para calcular los conjuntos de vértices resolutivos y la dimensión métrica de árboles y grafos. (Javier Díaz Hernández, septiembre 2009)

Recorridos y trayectorias

• Problema del Viajante. Aplicación que resuelve de forma aproximada el Problema del Viajante utilizando diferentes estrategias. (Pedro Díaz Jiménez, 2004)
• Descomposiciones de grafos. Se presentan varias descomposiciones de grafos: la descomposición de un grafo completo en ciclos hamiltonianos, la descomposición del conjunto de aristas en recorridos tipo euleriano, en caminos de longitud dos y en caminos de longitud tres. (Vanesa Mancebo, diciembre 2003)

Emparejamientos

• Emparejamientos. Aplicación interactiva que permite construir emparejamientos en grafos bipartidos y en grafos generales, todos ellos sin pesos. (Raquel Pérez, enero 2005)
• Estabilidad en emparejamientos. Aplicación interactiva que construye emparejamientos estables. (Julio Ortega, septiembre 2017)

Coloración

• Coloración en triangulaciones. Estudio teórico sobre coloración de triangulaciones, con análisis especial de algunas variantes sobre grafos periplanos maximales.  (Guillermo Esteban Pascual, junio 2017)
• Coloración de grafos. Listas y Juegos. Aplicación para colorear de forma interactiva los vértices de un grafo con diferentes estrategias de tipo secuencial. También se puede colorear con listas de colores y jugar a colorear o impedir colorear un grafo. (Javier Muñoz, febrero 2010)
• Juegos sobre coloración de grafos. Juegos de dos jugadores en que se colorean los vértices y las aristas de un grafo. (Manuel Delgado, mayo 2008)
• Coloración defectiva. Algoritmos para colorear grafos ponderados cuando se dispone de menos colores de los necesarios para colorear correctamente. El objetivo es minimizar el peso de las aristas conflictivas. (Félix Rodríguez, mayo 2006)
• Coloración por conjuntos independientes. Herramienta que permite colorear los vértices de un grafo utilizando estrategias de búsqueda de conjuntos independientes. (David Rodríguez Pacheco, 2004)
• Coloración de aristas. Herramienta para colorear las aristas de un grafo atendiendo a estrategias secuenciales o de independencia. (Patricia Pascual Montes, 2004)

Dominación y recubrimiento

• Dominación romana, dominación potencial y “zero forcing”, Estudio teórico sobre estas variantes de dominación con análisis especial sobre los grafos periplanos maximales. (Sandra Ranilla Cortina, junio 2017)
   
• GTapp: Dominating sets in triangulations. Estudio experimental de algunas variantes de dominación en grafos correspondientes a triangulaciones de conjuntos de puntos del plano (Héctor Moreno Cervera, junio 2016)
   
• Dominación en grafos periplanos maximales. Estudio teórico y exhaustivo de diferentes variantes de dominación en grafos periplanos maximales que, geométricamente, corresponden a las triangulaciones de polígonos. (Irene Castro Delgado, junio 2016)
   
• Dominación local en grafos, Algoritmos que resuelven el problema de dominación en grafos con estrategias locales, sin conocimiento de la globalidad del grafo.  (Jorge Durán, noviembre 2014)
   
• Recubrimiento, recubrimiento a distancia e independencia en grafos, Algoritmos que implementan diferentes estrategias para resolver el problema de recubrimiento por vértices en un grafo. (Oscar Díaz Martín, julio 2013)
   
• Recubrimiento y Dominación: Algoritmos sobre grafos de proximidad y grafos aleatorios, Estrategias de recubrimiento y dominación  sobre grafos de proximidad. (José Luis Capilla Lara, julio 2012)

Trazado de grafos (Graph Drawing)

• Representación de Visibilidad (Graph Drawing). Aplicación que permite construir la representación geométrica de digrafos acíclicos planos por segmentos verticales y horizontales (representación de visibilidad) y los trazados que se derivan.  (Walber González Sedeño, julio 2013)
• Trazado de árboles (Tree Drawing). Aplicación que representa de forma visual árboles y árboles binarios en el plano, atendiendo a diferentes estrategias de visualización: niveles, radial, HV, winding, poligonal óptima, etc. (Alejandro Balcells, febrero 2010)
• Trazado de digrafos por niveles (Layered Drawing). Aplicación que presenta algunos ejemplos de trazado de digrafos por capas, con diferentes estrategias en cada uno de los pasos de la representación. (Daniel Rodríguez Troitiño, 2008)
• Inmersión rectilínea de un grafo plano. Todo grafo plano se puede dibujar siempre de forma que sus aristas sean segmentos que no se corten entre sí. (Ana Belén Pérez Juy, octubre 2002)
• Trazado de árboles binarios. (Francisco Javier Merino Guardiola, 2008)
• Trazado de un grafo por capas. Se representan grafos dirigidos por niveles. (Ángel Ortiz Gil, mayo 2004)