Arbol generador minimo
Algoritmo del árbol de expansión mínima
Contenidos
ResumenLa generación de todos los árboles de expansión posibles de un grafo es una de las principales áreas de investigación en teoría de grafos, ya que el número de árboles de expansión de un grafo aumenta exponencialmente con el tamaño del grafo. Desde principios de los
Desde principios de la década de 1960, investigadores de todo el mundo han desarrollado varios algoritmos de distinta eficacia. Este artículo es un estudio exhaustivo de la literatura sobre estos algoritmos, suponiendo que la entrada es un grafo simple conectado no dirigido de orden finito, y contiene un análisis detallado y comparaciones en el comportamiento teórico y experimental de estos algoritmos.
Para cualesquiera dos aristas e, f ∉ T0, e < f sólo si ∂+e ≤ ∂+f.Sea S cualquier subconjunto no vacío de E. Sea, Min(S) denota la arista más pequeña en S, considerando Min(Φ) = en. Para cualquier árbol de expansión T y cualquier arista f ∈ T, el subgrafo inducido por el conjunto de aristas T\f tiene exactamente dos componentes. El conjunto de aristas que conectan estas componentes se denomina corte fundamental asociado a T y f, y se representa como C*(T\f). Así, para cualquier arista f ∈ T y para una arista arbitraria g ∈ C*(T\f), T\f ∪ g es también un árbol de spanning. Para cualquier arista g ∉ T, el subgrafo inducido de aristas de G por T ∪ g tiene un ciclo único, llamado ciclo fundamental asociado a T y g. El conjunto de aristas del ciclo se representa como C(T ∪ g). Para cualquier g∉ T y para cualquier f ∈ C(T ∪ g), T ∪ g\f es un árbol de expansión.Es evidente que, si f = Min(T0\Tc), entonces |C(Tc ∪ f) ∩ C*(T0\f)|f | = 1 se cumple. Para cualquier árbol de expansión Tp de G y para dos aristas arbitrarias f y g, sea Tc= Tpf ∪ g. Tc es hijo de Tp si y sólo si se cumplen las siguientes condiciones:
Calculadora del árbol de máxima expansión
El algoritmo de Kruskal es un concepto introducido en la teoría de grafos de las matemáticas discretas. Se utiliza para descubrir el camino más corto entre dos puntos en un grafo ponderado conectado. Este algoritmo convierte un grafo dado en un bosque, considerando cada nodo como un árbol independiente. Estos árboles sólo pueden enlazarse entre sí si la arista que los conecta tiene un valor bajo y no genera un ciclo en la estructura MST. En este tutorial, aprenderá más sobre el Algoritmo de Kruskal en detalle.
Como se mencionó anteriormente, el algoritmo de Kruskal se utiliza para generar un árbol de extensión mínima para un grafo dado. Pero, ¿qué es exactamente un árbol de expansión mínima? Un árbol de extensión mínima es un subconjunto de un grafo con el mismo número de vértices que el grafo y aristas iguales al número de vértices -1. También tiene un coste mínimo para el grafo. También tiene un coste mínimo la suma de todos los pesos de las aristas de un árbol de expansión.
El algoritmo de Kruskal ordena todas las aristas por orden creciente de sus pesos de arista y sigue añadiendo nodos al árbol sólo si la arista elegida no forma ningún ciclo. Además, elige la arista con un coste mínimo al principio y la arista con un coste máximo al final. Por lo tanto, se puede decir que el algoritmo de Kruskal hace una elección localmente óptima, con la intención de encontrar la solución óptima global. Por eso se le llama algoritmo codicioso.
Calculadora en línea del algoritmo de Kruskal
Un Árbol de Mínimo Alcance (MST) o Árbol de Mínimo Peso es un subconjunto de aristas de un grafo no dirigido, conectado y de aristas ponderadas, que conecta todos los vértices entre sí, sin ningún ciclo y con el mínimo peso total de arista posible[1], es decir, es un árbol cuya suma de pesos de arista es lo más pequeña posible[2]. En términos más generales, cualquier grafo no dirigido de aristas ponderadas (no necesariamente conectado) tiene un Bosque de Mínimo Alcance, que es la unión de los árboles de mínimo alcance de sus componentes conectados.
Hay muchos casos de uso de los árboles de extensión mínima. Por ejemplo, una empresa de telecomunicaciones que quiere tender un cable en un barrio nuevo. Si se ve obligada a soterrar el cable sólo a lo largo de determinados caminos (por ejemplo, carreteras), entonces existiría un grafo que contendría los puntos (por ejemplo, casas) conectados por esos caminos. Algunos de los caminos pueden ser más caros, porque son más largos, o requieren que el cable se entierre a mayor profundidad; estos caminos estarían representados por aristas con pesos mayores. La moneda es una unidad aceptable para el peso de las aristas: no es necesario que las longitudes de las aristas obedezcan las reglas normales de la geometría, como la desigualdad de los triángulos. Un árbol de expansión para ese grafo sería un subconjunto de esos caminos que no tuviera ciclos pero que conectara todas las casas; podría haber varios árboles de expansión posibles. El árbol mínimo sería el de menor coste total, es decir, el camino más barato para tender el cable.
Ejemplo de árbol de expansión mínima
En matemáticas, se puede formar un árbol mínimo aleatorio asignando pesos aleatorios de alguna distribución a las aristas de un grafo no dirigido y construyendo después el árbol mínimo del grafo.
Cuando el grafo dado es un grafo completo de n vértices, y los pesos de las aristas tienen una función de distribución continua cuya derivada en cero es D > 0, entonces el peso esperado de sus árboles mínimos aleatorios está limitado por una constante, en lugar de crecer en función de n. Más concretamente, esta constante tiende a crecer en función de n. Más concretamente, esta constante tiende en el límite (a medida que n va al infinito) a ζ(3)/D, donde ζ es la función zeta de Riemann y ζ(3) es la constante de Apéry. Por ejemplo, para pesos de arista distribuidos uniformemente en el intervalo unitario, la derivada es D = 1, y el límite es simplemente ζ(3)[1].
En contraste con los árboles de expansión uniformemente aleatorios de grafos completos, para los que el diámetro típico es proporcional a la raíz cuadrada del número de vértices, los árboles de expansión mínima aleatorios de grafos completos tienen un diámetro típico proporcional a la raíz cúbica[2].