LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Un gráfico plano y su árbol de expansión mínimo. Cada borde está etiquetado con su peso, que aquí es aproximadamente proporcional a su longitud.

Un árbol de expansión mínima ( MST ) o un árbol de expansión de peso mínimo es un subconjunto de los bordes de un gráfico no dirigido conectado con ponderación de bordes que conecta todos los vértices entre sí, sin ciclos y con el peso total de bordes mínimo posible. Es decir, es un árbol de expansión cuya suma de pesos de borde es lo más pequeña posible. De manera más general, cualquier gráfico no dirigido ponderado por el borde (no necesariamente conectado) tiene un bosque de expansión mínimo , que es una unión de los árboles de expansión mínimos para sus componentes conectados .

Hay bastantes casos de uso para árboles de expansión mínima. Un ejemplo sería una empresa de telecomunicaciones que intenta instalar el cable en un nuevo vecindario. Si se limita a enterrar el cable solo a lo largo de ciertos caminos (por ejemplo, carreteras), entonces habría un gráfico que contiene los puntos (por ejemplo, casas) conectados por esos caminos. Algunos de los caminos pueden ser más caros, ya que son más largos o requieren que el cable esté más enterrado; estos caminos serían representados por bordes con pesos más grandes. La moneda es una unidad aceptable para el peso de los bordes, no es necesario que las longitudes de los bordes obedezcan las reglas normales de la geometría, como la desigualdad del triángulo . Un arbol que se extiendepara esa gráfica sería un subconjunto de esos caminos que no tiene ciclos pero que aún conecta todas las casas; Puede haber varios árboles en expansión posibles. Un árbol de expansión mínimo sería uno con el costo total más bajo, que representa la ruta menos costosa para colocar el cable.

Propiedades [ editar ]

Posible multiplicidad [ editar ]

Si hay n vértices en el gráfico, entonces cada árbol de expansión tiene n - 1 aristas.

Esta figura muestra que puede haber más de un árbol de expansión mínimo en un gráfico. En la figura, los dos árboles debajo del gráfico son dos posibilidades de árbol de expansión mínima del gráfico dado.

Puede haber varios árboles de expansión mínima del mismo peso; en particular, si todos los pesos de borde de un gráfico dado son los mismos, entonces cada árbol de expansión de ese gráfico es mínimo.

Unicidad [ editar ]

Si cada borde tiene un peso distinto, solo habrá un único árbol de expansión mínimo . Esto es cierto en muchas situaciones realistas, como en el ejemplo de la compañía de telecomunicaciones anterior, donde es poco probable que dos caminos tengan exactamente el mismo costo. Esto también se generaliza a bosques extensos.

Prueba:

1. Supongamos lo contrario , que hay dos MST A y B diferentes .
2. Como A y B difieren a pesar de que contienen los mismos nodos, hay al menos un borde que pertenece a uno pero no al otro. Entre tales bordes, sea e _{1 el que} tenga menos peso; Esta elección es única porque los pesos de los bordes son distintos. Sin pérdida de generalidad, supongamos e ₁ se encuentra en una .
3. Como B es un MST, { e ₁ }$${\ displaystyle \ cup} B debe contener un ciclo C con e ₁ .
4. Como un árbol, A no contiene ciclos, por lo tanto C debe tener un borde e ₂ que no está en A .
5. Dado que e ₁ fue elegido como el borde único de menor peso entre los que pertenecen exactamente a uno de A y B , el peso de e ₂ debe ser mayor que el peso de e ₁ .
6. Como e ₁ y e ₂ son parte del ciclo C, reemplazar e ₂ por e ₁ en B produce un árbol de expansión con un peso menor.
7. Esto contradice la suposición de que B es un MST.

De manera más general, si los pesos de los bordes no son todos distintos, solo el conjunto de pesos (multi-) en los árboles de expansión mínima será ciertamente único; Es el mismo para todos los árboles de expansión mínima. ^[1]

Subgrafo de costo mínimo [ editar ]

Si los pesos son positivos , entonces un árbol de expansión mínimo es de hecho un subgrafo de costo mínimo que conecta todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total.

Propiedad del ciclo [ editar ]

Para cualquier ciclo C en el gráfico, si el peso de un borde e de C es mayor que los pesos individuales de todos los otros bordes de C , este borde no puede pertenecer a un MST.

Prueba: suponga lo contrario , es decir, que e pertenece a un MST T ₁ . Luego, al eliminar e se dividirá T ₁ en dos subárboles con los dos extremos de e en subárboles diferentes. El resto de C vuelve a conectar los subárboles, por lo tanto, hay un borde f de C con extremos en diferentes subárboles, es decir, vuelve a conectar los subárboles en un árbol T ₂ con un peso menor que el de T ₁ , porque el peso de f es menor que el peso de e.

Propiedad de corte [ editar ]

Esta figura muestra la propiedad de corte de los MST. T es el único MST del gráfico dado. Si S = {A, B, D, E}, por lo tanto VS = {C, F}, entonces hay 3 posibilidades del borde a través del corte (S, VS), son los bordes BC, EC, EF del original grafico. Entonces, e es uno de los bordes de peso mínimo para el corte, por lo tanto S ∪ {e} es parte de la MST T.

Para cualquier corte C del gráfico, si el peso de un borde e en el conjunto de cortes de C es estrictamente menor que el peso de todos los demás bordes del conjunto de cortes de C , este borde pertenece a todos los MST del gráfico .

Prueba: suponga que hay un MST T que no contiene e . La adición de e a T producirá un ciclo, que cruza el corte una vez en e y lo cruza en otro extremo e ' . Eliminación e 'obtenemos un árbol de expansión T ∖ {e'} ∪ {e} de peso estrictamente menor que T . Esto contradice la suposición de que T era un MST.

Por un argumento similar, si más de un borde tiene un peso mínimo a lo largo de un corte, cada uno de esos bordes está contenido en un árbol de expansión mínimo.

Borde de costo mínimo [ editar ]

Si el borde de costo mínimo e de un gráfico es único, entonces este borde se incluye en cualquier MST.

Prueba: si e no se incluyó en el MST, la eliminación de cualquiera de los bordes (mayor costo) en el ciclo formado después de agregar e al MST, produciría un árbol de menor peso.

Contracción [ editar ]

Si T es un árbol de bordes de MST, entonces podemos contraer T en un solo vértice mientras mantenemos el invariante de que el MST del gráfico contraído más T proporciona el MST para el gráfico antes de la contracción. ^[2]

Algoritmos [ editar ]

En todos los algoritmos a continuación, m es el número de bordes en el gráfico y n es el número de vértices.

Algoritmos clásicos [ editar ]

El primer algoritmo para encontrar un árbol de expansión mínimo fue desarrollado por el científico checo Otakar Borůvka en 1926 (consulte el algoritmo de Borůvka ). Su finalidad era una eficiente cobertura eléctrica de Moravia . El algoritmo procede en una secuencia de etapas. En cada etapa, llamada paso de Boruvka , identifica un bosque F que consiste en el borde de peso mínimo que incide en cada vértice en la gráfica G , luego forma la gráfica$${\ displaystyle G_ {1} = G \ setminus F}como la entrada para el siguiente paso. aquí$${\ displaystyle G \ setminus F}denota el gráfico derivado de G al contraer bordes en F (por la propiedad Cortar , estos bordes pertenecen al MST). Cada paso de Boruvka lleva un tiempo lineal. Como el número de vértices se reduce al menos a la mitad en cada paso, el algoritmo de Boruvka toma tiempo O ( m log n ). ^[2]

Un segundo algoritmo es el algoritmo de Prim , que fue inventado por Vojtěch Jarník en 1930 y redescubierto por Prim en 1957 y Dijkstra en 1959. Básicamente, crece el MST ( T ) una ventaja a la vez. Inicialmente, T contiene un vértice arbitrario. En cada paso, T se aumenta con un borde de menor peso ( x , y ) tales que x está en T y ytodavía no está en T . Por la propiedad Cortar , todos los bordes agregados a T están en el MST. Su tiempo de ejecución es O ( m log n ) u O ( m+ n log n ), dependiendo de las estructuras de datos utilizadas.

Un tercer algoritmo comúnmente usado es el algoritmo de Kruskal , que también lleva tiempo O ( m log n ).

Un cuarto algoritmo, que no se usa comúnmente, es el algoritmo de eliminación inversa , que es el inverso del algoritmo de Kruskal. Su tiempo de ejecución es O ( m log n (log log n ) ³ ).

Todos estos cuatro son algoritmos codiciosos . Puesto que se ejecutan en tiempo polinómico, el problema de encontrar tales árboles está en FP , y relacionados problemas de decisión tales como la determinación de si un borde particular es en el MST o determinar si el peso total mínimo excede un cierto valor están en P .

Algoritmos más rápidos [ editar ]

Varios investigadores han tratado de encontrar algoritmos de computación más eficientes.

En un modelo de comparación, en el que las únicas operaciones permitidas en pesos de bordes son comparaciones por pares, Karger, Klein y Tarjan (1995) encontraron un algoritmo aleatorio de tiempo linealbasado en una combinación del algoritmo de Borůvka y el algoritmo de borrado inverso. ^[3] [4]

El algoritmo basado en comparación no aleatorizado más rápido con complejidad conocida, por Bernard Chazelle, se basa en el montón blando , una cola de prioridad aproximada. ^[5] [6] Su tiempo de ejecución es O ( m  α ( m , n )), donde α es el inverso funcional clásico de la función Ackermann . La función α crece extremadamente lentamente, de modo que, para todos los propósitos prácticos, se puede considerar una constante no mayor que 4; por lo tanto, el algoritmo de Chazelle toma muy cerca del tiempo lineal.

Algoritmos de tiempo lineal en casos especiales [ editar ]

Graficos densos [ editar ]

Si el gráfico es denso (es decir, m / n ≥ log log log n ), un algoritmo determinista de Fredman y Tarjan encuentra el MST en el tiempo O ( m ). ^[7] El algoritmo ejecuta una serie de fases. Cada fase ejecuta el algoritmo de Primmuchas veces, cada una para un número limitado de pasos. El tiempo de ejecución de cada fase es O ( m + n ). Si el número de vértices antes de una fase es$${\ displaystyle n '}, el número de vértices que quedan después de una fase es como máximo $${\ displaystyle n '/ 2 ^ {m / n'}}. Por lo tanto, a lo sumo$${\ displaystyle \ log ^ {*} {n}}Se necesitan fases, lo que da un tiempo de ejecución lineal para gráficos densos. ^[2]

Hay otros algoritmos que funcionan en tiempo lineal en gráficos densos. ^[5] [8]

Pesos enteros [ editar ]

Si los pesos de borde son enteros representados en binario, entonces se conocen algoritmos deterministas que resuelven el problema en operaciones de enteros O ( m  +  n ). ^[9] Si el problema se puede resolver de manera determinista para un gráfico general en tiempo lineal mediante un algoritmo basado en comparación, sigue siendo una pregunta abierta.

Árboles de decisión [ editar ]

Dado el gráfico G donde los nodos y los bordes están fijos pero los pesos son desconocidos, es posible construir un árbol de decisión binario (DT) para calcular el MST para cualquier permutación de pesos. Cada nodo interno de la DT contiene una comparación entre dos bordes, por ejemplo, "es el peso del borde entre x y y más grande que el peso de la arista entre w y z ?". Los dos hijos del nodo corresponden a las dos respuestas posibles "sí" o "no". En cada hoja del DT, hay una lista de bordes de Gque corresponden a un MST. La complejidad del tiempo de ejecución de un DT es la mayor cantidad de consultas requeridas para encontrar el MST, que es solo la profundidad del DT. A DT para un gráfico de G se llama óptima si tiene la menor profundidad de todos los DTs correctos para G .

Por cada entero r , es posible encontrar árboles de decisión óptimos para todos los gráficos en r vértices por búsqueda de fuerza bruta . Esta búsqueda se realiza en dos pasos.

A. Generando todos los DT potenciales

• Existen $${\ displaystyle 2 ^ {r \ elige 2}}Diferentes gráficas en r vértices.
• Para cada gráfico, siempre se puede encontrar un MST utilizando r ( r -1) comparaciones, por ejemplo, mediante el algoritmo de Prim .
• Por lo tanto, la profundidad de un DT óptimo es menor que $${\ displaystyle r ^ {2}}.
• Por lo tanto, el número de nodos internos en un DT óptimo es menor que $${\ displaystyle 2 ^ {r ^ {2}}}.
• Cada nodo interno compara dos aristas. El número de bordes es como máximo.$${\ displaystyle r ^ {2}} por lo que el número diferente de comparaciones es a lo sumo $${\ displaystyle r ^ {4}}.
• Por lo tanto, el número de DT potenciales es menor que: $${\ displaystyle {(r ^ {4})} ^ {(2 ^ {r ^ {2}})} = r ^ {2 ^ {(r ^ {2} +2)}}}.

B. Identificación de los DT correctos Para verificar si un DT es correcto, debe verificarse todas las posibles permutaciones de los pesos de borde.

• El número de tales permutaciones es como máximo $${\ displaystyle (r ^ {2})!}.
• Para cada permutación, resuelva el problema MST en el gráfico dado usando cualquier algoritmo existente, y compare el resultado con la respuesta dada por el DT.
• El tiempo de ejecución de cualquier algoritmo MST es a lo sumo $${\ displaystyle (r ^ {2})}, por lo que el tiempo total requerido para verificar todas las permutaciones es como máximo $${\ displaystyle (r ^ {2} +1)!}.

Por lo tanto, el tiempo total requerido para encontrar un DT óptimo para todos los gráficos con r vértices es:$${\ displaystyle 2 ^ {r \ elige 2} \ cdot r ^ {2 ^ {(r ^ {2} +2)}} \ cdot (r ^ {2} +1)!}, que es menor que: $${\ displaystyle 2 ^ {2 ^ {r ^ {2} + o (r)}}}. ^[2]

Ver también: Modelo de árbol de decisión.

Algoritmo optimo [ editar ]

Seth Pettie y Vijaya Ramachandran han encontrado un algoritmo de árbol de expansión basado en una comparación determinista, óptimamente óptima. ^[2] La siguiente es una descripción simplificada del algoritmo.

1. Dejar $${\ displaystyle r = \ log \ log \ log n}, donde n es el número de vértices. Encuentra todos los árboles de decisión óptimos en r vértices. Esto se puede hacer en el tiempo O ( n ) (ver Árboles de decisión arriba).
2. Divida la gráfica en componentes con un máximo de r vértices en cada componente. Esta partición se puede hacer en el tiempo O ( m ).
3. Utilice los árboles de decisión óptimos para encontrar un MST para cada componente.
4. Contrate cada componente conectado abarcado por los MST a un solo vértice.
5. Es posible probar que el gráfico resultante tiene como máximo n / r vértices. Por lo tanto, el gráfico es denso y podemos usar cualquier algoritmo que funcione en gráficos densos en el tiempo O ( m ).

El tiempo de ejecución de todos los pasos en el algoritmo es O ( m ), excepto el paso de usar los árboles de decisión . No conocemos el tiempo de ejecución de este paso, pero sabemos que es óptimo, ningún algoritmo puede hacerlo mejor que el árbol de decisiones óptimo.

Por lo tanto, este algoritmo tiene la propiedad peculiar de que es probablemente óptimo, aunque se desconocesu complejidad en tiempo de ejecución .

Algoritmos paralelos y distribuidos [ editar ]

La investigación también ha considerado algoritmos paralelos para el problema del árbol de expansión mínimo. Con un número lineal de procesadores es posible resolver el problema en$${\ displaystyle O (\ log n)}hora. ^[10] [11] Bader y Cong (2006) demuestran un algoritmo que puede calcular MST 5 veces más rápido en 8 procesadores que un algoritmo secuencial optimizado. ^[12]

Otros algoritmos especializados se han diseñado para calcular los árboles de expansión mínimos de un gráfico tan grande que la mayor parte de ellos deben almacenarse en el disco en todo momento. Estos algoritmos de almacenamiento externo , por ejemplo, como se describe en "Ingeniería de un algoritmo de árbol de expansión mínimo de memoria externa" por Roman, Dementiev et al., ^[13] pueden operar, según las afirmaciones de los autores, tan solo 2 a 5 veces más lento que un sistema tradicional. algoritmo en memoria. Se basan en algoritmos eficientes de clasificación de almacenamiento externo y en técnicas de contracción de gráficos para reducir el tamaño del gráfico de manera eficiente.

El problema también puede abordarse de manera distribuida . Si cada nodo se considera una computadora y ningún nodo sabe nada, excepto sus propios enlaces conectados, aún se puede calcular el árbol de expansión mínimo distribuido .

MST en gráficos completos [ editar ]

Alan M. Frieze mostró que, dado un gráfico completo en n vértices, con ponderaciones de borde que son independientes, se distribuyen de manera idéntica variables aleatorias con función de distribución$${\ displaystyle F} satisfactorio {\ displaystyle F '(0)> 0}, luego a medida que n se acerca + ∞ el peso esperado de los MST se aproxima$${\ displaystyle \ zeta (3) / F '(0)}, dónde $${\ displaystyle \ zeta}Es la función zeta de Riemann . Frieze y Steele también demostraron la convergencia en la probabilidad. Svante Janson demostró un teorema de límite central para el peso del MST.

Para pesos aleatorios uniformes en $${\ displaystyle [0,1]}, el tamaño esperado exacto del árbol de expansión mínimo se ha calculado para pequeños gráficos completos. ^[14]

Vértices	Tamaño esperado	Tamaño aproximado aproximado
2	1/2	0.5
3	3/4	0.75
4	31/35	0.8857143
5	893/924	0.9664502
6	278/273	1.0183151
7	30739/29172	1.053716
8	199462271/184848378	1.0790588
9	126510063932/115228853025	1.0979027

Aplicaciones [ editar ]

Árboles de expansión mínima tienen aplicaciones directas en el diseño de redes, incluidas las redes de computadoras , redes de telecomunicaciones , redes de transporte , redes de suministro de agua y redes eléctricas (que fueron inventadas por primera vez para, como se mencionó anteriormente). ^[15] Se invocan como subrutinas en algoritmos para otros problemas, incluido el algoritmo Christofides para aproximar el problema del vendedor ambulante , ^[16] aproximar el problema de corte mínimo multiterminal (que es equivalente en el caso de un solo terminal al flujo máximo) problema ), ^[17] y aproximando el mínimo coste igualado perfecto igualado . ^[18]

Otras aplicaciones prácticas basadas en árboles de expansión mínima incluyen:

• Taxonomía . ^[19]
• Análisis de agrupamiento: puntos de agrupamiento en el plano, ^[20] agrupamiento de enlace único (un método de agrupamiento jerárquico ), ^[21] agrupamiento teórico-gráfico, ^[22] y agrupamiento de datos de expresión génica . ^[23]
• Construcción de árboles para su difusión en redes informáticas. ^[24]
• Registro de imagen ^[25] y segmentación ^[26] : consulte la segmentación mínima basada en árboles .
• Extracción de rasgos curvilíneos en visión artificial . ^[27]
• Reconocimiento de expresiones matemáticas a mano. ^[28]
• Diseño de circuitos : implementando multiplicaciones constantes múltiples eficientes, como se usa en filtros de respuesta de impulsos finitos . ^[29]
• Regionalización de áreas socio-geográficas, la agrupación de áreas en regiones homogéneas y contiguas. ^[30]
• Comparación de datos ecotoxicológicos . ^[31]
• Topológica observabilidad en sistemas de potencia. ^[32]
• Medición de la homogeneidad de materiales bidimensionales. ^[33]
• Control del proceso minimax . ^[34]
• Los árboles de expansión mínima también se pueden usar para describir los mercados financieros. ^[35] [36] Se puede crear una matriz de correlación calculando un coeficiente de correlación entre dos acciones. Esta matriz se puede representar topológicamente como una red compleja y se puede construir un árbol de expansión mínimo para visualizar las relaciones.

Problemas relacionados [ editar ]

Se sabe que el problema de encontrar el árbol Steiner de un subconjunto de vértices, es decir, el árbol mínimo que abarca el subconjunto dado, es NP-Completo . ^[37]

Un problema relacionado es el árbol de expansión mínimo de k ( k -MST), que es el árbol que abarca un subconjunto de k vértices en la gráfica con un peso mínimo.

Un conjunto de k árboles de expansión más pequeños es un subconjunto de k árboles de expansión (de todos los árboles de expansión posibles), de manera que ningún árbol de expansión fuera del subconjunto tiene un peso menor. ^{[38] [39] [40]} (Tenga en cuenta que este problema no está relacionado con el árbol de expansión k-minimo.)

El árbol de expansión mínimo euclidiano es un árbol de expansión de una gráfica con ponderaciones de borde correspondientes a la distancia euclidiana entre vértices que son puntos en el plano (o espacio).

El árbol de expansión mínimo rectilíneo es un árbol de expansión de una gráfica con pesos de bordes correspondientes a la distancia rectilínea entre vértices que son puntos en el plano (o espacio).

En el modelo distribuido , donde cada nodo se considera una computadora y ningún nodo conoce nada, excepto sus propios enlaces conectados, se puede considerar un árbol de expansión mínimo distribuido . La definición matemática del problema es la misma pero hay diferentes enfoques para una solución.

El árbol de expansión mínimo capacitado es un árbol que tiene un nodo marcado (origen o raíz) y cada uno de los subárboles adjuntos al nodo no contiene más de c nodos. c se llama capacidad de un árbol. Resolver CMST de manera óptima es NP-difícil , ^[41] pero buenas heurísticas como Esau-Williams y Sharma producen soluciones casi óptimas en el tiempo polinomial.

El árbol de expansión mínimo de grado restringido es un árbol de expansión mínimo en el que cada vértice está conectado a no más d otros vértices, para un número dado d . El caso d  = 2 es un caso especial del problema del vendedor ambulante , por lo que el árbol de expansión mínimo de grado limitado es NP-duro en general.

Para los gráficos dirigidos , el problema del árbol de expansión mínimo se denomina problema de arborescenciay se puede resolver en tiempo cuadrático utilizando el algoritmo Chu-Liu / Edmonds .

Un árbol de expansión máxima es un árbol de expansión con un peso mayor o igual al peso de cualquier otro árbol de expansión. Este árbol se puede encontrar con algoritmos como el de Prim o el de Kruskal, después de multiplicar los pesos de los bordes por -1 y resolver el problema MST en el nuevo gráfico. Una ruta en el árbol de expansión máxima es la ruta más ancha en el gráfico entre sus dos puntos finales: entre todas las rutas posibles, maximiza el peso del borde de peso mínimo. ^[42] Los árboles de expansión máxima encuentran aplicaciones en algoritmos de análisis para lenguajes naturales ^[43] y en algoritmos de entrenamiento para campos aleatorios condicionales .

El problema dinámico de MST se refiere a la actualización de un MST previamente calculado después de un cambio de peso en el borde del gráfico original o la inserción / eliminación de un vértice. ^{[44] [45] [46]}

El problema del árbol de expansión de etiquetado mínimo es encontrar un árbol de expansión con menos tipos de etiquetas si cada borde de un gráfico está asociado con una etiqueta de un conjunto de etiquetas finito en lugar de un peso. ^[47]

Un borde de cuello de botella es el borde ponderado más alto en un árbol de expansión. Un árbol de expansión es un árbol de expansión de cuello de botella mínimo (o MBST ) si el gráfico no contiene un árbol de expansión con un peso de borde de cuello de botella más pequeño. Un MST es necesariamente un MBST (que se puede demostrar por la propiedad de corte ), pero un MBST no es necesariamente un MST.