最小產品生成樹是否與最小生成樹不同？

Question

最小產品生成樹是否與最小生成樹不同？ PLZ解釋（如果可能的話，用示例）。我的意思是，添加到最小值的邊應該（？）也具有最小的乘積。

Answer 1

與所有邊權重（正，負，零）：

他們可能是不一樣的。

藉此例如：

 -10 
    □______□ 
/\ 
1 | | 0 
    \/
    □ 

在這裏，我們有：

Minimum product spanning tree:   Minimum sum spanning tree: 
     -10        -10 
    □______□       □______□ 
/         \ 
1 |          | 0 
    \         /
    □         □ 

非零邊權重（正面和負面的）：

他們可能不相同。

偶數個負值的乘積導致正值，所以在這種情況下爲最小產品生成樹選擇正值會更好。

藉此例如：

 -5 
    □______□ 
/\ 
5 | | -5 
    \/
    □ 

在這裏，我們有：

Minimum product spanning tree:   Minimum sum spanning tree: 
     -5         -5 
    □______□       □______□ 
/         \ 
5 |          | -5 
    \         /
    □         □ 

這也將是更好的挑選較高的正值，而不是小的負值，只要我們結束了奇數個負值。

具有非負邊權重（正，零）：

可能有多個極小產品生成樹，其中一些可能不是最小和生成樹（我還沒有找到一個證明/計數器示例，但目前看起來像至少有一個最小產品生成樹的將具有最小總和）。

藉此例如：

 0 
    □______□ 
/\ 
1 | | 10 
    \/
    □ 

這裏既有10-0和1-0是最低產品生成樹，但只有1-0是最小的總和生成樹。

由於只有正邊緣權重和不同的邊權：

他們將是相同的。

證明：

考慮a和b之間採摘與c在樹的其餘部分的總和。

假設a，b，c> 0 ...

Assume ca < cb 
then a  < b  (since c > 0) 
then a + c < b + c 

因此，如果採摘a導致最小的產品，它也將導致最小的總和。

因此，獲得最小的產品和最小的總和將包括挑選所有相同的邊緣。

因此，它們將具有相同的生成樹。

由於只有正邊緣權重和非獨特的優勢權重：

上述假設不同的邊權，如果不是這樣的話，有可能是要麼多生成樹，和他們顯然贏得了」不一定是相同的，但兩者的生成樹的選擇將是相同的，因爲它們將具有相同的產品和相同的總和，因爲唯一的區別是在具有相同權重的兩個邊之間進行選擇。

考慮：

 10 
    □______□ 
/\ 
5 | | 5 
    \/
    □ 

兩個可能的生成樹是：

 10    10 
    □______□  □______□ 
/    \ 
5 |     | 5 
    \    /
    □    □ 

兩者都是最小積和生成樹（唯一的區別是，我們挑選其中5個，但5 = 5 ，所以它不會改變總和或產品）。

Answer 2

如果所有的邊權重嚴格爲正，那麼它們將是同一棵樹。一個簡單的方法是查看MST算法，並注意不要做任何實際的添加，他們只在每個步驟中從某個集合中選擇最小邊緣。

如果邊權重嚴格爲正，那麼具有權重W_i的最小乘積生成樹將與具有權重log W_i的最小和生成樹相同，並且由於對數函數是單調的，則任何MST算法將表現相同權重W_i比權重W_i。 （假設所有的邊權重是不同的），那麼圖的MST將包含圖的每次切割的最小代價邊。很明顯，MST在邊權重的單調變換下是不變的。