證明如果一個圖的所有邊的權(quán)重都是正值，則任意一個連接所有結(jié)點(diǎn)且總權(quán)重最小的一個邊集合必然形成一棵樹

求證: 如果一個圖的所有邊的權(quán)重都是正值，則任意一個連接所有結(jié)點(diǎn)且總權(quán)重最小的一個邊集合必然形成一棵樹。

證明：

1）此圖不包含回路，反之，若包含回路，那么可以選擇構(gòu)成回路的邊集合中權(quán)重最大的邊，將這條邊從邊集中刪除。經(jīng)過變換之后，此圖連通性不改變，而且總權(quán)重減少。所以總權(quán)重最小的連接所有結(jié)點(diǎn)的一個邊集，必然不包含回路，所以形成一棵樹。

2）畫個三角形即可，3條邊權(quán)重是-1，，那么如果邊集只有2個邊，總權(quán)重是最少是－2。邊集如果是3邊，那么權(quán)重是－3。－3<-2但是3邊是圈，2邊是樹，所以不成立。