 |
Grafos
|
|
ENLACES
INTERESANTES
Software
desarrollado por alumnos de la Facultad de Informática
- 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 Melgar,
mayo 2009)
- 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
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)
- PathFinder
El algoritmo de Dijkstra interactivo
(Miguel Ángel López Martínez)
- Centralidad
y excentricidad en grafos.
Herramienta 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)
- EulerPathSolver
Herramienta interactiva para la construcción de recorridos eulerianos utilizando el algoritmo de Fleury
(Leila Navascués)
- 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)
- COLORACIÓN
- 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
robusta.
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)
- TRAZADO DE GRAFOS (GRAPH DRAWING)
- 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 Drawings)
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)