请问是不是全世界所有海都是无向连通图的?那如果不无向连通图的海,当港口运输时是不是还得走回陆地?

设G是所有边权均不相同的无向联通图

首先,易证图G中权值最小的边一定是最小生成树中的边(否则最小生成树加上权值最小的边后构成一个环,去掉环中任意一条非此邊则形成了另一个权值更小的生成树)

之后用反证法,假设G存在俩个不同的最小生成树

①.设G的俩个不同的最小生成树T1 T2设这俩颗生成树的並集为子图G1,G1为无向连通图图且T1 T2显然为G1的最小生成树由首先可得知俩颗生成树至少包含一条公共边,将G1中两颗生成树的公共边删去得箌子图G2。G2由一个或多个无向连通图分量组成其中至少有一个无向连通图分量的最小生成树不唯一(否则若所有无向连通图分量的最小生荿树唯一,则将删掉的公共边加上则T1等于T2,这与假设相矛盾)

②.对其中一个最小生成树不唯一的无向连通图分量设为H,若H中点数>2重複①的操作。否则H中只有俩个点由于所有边权值不同,显然最小生成树唯一这与①中的最后一句相矛盾。

综上所有边权均不相同的無向图最小生成树是唯一的。

设ek满足ek≠e'k且k最小由于所有边权值不同,不妨假设weight(ek)

还有一个更强的结论:同一个图不同最小生成树的边权重序列相同

一线资深高中数学教师擅长高Φ数学教学,曾获得中青年骨干教师爱好收集各种教育资料

我要回帖

更多关于 强连通 的文章

 

随机推荐