LISTA DE PROBLEMAS

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 árbol de expansión de peso mínimo es un subconjunto de los bordes de un gráfico conectado , ponderado de borde no dirigido que conecta todos los vértices , sin ningún ciclo y con el mínimo peso total posible. Es decir, es un árbol de expansión cuya suma de pesos de borde es lo más pequeña posible. En términos más generales, cualquier gráfico no dirigido ponderado por el borde (no necesariamente conectado) tiene un bosque de expansión mínima , que es una unión de los árboles de expansión mínima para sus componentes conectados .

Hay bastantes casos de uso para árboles de expansión mínima. Un ejemplo sería una compañía de telecomunicaciones que intenta tender 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 porque son más largos o requieren que el cable esté enterrado más profundo; estos caminos estarían representados por aristas con pesos mayores. La moneda es una unidad aceptable para el peso del borde: no es necesario que las longitudes del borde obedezcan las reglas normales de la geometría, como la desigualdad del triángulo . Un árbolpara ese gráfico sería un subconjunto de esos caminos que no tiene ciclos pero que aún conecta todas las casas; Puede haber varios árboles de 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 tender el cable.

Propiedades [ editar ]

Posible multiplicidad [ editar ]

Si hay n vértices en el gráfico, 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 iguales, entonces cada árbol de expansión de ese gráfico es mínimo.

Singularidad [ 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 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 para abarcar bosques.

Prueba:

1. Asumir el contrario , que hay dos MSTs diferentes A y B .
2. Como A y B difieren a pesar de contener 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 aquellos 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, al reemplazar e ₂ con e ₁ en B, se obtiene un árbol de expansión con un peso menor.
7. Esto contradice la suposición de que B es un MST.

En términos más generales, si los pesos de los bordes no son todos distintos, entonces solo el (multi) conjunto de pesos en los árboles de expansión mínima seguramente será único; Es lo mismo para todos los árboles de expansión mínima. ^[1]

Subgrafo de costo mínimo [ editar ]

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

Propiedad de 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 , entonces 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 diferentes subárboles. 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 .

Cortar propiedad [ 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 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 del MST T.

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

Prueba: suponga que hay un MST T que no contiene e . Agregar e a T producirá un ciclo, que cruza el corte una vez en e y vuelve a cruzar en otro borde 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 en un corte, entonces cada borde está contenido en un árbol de expansión mínimo.

Costo mínimo borde [ editar ]

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

Prueba: si e no se incluyó en el MST, la eliminación de cualquiera de los (coste más grande) los bordes en el ciclo formado después de la adición de e para el MST, produciría un árbol de expansión de menor peso.

Contracción [ editar ]

Si T es un árbol de bordes MST, entonces podemos contraer T en un solo vértice mientras mantenemos la invariante de que el MST del gráfico contraído más T da 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 aristas en el gráfico yn 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 (ver el algoritmo de Borůvka ). Su propósito era una cobertura eléctrica eficiente 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 incidente a cada vértice en el gráfico G , luego forma el gráfico$${\ displaystyle G_ {1} = G \ setminus F}como la entrada al siguiente paso. aquí$${\ displaystyle G \ setminus F}denota el gráfico derivado de G contrayendo bordes en F (por la propiedad Cut , estos bordes pertenecen al MST). Cada paso de Boruvka toma tiempo lineal. Dado que 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 ) de un lado 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 y todavía no está en T . Por la propiedad Cut , todos los bordes agregados a T están en el MST. Su tiempo de ejecución es O ( m logn ) u O ( m + n log n ), dependiendo de las estructuras de datos utilizadas.

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

Un cuarto algoritmo, no tan comúnmente usado, 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 mínimo total excede de un cierto valor están en P .

Algoritmos más rápidos [ editar ]

Varios investigadores han intentado encontrar más algoritmos computacionalmente eficientes.

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

El algoritmo basado en la comparación no aleatorio más rápido con complejidad conocida, de Bernard Chazelle , se basa en el montón dinámico , 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 de Ackermann . La función α crece extremadamente lentamente, de modo que, a todos los efectos prácticos, puede considerarse una constante no mayor que 4; así, el algoritmo de Chazelle se acerca mucho al tiempo lineal.

Algoritmos de tiempo lineal en casos especiales [ editar ]

Gráficos densos [ editar ]

Si el gráfico es denso (es decir, m / n ≥ log log log n ), entonces 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 Prim muchas 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 restantes 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 proporciona 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 los bordes son enteros representados en binario, entonces se conocen algoritmos deterministas que resuelven el problema en operaciones enteras O ( m  +  n ). ^[9] Si un problema basado en la comparación puede resolverse de manera determinista para un gráfico general en tiempo lineal sigue siendo una cuestión 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 del DT contiene una comparación entre dos bordes, por ejemplo, "¿Es el peso del borde entre x e y mayor que el peso del borde 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 necesarias 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 .

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

A. Generando todos los DT potenciales

• Existen $${\ displaystyle 2 ^ {r \ choose 2}}diferentes gráficos en vértices r .
• Para cada gráfico, siempre se puede encontrar un MST usando comparaciones r ( r -1), 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}} entonces el número diferente de comparaciones es como máximo $${\ 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 en todas las permutaciones posibles de los pesos de los bordes.

• 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 como máximo $${\ 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 óptimo DT para todos los gráficos con r vértices es:$${\ displaystyle 2 ^ {r \ choose 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 óptimo [ editar ]

Seth Pettie y Vijaya Ramachandran han encontrado un algoritmo de árbol de expansión mínima determinista basado en la comparación, demostrablemente óptimo. ^[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. Buscar todos los árboles de decisión óptima en r vértices. Esto se puede hacer a tiempo O ( n ) (ver los árboles de decisión arriba).
2. Particione el gráfico en componentes con a lo sumo r vértices en cada componente. Esta partición utiliza un montón dinámico , que "corrompe" una pequeña cantidad de los bordes del gráfico.
3. Utilice los árboles de decisión óptimos para encontrar un MST para el subgrafo sin corrupción dentro de cada componente.
4. Contrae cada componente conectado que abarcan los MST a un solo vértice y aplique cualquier algoritmo que funcione en gráficos densos en el tiempo O ( m ) a la contracción del subgrafo no corrupto
5. Vuelva a agregar los bordes dañados al bosque resultante para formar una subgrafía que garantice que contiene el árbol de expansión mínimo, y más pequeño en un factor constante que el gráfico inicial. Aplique el algoritmo óptimo de forma recursiva a este gráfico.

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 decisión óptimo.

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

Algoritmos paralelos y distribuidos [ editar ]

Más información: Algoritmos paralelos para árboles de expansión mínima.

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]

Se han diseñado otros algoritmos especializados para calcular los árboles de expansión mínima de un gráfico tan grande que la mayor parte debe 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 poco como 2 a 5 veces más lento que un tradicional algoritmo en memoria. Se basan en algoritmos de clasificación de almacenamiento externo eficientes 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 demostró que dado un gráfico completo en n vértices, con pesos de borde que son variables aleatorias independientes distribuidas idénticamente con función de distribución$${\ displaystyle F} satisfactorio {\ displaystyle F '(0)> 0}, entonces cuando n se aproxima a + ∞ se acerca el peso esperado de la MST$${\ displaystyle \ zeta (3) / F '(0)}, dónde $${\ displaystyle \ zeta}es la función zeta de Riemann . Frieze y Steele también demostraron 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 exacto esperado 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 esperado
2	1/2	0.5 0.5
3	3/4	0,75
4 4	31/35	0.8857143
5 5	893/924	0.9664502
6 6	278/273	1.0183151
7 7	30739/29172	1.053716
8	199462271/184848378	1.0790588
9 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 ya que, como se mencionó anteriormente). ^[15] Se invocan como subrutinas en algoritmos para otros problemas, incluido el algoritmo de Christofides para aproximar el problema del vendedor ambulante , ^[16] aproximando el problema de corte mínimo de múltiples terminales (que es equivalente en el caso de un solo terminal al flujo máximo problema ), ^[17] y aproximar la coincidencia perfecta ponderada de costo mínimo . ^[18]

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

• Taxonomía . ^[19]
• Análisis de conglomerados : puntos de conglomeración en el plano, ^[20] conglomeración de enlace único (un método de conglomeración jerárquica ), ^[21] conglomeración teórica de grafos, ^[22] y conglomeración 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 el árbol de expansión .
• Extracción de características curvilíneas en visión artificial . ^[27]
• Reconocimiento de escritura a mano de expresiones matemáticas. ^[28]
• Diseño de circuito : implementando multiplicaciones constantes múltiples eficientes, como se usa en filtros de respuesta de impulso finito . ^[29]
• Regionalización de áreas sociogeográficas, agrupación de áreas en regiones homogéneas y contiguas. ^[30]
• Comparación de datos de ecotoxicología . ^[31]
• Topológica observabilidad en sistemas de potencia. ^[32]
• Medición de la homogeneidad de materiales bidimensionales. ^[33]
• Control de 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 existencias. 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 ]

Árboles Steiner mínimos de vértices de polígonos regulares con N = 3 a 8 lados. La longitud de red más baja L para N > 5 es la circunferencia menos un lado. Los cuadrados representan puntos Steiner.

Se sabe que el problema de encontrar el árbol Steiner de un subconjunto de los 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 k- mínimo ( k -MST), que es el árbol que abarca algún subconjunto de k vértices en el gráfico 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 modo que ningún árbol de expansión fuera del subconjunto tenga un peso menor. ^{[38] [39] [40]} (Tenga en cuenta que este problema no está relacionado con el árbol de expansión k- mínimo).

El árbol de expansión mínimo euclidiano es un árbol de expansión de un gráfico con pesos 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 un gráfico con pesos de borde 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 sabe nada excepto sus propios enlaces conectados, se puede considerar un árbol de expansión mínima distribuida . La definición matemática del problema es la misma, pero existen 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 conectados al nodo no contiene más que un nodo c . c se llama capacidad de árbol. Resolver CMST de manera óptima es NP-difícil , ^[41] pero las buenas heurísticas como Esau-Williams y Sharma producen soluciones cercanas a lo óptimo en tiempo polinómico.

El árbol de expansión mínima con restricción de grado es un árbol de expansión mínima en el que cada vértice está conectado a no más de 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 con restricción de grado es NP-duro en general.

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

Un árbol de expansión máximo es un árbol de expansión con un peso mayor o igual al peso de cualquier otro árbol de expansión. Tal árbol se puede encontrar con algoritmos como los de Prim o Kruskal después de multiplicar los pesos de borde 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 de la MST dinámica se refiere a la actualización de una MST calculada previamente después de un cambio de peso del borde en el gráfico original o la inserción / eliminación de un vértice. ^{[44] [45] [46]}

El problema mínimo del árbol de expansión de etiquetado 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 finitas en lugar de un peso. ^[47]

Un borde de cuello de botella es el borde más alto ponderado 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 (demostrable por la propiedad de corte ), pero un MBST no es necesariamente un MST.