Del*_*lup 13 graph minimum-spanning-tree data-structures
我花了很多时间阅读有关最小生成树的剪切属性的在线演示和教科书.我并没有真正得到它的假设,甚至为什么它是实用的.据说它有助于确定要添加到MST的边缘,但我没有看到它是如何实现的.到目前为止,我对cut属性的理解是你将MST分成两个任意子集.这里有什么帮助？谢谢!
dei*_*nst 64
连接图的切割是一组最小边,其去除将图分成两个部分(部分).最小切割属性表示如果切口的一个边缘的重量小于切口中的任何其他边缘,则它在MST中.要看到这一点,假设有一个不包含边缘的MST.如果我们将边缘添加到MST,我们得到一个与切割相交至少两次的循环,因此我们可以通过从MST中移除另一个边缘来打破循环,从而使新的树具有较小的权重,从而与最小化相矛盾. MST.