Minimal Spanning Tree Dengan Parameter Berat Ganda

Pertimbangkan grafik . Setiap tepi e memiliki dua bobot A e dan B e . Cari pohon rentang yang meminimalkan produk ( Σ e ∈ T A e ) ( Σ e ∈ T B e ) . Algoritme harus dijalankan dalam waktu polinomial berkenaan dengan | V | , | E | .$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|$

Saya merasa kesulitan untuk mengadaptasi salah satu algoritma tradisional pada spanning tree (Kruskal, Prim, Edge-Deletion). Bagaimana cara mengatasinya? Ada petunjuk?

Saya akan menganggap Anda tidak diberi tepi berbobot negatif, karena ini mungkin tidak berfungsi jika ada bobot negatif.

Algoritma

Untuk setiap sisi Anda, beri label hingga$1$$n$

Biarkan bobot A dari jumlah tepi$a_i$$i$

Biarkan bobot B dari nomor tepi$b_i$$i$

Gambarkan tabel ini

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

Dengan masing-masing elemen tabel menjadi produk baris dan kolom.

Untuk setiap tepi, jumlah baris dan kolom tabel yang relevan (dan ingat untuk menghapus elemen di persimpangan karena telah dijumlahkan dua kali).

Temukan tepi yang memiliki jumlah terbesar, hapus tepi ini jika tidak memutuskan grafik. Tandai tepi sebagai esensial jika tidak. Jika tepi telah dihapus, isi baris dan kolomnya dengan 0.

Ketepatan

Hasilnya jelas pohon.

Hasilnya jelas mencakup karena tidak ada simpul yang terputus.

Hasilnya minimal? Jika ada tepi lain yang penghapusannya akan membuat spanning tree yang lebih kecil di akhir algoritma, maka tepi itu akan dihapus dan dibatalkan terlebih dahulu. (Jika seseorang dapat membantu saya membuat ini sedikit lebih teliti / dan / atau contoh balasan maka itu akan bagus)

Runtime

Jelas polinomial dalam.$|V|$

sunting

$(2,11), (11,2), (4,6)$ adalah tidak contoh counter.

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

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

Kemudian

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

$(11,2)$ dihapus.

Berakhir dengan$(2,11), (4,6) = 6 * 17 = 102$

Pohon merentang lainnya adalah

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

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

Ini adalah solusi dari http://www.cnblogs.com/autsky-jadek/p/3959446.html .

Kita dapat melihat setiap spanning tree sebagai titik di bidang , di mana adalah jumlah berat , y adalah jumlah berat . Tujuannya untuk meminimalkan .$x-y$$x$$\sum_{e\in T}A_{e}$$\sum_{e\in T}B_{e}$$xy$

1. Menemukan minimum spanning tree sesuai dengan berat dan berat . Jadi kita memiliki dua poin dalam bidang xy . Di semua titik spanning tree dalam pesawat, memiliki minimum , memiliki minimum .$A$$B$$A,B$$A$$x$$B$$y$

2. Sekarang kita bertujuan untuk menemukan titik dalam segitiga yang memiliki jarak maksimum ke garis , sehingga kita dapat memiliki nilai untuk diperkecil untuk semua titik dalam segitiga .$C$$OAB$$AB$$xy$$C$$ABC$

Karena .$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. Perhatikan bahwa adalah konstanta, jadi sekarang kami bertujuan untuk memaksimalkan . Jadi kita membuat grafik baru , sedangkan bobot . Sekarang kita menjalankan spanning tree maksimum pada untuk mendapatkan titik .$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. Jalankan algoritma di atas pada rekursif, sampai tidak ada lagi yang mencakup pohon antara dan .$OBC, OAC$$BC,AC$$O$

5. Sekarang kita mendapatkan satu set pohon spanning yang mungkin. Hitung nilai untuk setiap pohon untuk mendapatkan pohon minimum.$xy$