Subscribed unsubscribe Subscribe Subscribe

0w1

生成樹相關問題 -- 訓練指南

訓練指南裡提出了幾個經典的生成樹問題,我想做一點整理。 首先提出了最小生成樹有兩個性質: 1. 切割性質:任一個圖 G的子集 G'非空且不為 G本身,則其中一個端點在 G'裡,另一個端點在 G 的邊裡權值最小的必然會包含於 G的最小生成樹裡。 2. 迴路性質:任…