Cómo funciona Graph Labs

Un recorrido de dos minutos para conocer el estudio con un grafo listo:

1. 1.En la pestaña Construir, haz clic en Red ponderada. El grafo se carga y se encuadra automáticamente.
2. 2.Ve a Ejecutar y elige Algoritmo de Dijkstra, en Caminos mínimos.
3. 3.En Raíz / origen, selecciona A; en Vértice de destino, selecciona F.
4. 4.Haz clic en Ejecutar Dijkstra y usa Paso siguiente para ver cómo se cierra cada vértice y se relaja cada arista tensa en la tabla dist y pred.
5. 5.En el último paso, el camino mínimo A → C → F, de peso 11, aparece en morado, y la tarjeta de Conclusiones resume las distancias finales.

Solo hay una herramienta activa a la vez, resaltada en la barra superior. El cursor cambia de forma para indicar cuál está en uso, y una sugerencia junto a la barra explica qué hacer.

• Seleccionar y mover

  Herramienta por defecto. Haz clic en un vértice o una arista para seleccionarlo, arrastra los vértices para reubicarlos y arrastra el fondo para mover la vista.

• Añadir vértice

  Cada clic en un punto vacío crea un vértice ahí. Las etiquetas siguen la secuencia A, B, C, ..., Z, A1, B1, ..., saltando siempre las que ya están en uso.

• Conectar vértices

  Haz clic en el vértice de origen y luego en el de destino. Entre los dos clics, una línea discontinua sigue al cursor. Esc cancela.

• Eliminar elemento

  Haz clic en un vértice o una arista para borrarlo. Eliminar un vértice elimina también todas las aristas unidas a él.

• Deshacer

  Revierte el último cambio del grafo. Guarda hasta 60 cambios.

• Rehacer

  Vuelve a aplicar un cambio deshecho.

• Vaciar grafo

  Borra todos los vértices y aristas. Se puede revertir con Deshacer.

• Nuevas aristas no dirigidas

  Las aristas creadas en el lienzo nacen no dirigidas (por defecto).

• Nuevas aristas dirigidas

  Las aristas creadas en el lienzo nacen con flecha, del origen al destino.

• Sugerencia de posición

  Cuando está activada, cada nueva arista provoca un ajuste fino del dibujo. La preferencia se guarda.

• Reorganizar ahora

  Aplica el ajuste de posición de inmediato, una sola vez.

Arrastra el fondo para mover la vista y usa la rueda del ratón (o el gesto de pellizcar en el trackpad y en el móvil) para acercar y alejar, siempre centrado en el punto bajo el cursor. El zoom va del 30% al 260%. Los botones de la esquina inferior derecha ofrecen el mismo control:

• Acercar

  Aumenta el zoom un 25%, manteniendo el centro.

• Alejar

  Reduce el zoom un 20%, manteniendo el centro.

• Encuadrar grafo

  Ajusta el zoom y la posición para que el grafo entero quepa en la pantalla.

Al cargar un grafo de ejemplo, se encuadra automáticamente. Las aristas paralelas entre el mismo par de vértices, como A → B y B → A, se dibujan curvas para no superponerse.

Una vez ejecutado un algoritmo, cada vértice y arista recibe un estado en cada paso. La leyenda de la esquina inferior izquierda del lienzo resume el significado de los colores:

• No explorado

  Estado inicial: el algoritmo todavía no ha alcanzado el elemento.

• Marcado

  Alcanzado pero aún no procesado: está en la cola, la pila o la frontera.

• En análisis

  Elemento examinado en el paso actual. Los vértices en análisis laten para llamar la atención.

• Explorado / en la solución

  Procesamiento terminado o elemento aceptado en la solución (árbol, orden, emparejamiento).

• Descartado

  Rechazado por el algoritmo, como una arista que formaría un ciclo. Las aristas descartadas se ven discontinuas.

• Camino

  Resultado resaltado al final: camino mínimo, camino aumentante o camino euleriano.

• Anillo discontinuo en el color principal

  Vértice de partida. La etiqueta encima indica RAÍZ o, en los algoritmos de flujo, FUENTE.

• Anillo discontinuo morado

  Vértice de llegada: DESTINO, o SUMIDERO en los algoritmos de flujo.

• 1/6

  Etiqueta bajo el vértice

  Valor del vértice en el paso actual: TD/TF en la búsqueda en profundidad, nivel en la búsqueda en anchura, dist en Dijkstra, color en la coloración, s y t en el flujo.

• 3/5

  Rótulo de la arista

  Muestra el peso. Durante la ejecución puede dar paso a otro valor, como flujo/capacidad en los algoritmos de flujo o el orden de recorrido en Fleury.

• Contorno de color

  Agrupa vértices del mismo conjunto: componentes fuertemente conexas en Kosaraju, árboles del bosque en Kruskal, clases de color en la coloración.

Los ejemplos reproducen casos usados en clase, cada uno pensado para resaltar el comportamiento de determinados algoritmos. Cargar un ejemplo sustituye el grafo actual (se puede deshacer), borra la raíz y el destino elegidos y encuadra el dibujo.

• Red ponderada

  Grafo no dirigido y ponderado, con peso w(e) > 0 en cada arista: la base para el AEM (Prim y Kruskal) y para Dijkstra.

  PrimKruskalDijkstra

• Grafo dirigido con ciclos

  Grafo dirigido con tres componentes fuertemente conexas, para el algoritmo de Kosaraju.

  KosarajuDFS

• Red de flujo

  Red de flujo: grafo dirigido con capacidad u(e) en cada arista, de la fuente s = S al sumidero t = T.

  Ford-Fulkerson

• Pesos negativos

  Grafo dirigido con aristas de peso negativo y sin ciclos de peso negativo, para Bellman-Ford y Floyd-Warshall.

  Bellman-FordFloyd-Warshall

• Grafo simple

  Grafo simple no dirigido, sin pesos relevantes: ideal para las búsquedas en anchura y en profundidad.

  BFSDFS

• Grafo euleriano

  Ejemplo 1 de las diapositivas de grafos eulerianos: todos los vértices tienen grado par, así que existe un circuito euleriano.

  Fleury

• Grafo semieuleriano

  Ejemplo 2 de las diapositivas: exactamente dos vértices de grado impar (5 y 6), así que existe un camino euleriano abierto.

  Fleury

• Red con cuello de botella

  La red de las diapositivas de Edmonds-Karp: dos aristas de capacidad 100 unidas por una de capacidad 1, que expone la debilidad de elegir caminos arbitrariamente.

  Ford-FulkersonEdmonds-KarpDinic

• Precedencia de actividades

  Grafo acíclico de las diapositivas de ordenación topológica: la fabricación de una estantería, desde comprar las tablas hasta transportarla.

  KahnOrden topológico (DFS)

• Emparejamiento con flores

  Grafo general con dos ciclos de longitud impar: exige la contracción de flores (blossoms) del algoritmo de Edmonds.

  Edmonds

• Coloración de vértices

  Grafo con χ(G) = 3 en el que el orden alfabético hace que el método voraz use 4 colores, mientras que Welsh-Powell encuentra 3.

  Coloración vorazWelsh-Powell

• Contraejemplo de Welsh-Powell

  Grafo bipartito, luego χ(G) = 2, en el que Welsh-Powell aun así usa 3 colores. Es el contraejemplo de las diapositivas de coloración.

  Welsh-PowellColoración voraz

La tarjeta Vértices lista todos los vértices en orden alfabético, con el total en el encabezado. El botón Nuevo crea un vértice en el lienzo sin cambiar de herramienta; después solo tienes que arrastrarlo al lugar deseado.

• Renombrar: edita la etiqueta directamente en el campo de texto, con hasta 6 caracteres. El orden alfabético de las etiquetas es el orden de visita por defecto de todos los algoritmos.
• Seleccionar: haz clic en el círculo con las iniciales o en el campo de texto para resaltar el vértice en el lienzo.
• Eliminar: el icono de papelera borra el vértice y todas las aristas incidentes a él.

El formulario de la parte superior de la tarjeta crea aristas con precisión, algo útil para grafos grandes o para copiar un ejercicio: elige los vértices De y A, indica el Peso y el Tipo (no dirigida o dirigida) y haz clic en Añadir arista. El encabezado muestra el total de aristas y cuántas hay de cada tipo.

Cada arista de la lista se puede editar sin volver a crearla:

• el campo numérico cambia el peso, y vaciarlo deja la arista sin peso;
• la insignia cambia la dirección con un clic: no dirigida / dirigida
• hacer clic en las etiquetas selecciona la arista en el lienzo;
• la papelera elimina la arista.

La tarjeta Algoritmo agrupa los métodos por tema, en el orden de la asignatura. Cada opción muestra el nombre, la complejidad y un resumen de la estrategia. El algoritmo seleccionado queda resaltado y define el contenido de la tarjeta Parámetros justo debajo.

El encabezado de la tarjeta repite el nombre y la complejidad del método, seguidos de los requisitos del grafo en forma de insignias. Los campos de vértice solo aparecen cuando el algoritmo los usa:

Cuando todavía no se ha elegido un campo obligatorio, el estudio usa el primer vértice en orden alfabético (y, para el sumidero, el primero distinto de la fuente). Los vértices elegidos reciben un anillo discontinuo en el lienzo con la etiqueta RAÍZ, DESTINO, FUENTE o SUMIDERO.

Muchos algoritmos necesitan decidir qué vecino examinar primero. Por defecto, la decisión sigue el orden alfabético de las etiquetas, que es la convención usada en clase. Cuando el ejercicio pide otro orden, constrúyelo en Secuencia de visita:

• haz clic en los vértices en el orden deseado para añadirlos a la secuencia;
• el primer vértice elegido pasa a ser la raíz cuando no se define ninguna arriba (en los algoritmos de flujo, es el primer vecino que se prueba en la búsqueda);
• haz clic en un vértice de la secuencia para quitarlo;
• los vértices que queden fuera siguen en orden alfabético, después de los elegidos;
• el botón Por defecto vuelve al orden alfabético.

Los requisitos se comprueban con cada cambio del grafo o de los parámetros. Si todo está bien, aparece una confirmación en verde; si no, cada problema se lista en rojo con la corrección sugerida y el botón Ejecutar queda desactivado.

El encabezado indica el algoritmo y la posición actual (por ejemplo, Paso 4 de 23), con una barra de progreso justo debajo. Los controles son:

• Primer paso

  Vuelve al estado inicial.

• Paso anterior

  Retrocede una iteración.

• Reproducir / pausar

  Avanza solo al ritmo elegido. Al final, vuelve a empezar desde el primer paso.

• Paso siguiente

  Avanza una iteración.

• Último paso

  Salta al resultado final.

• Limpiar

  Descarta la ejecución y devuelve el lienzo a sus colores originales.

El control deslizante salta directamente a cualquier paso. Cualquier navegación manual pausa la reproducción automática. Las velocidades disponibles son:

La tarjeta principal muestra el título de la decisión tomada (por ejemplo, “Arista tensa (A, C): relajada”), la justificación con los valores implicados y, cuando tiene sentido, métricas como el orden de visita, la iteración actual o el valor del flujo. Debajo aparecen las estructuras auxiliares del algoritmo.

Las tablas reproducen las de la pizarra: dist y pred, tiempos de descubrimiento y finalización, matrices de Floyd-Warshall, flujo y capacidades residuales, entre otras. Las filas de color indican el papel de cada entrada en el paso actual:

En el último paso aparece la tarjeta verde de Conclusiones, que interpreta el resultado: distancias finales y camino recuperado, peso total del árbol de expansión, valor del flujo máximo y el corte correspondiente, componentes encontradas, orden topológico, número de colores usados. Es el resumen para comparar con tu respuesta.