Árbol de expansión mínimo con parámetros de doble peso

Considere una gráfica $G(V,E)$ . Cada borde $e$ tiene dos pesos $A_e$ y $B_e$ . Encuentre un árbol de expansión que minimice el producto $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$ . El algoritmo debe ejecutarse en tiempo polinómico con respecto a $|V|, |E|$ .

Me resulta difícil adaptar cualquiera de los algoritmos tradicionales en árboles de expansión (Kruskal, Prim, Edge-Deletion). ¿Cómo resolverlo? ¿Alguna pista?

algorithms graph-theory spanning-trees Strin
fuente

e

$e$

max (A_{e}, B_{e})

$\max(A_e,B_e)$

¿Es este un problema / ejercicio de tarea? Si es así, ¿es de un libro de texto? La razón por la que pregunto es que el contexto puede ayudar a "aplicar ingeniería inversa" al problema. No es inmediatamente obvio que un algoritmo codicioso sea apropiado aquí, pero si proviene del capítulo sobre algoritmos codiciosos ...

Joe

@utdiscant, eso no funcionará. Los bordes negativos pueden ser útiles.

Nicholas Mancuso

incluso para bordes positivos no es útil, por ejemplo, el par (10,10) no es mejor que el par (11,1) en la mayoría de los casos.

Respuestas:

Asumiré que no tienes bordes ponderados negativos, porque esto puede no funcionar si hay pesos negativos.

Algoritmo

Para cada uno de sus bordes, rotúlelos de a $1$ $n$

Deje pesar A del borde número $a_i$ $i$

Sea peso B del borde número $b_i$ $i$

Dibuja esta tabla

   |a_1 a_2 a_3 a_4 .. a_n
---+-------------------------
b_1|.........................
b_2|.........................
 . |.........................
 . |.........................
b_n|...................a_n * b_n

Con cada uno de los elementos de la tabla como producto de fila y columna.

Para cada borde, sume la fila y columna de la tabla relevante (y recuerde eliminar el elemento en la intersección ya que se ha sumado dos veces).

Encuentre el borde que tiene la suma más grande, elimine este borde si no desconecta el gráfico. Marque el borde como esencial de lo contrario. Si se ha eliminado un borde, complete sus filas y columnas con 0.

Exactitud

El resultado es obviamente un árbol.

El resultado obviamente se extiende ya que no hay vértices desconectados.

El resultado es mínimo? Si hay otro borde cuya eliminación creará un árbol de expansión más pequeño al final del algoritmo, entonces ese borde se habría eliminado y anulado primero. (si alguien pudiera ayudarme a hacer esto un poco más riguroso y / o contraejemplo, entonces sería genial)

Tiempo de ejecución

Obviamente polinomio en. $|V|$

editar

$(2,11), (11,2), (4,6)$ no es un contraejemplo.

$a_1 = 2, a_2 = 11, a_3 = 4$

$b_1 = 11, b_2 = 2, b_3 = 6$

Luego

   | 2     11     4
---+--------------------
11 | 22    121    44
 2 | 4     22     8
 6 | 12    66     24

\begin{aligned} (4, 6) & = 44 + 8 + 24 + 66 + 12 = 154 \\ (2, 11) & = 22 + 4 + 12 + 121 + 44 = 203 \\ (11, 2) & = 121 + 22 + 66 + 4 + 8 = 221 \end{aligned}

$\begin{align*} (4,6) &= 44 + 8 + 24 + 66 + 12 = 154 \\ (2,11) &= 22 + 4 + 12 + 121 + 44 = 203 \\ (11,2) &= 121 + 22 + 66 + 4 + 8 = 221 \end{align*}$

$(11,2)$ se elimina.

Termina con $(2,11), (4,6) = 6 * 17 = 102$

Otros árboles de expansión son

$(11,2), (4,6) = 15 * 12 = 180$

$(2,11), (11,2) = 13 * 13 = 169$

Herp Derpington
fuente

Me parece que este es un enfoque bastante codicioso. No me convence su "prueba" de minimalismo.

Nejc

@SaeedAmiri ¿Cómo es ese un ejemplo contrario? Publiqué el trabajo en la sección editada, el algoritmo da el resultado correcto.

Herp Derpington el

Lo que hizo fue encontrar cuánto contribuye cada uno en , y eliges los que tienen el mayor impacto. Eso es bueno, pero no es lo que se requiere. Es una pregunta difícil. Si desea mejorar su respuesta, debe venir con una prueba. De lo contrario, no tiene sentido.

(a_{i}, b_{i})

$(a _i, b _i)$

\sum_{e \in E} a_{i} . \sum_{e \in E} b_{i}

$\sum _{e \in E} a _i. \sum _{e \in E} b _i$

AJed

Sin embargo, es muy injusto obtener un voto negativo por su esfuerzo.

AJed

@AJed La prueba es la misma que en la eliminación primaria / kush / inversa. Todo lo que tenemos que demostrar ahora es que la propiedad de corte aún se mantiene.

Herp Derpington

Esta es la solución de http://www.cnblogs.com/autsky-jadek/p/3959446.html .

Podemos ver cada árbol de expansión como un punto en el plano , donde es la suma de peso , y es la suma de peso . El objetivo es minimizar . $x-y$ $x$ $\sum_{e\in T}A_{e}$ $\sum_{e\in T}B_{e}$ $xy$

Encontrar el árbol de expansión mínima en función del peso y peso . Así que tenemos dos puntos en el plano xy . En todos los puntos del árbol de expansión en el plano, tiene el mínimo , tiene el mínimo . $A$ $B$ $A,B$ $A$ $x$ $B$ $y$
Ahora nuestro objetivo es encontrar un punto en el triángulo que tenga una distancia máxima a la línea , de modo que podamos minimizar el valor de para todos los puntos en el triángulo . $C$ $OAB$ $AB$ $xy$ $C$ $ABC$

Porque . $2S_{ABC}=|\overrightarrow{AB}\times\overrightarrow{AC}|=(B_{x}-A_{x},B_{y}-A_{y})\times(C_{x}-A_{x},C_{y}-A_{y})=(B_{x}-A_{x})\cdot C_{y}+(A_{y}-B_{y})\cdot C_{x}-A_{y}(B_{x}-A_{x})+A_{x}(B{}_{y}-A_{y})$

Observe que es una constante, por lo que ahora a maximizar . Entonces hacemos un nuevo gráfico , mientras que el peso . Ahora ejecutamos un árbol de expansión máxima en para obtener el punto . $A_{y}(B_{x}-A_{x})+A_{x}(B{}_{y}-A_{y}$ $(B_{x}-A_{x})\cdot C_{y}+(A_{y}-B_{y})\cdot C_{x}$ $G^{\prime}=(V,E)$ $w(e)=B_{e}(B_{x}-A_{x})+C_{x}(A_{y}-B_{y})$ $G^{\prime}$ $C$
Ejecutar el algoritmo anterior en de forma recursiva, hasta que no hay más árboles de expansión entre y . $OBC, OAC$ $BC,AC$ $O$
Ahora tenemos un conjunto de posibles árboles de expansión. Calcule el valor para cada árbol para obtener el árbol mínimo. $xy$

fuente