平面连通图是一个二维网络,网络由节点和边组成,比如我随手画了一个:
也可以是这样:
它并不是一个空间连通图因为他可以拓扑变换成这样:
但如果这种图就不行了:
这样的连通图只能出现在三维空间中,所以无法满足欧拉公式.
前期准备：
kruskal算法是由一个个递进的循环周期组成的，每个循环周期的步骤如下：
然后给一个过程图，大家自己意会：
根据之前对生成树下的定义，首先要覆盖所有点，其次不能有环，最后不能有断路。
第一点：很容易，既然通过集合A、B、C包含所有边的洗牌过程，自然照顾到了G中所有的点。
第二点：更容易，每个循环中都要检查一遍是否与之前的”小树苗“形成环路，最后肯定无环。
第三点：可以用反证法，假设最后生成了相互隔离的两棵树，因为总共循环了x次（每条边各一次），两棵树中间的那些边（C中可以连接两棵树的边）当初被审查的时候肯定会被纳入B，与“纳入C”矛盾，所以不可能生成两棵树。
这个地方考验大家的空间想象能力，如果想不出来可以画图。
同样是反证法：
现在开始做一系列的变换,将K变换成T:
prim算法见下文