Arbre couvrant minimal avec des paramètres de double poids

Considérons un graphe . Chaque arête a deux poids et . Trouvez un arbre couvrant qui minimise le produit . L'algorithme doit s'exécuter en temps polynomial par rapport à.$G(V,E)$$e$$A_e$$B_e$$\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$$|V|, |E|$

Je trouve difficile d'adapter l'un des algorithmes traditionnels sur les arbres couvrant (Kruskal, Prim, Edge-Deletion). Comment le résoudre? Des indices?

Je vais supposer que vous ne recevez pas de bords pondérés négatifs, car cela peut ne pas fonctionner s'il y a des poids négatifs.

Algorithme

Pour chacun de vos bords, étiquetez-les de à$1$$n$

Soit poids A du nombre d'arêtes$a_i$$i$

Soit poids B du nombre d'arêtes$b_i$$i$

Dresser ce tableau

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

Chacun des éléments du tableau étant le produit d'une ligne et d'une colonne.

Pour chaque bord, additionnez la ligne et la colonne de tableau pertinentes (et n'oubliez pas de supprimer l'élément dans l'intersection car il a été additionné deux fois).

Trouvez l'arête qui a la plus grande somme, supprimez cette arête si elle ne déconnecte pas le graphique. Marquez le bord comme essentiel sinon. Si un bord a été supprimé, remplissez ses lignes et colonnes avec 0.

Exactitude

Le résultat est évidemment un arbre.

Le résultat s'étend évidemment car aucun sommet n'est déconnecté.

Le résultat est minime? S'il existe un autre bord dont la suppression créera un arbre couvrant plus petit à la fin de l'algorithme, ce bord aurait été supprimé et annulé en premier. (si quelqu'un pouvait m'aider à rendre cet exemple un peu plus rigoureux / et / ou contre, ce serait formidable)

Durée

Évidemment polynomial dans.$|V|$

Éditer

$(2,11), (11,2), (4,6)$ n'est pas un contre-exemple.

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

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

alors

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

$(11,2)$ est supprimé.

Se retrouver avec$(2,11), (4,6) = 6 * 17 = 102$

D'autres arbres couvrant sont

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

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

Il s'agit de la solution de http://www.cnblogs.com/autsky-jadek/p/3959446.html .

Nous pouvons voir chaque arbre couvrant comme un point dans le plan , où est la somme des poids , y est la somme des poids . Le but est de minimiser .$x-y$$x$$\sum_{e\in T}A_{e}$$\sum_{e\in T}B_{e}$$xy$

1. Trouvez l'arbre minimum en fonction du poids et le poids . Nous avons donc deux points dans le plan xy . Dans tous les points d'arbre couvrant dans le plan, a le minimum , a le minimum .$A$$B$$A,B$$A$$x$$B$$y$

2. Maintenant, nous cherchons à trouver un point dans le triangle qui a la distance maximale à la ligne , afin que nous puissions avoir la valeur pour minimisée pour tous les points du triangle .$C$$OAB$$AB$$xy$$C$$ABC$

Parce que .$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})$

3. Notez que est une constante, alors maintenant nous visons à maximiser . Nous donc un nouveau graphe , tandis que le poids . Maintenant, nous un arbre couvrant maximum sur pour obtenir le point . ( B x - A x )⋅$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$

4. Exécutez l'algorithme ci - dessus sur récursive, jusqu'à ce qu'il n'y a plus d' arbres couvrant entre et .B C , A C $OBC, OAC$$BC,AC$$O$

5. Nous obtenons maintenant un ensemble d'arbres couvrant possibles. Calculez la valeur pour chaque arbre pour obtenir l'arbre minimum.$xy$