子谦。

入门教程

未归档(52)

/ 注册

全部文章 / 入门教程（共1篇）

最小生成树

何为最小生成树？最小生成树就是对于一个连通图，保留若干条边，使图依然联通，且边权和最小。因为\(n\)个点的连通图（以下自动默认为连通图，），最少要有\(n-1\)条边。所以对于一个图的最小生成树，也一定只有\(n-1\)条边。反证一下（此证明仅限于非负边权）：如果这个图的最小生成树...

图论最小生成树入门教程

2019-08-16

0 403