¿Para qué un grafo completo — en las aplicaciones no suele ser ralo?

El grafo **euclidiano completo** es un modelo claro: en teoría se puede unir cualquier par, y el MST elige las **n−1** ligaduras más baratas sin ciclos. En redes reales hay menos aristas; los mismos algoritmos valen allí, pero el caso denso muestra bien la ordenación de **Kruskal** y el recuento de candidatos de **Prim**.

¿Cambia el MST si se cambia la raíz de Prim?

Si los pesos **no son únicos**, pueden existir **varios** conjuntos distintos de aristas con el mismo peso mínimo. Entonces raíces distintas (y otro orden) pueden dar **MST distintos** como conjuntos de aristas, pero el **peso total** sigue siendo el mismo: se contrasta con **Kruskal**.

¿Qué significa la línea roja punteada en el modo Kruskal?

Es la arista actual de la lista ordenada que **no se puede** añadir: ambos extremos ya están en la **misma** componente de los conjuntos disjuntos; añadirla cerraría un **ciclo** y el algoritmo la **omite**.

Árbol de expansión mínima (Prim y Kruskal)

Puntos al azar en el plano, grafo completo con pesos euclidianos: Prim paso a paso desde la raíz o Kruskal con conjuntos disjuntos; se compara el peso total.

Sobre el modelo

El árbol de expansión mínima une todos los vértices sin ciclos y con la menor suma de pesos. n puntos seudoaleatorios en el plano (reproducibles a partir de la semilla de la disposición). El grafo se toma completo: el peso de una arista es la distancia euclidiana entre vértices; cualquier árbol de expansión tiene n−1 aristas. Prim arranca de una raíz elegida y en cada paso añade la arista mínima que cruza el corte «ya en el árbol / afuera» (regla voraz según la propiedad del corte). Kruskal ordena todas las aristas por peso (si empatan, por orden lexicográfico de los extremos, para que sea determinista) y recorre la lista con conjuntos disjuntos: la arista se acepta si une componentes distintas y se rechaza (resalte rojo punteado) si cerraría un ciclo. Los pesos totales del MST de ambos algoritmos coinciden.

Para quién: Matemática discreta y algoritmos: construcciones voraces del MST, propiedades del corte y del ciclo, conjuntos disjuntos.

Conceptos clave

árbol de expansión mínima (MST)
algoritmo de Prim
algoritmo de Kruskal
propiedad del corte
propiedad del ciclo
conjuntos disjuntos (DSU)
grafo completo
pesos euclidianos

Cómo funciona

Grafo completo de n puntos en el plano con pesos de distancias euclidianas: Prim crece el árbol desde la raíz con la arista mínima que cruza el corte; Kruskal recorre las aristas por peso creciente y los conjuntos disjuntos descartan la arista si cerraría un ciclo; el peso total del MST coincide en ambos.

Preguntas frecuentes

¿Para qué un grafo completo — en las aplicaciones no suele ser ralo?: El grafo euclidiano completo es un modelo claro: en teoría se puede unir cualquier par, y el MST elige las n−1 ligaduras más baratas sin ciclos. En redes reales hay menos aristas; los mismos algoritmos valen allí, pero el caso denso muestra bien la ordenación de Kruskal y el recuento de candidatos de Prim.
¿Cambia el MST si se cambia la raíz de Prim?: Si los pesos no son únicos, pueden existir varios conjuntos distintos de aristas con el mismo peso mínimo. Entonces raíces distintas (y otro orden) pueden dar MST distintos como conjuntos de aristas, pero el peso total sigue siendo el mismo: se contrasta con Kruskal.
¿Qué significa la línea roja punteada en el modo Kruskal?: Es la arista actual de la lista ordenada que no se puede añadir: ambos extremos ya están en la misma componente de los conjuntos disjuntos; añadirla cerraría un ciclo y el algoritmo la omite.

Siga con temas cercanos de esta categoría — o todos los 48 de «Ingeniería».

Toda la categoría →

NuevoEscuela

Generadores de laberintos y A*

Abrir el simulador

Laberintos perfectos en una rejilla 40×28: recorrido recursivo, Wilson, Eller o Prim aleatorio; se resuelve con A* (Manhattan, 4-vecindad). Se pueden dibujar paredes y mover el inicio y la meta.

NuevoEscuela

A* y Dijkstra (rejilla)

Abrir el simulador

Rejilla 40×28: A*, Dijkstra o búsqueda voraz; heurísticas, 4- y 8-conectividad, paredes y celdas caras; se colorean el conjunto abierto y el cerrado.

NuevoEscuela

Autómata finito

Abrir el simulador

Máquina de Moore para un semáforo: ciclo verde–amarillo–rojo por temporizador o avance manual; grafo de estados.

NuevoEscuela

Planificador RRT (rejilla)

Abrir el simulador

El mismo mapa de paredes 40×28: muestras al azar, nodo más cercano, paso con comprobación de colisiones, sesgo de muestreo hacia la meta; botón para comparar con A*.

NuevoEscuela

Cinemática inversa de un brazo de dos eslabones

Abrir el simulador

Brazo plano de dos eslabones: objetivo en pantalla, dos soluciones — codo arriba y codo abajo, ángulos θ₁ y θ₂.

NuevoEscuela

Deflexión de una viga: método de la carga unitaria

Abrir el simulador

Viga de Euler–Bernoulli simplemente apoyada, con fuerza P y carga w: la deflexión analítica frente a la integral de trabajo virtual ∫Mm/EI dx.

Árbol de expansión mínima (Prim y Kruskal)

Sobre el modelo

Cómo funciona

Preguntas frecuentes

Simuladores afines

Generadores de laberintos y A*

A* y Dijkstra (rejilla)

Autómata finito

Planificador RRT (rejilla)

Cinemática inversa de un brazo de dos eslabones

Deflexión de una viga: método de la carga unitaria

Árbol de expansión mínima (Prim y Kruskal)

Sobre el modelo

Cómo funciona

Preguntas frecuentes