图论讲义：连通度与Cayley公式——生成树与连线问题详解

在图论讲义51的第三章中，讨论的核心内容是连通度和生成树的相关概念。首先，章节探讨了连通性的度量，通过实例分析了图3.1中四个图的连通程度差异，强调了顶点割的概念，即在连通图G中，如果某个子集V'使得G-V'不连通，那么V'被称为G的一个顶点割。 Cayley公式定理2.9给出了一个具体的计算公式，即τ(Kn)等于n除以(n-2)，这里τ表示简单无向图Kn的顶点数。其证明过程涉及构造一一对应关系，将Kn的每一个生成树T与一个特定的长为n-2的序列关联起来。生成树的构建过程中，通过选取每个1度顶点并删除它们，形成一个只剩两个顶点的树，这个过程是可逆的，可以用来重建生成树。 有趣的是，虽然nn-2看似是Kn非同构生成树的数量，但实际上它代表的是Kn所有不同生成树的总数。例如，K6尽管只有6个非同构的生成树，但它的所有生成树数量却是1296棵，这展示了生成树的多样性。 连线问题是章节中的另一个主题，它涉及实际应用中的优化问题。当需要构建一个铁路网络来连接多个城镇，每对城镇之间的直通线路都有相应的造价cij时，目标是找到总造价最低的连通网络。这个问题可以转化为在赋权图G中寻找具有最小权的连通生成子图，即最优树。最小生成树问题的一个具体例子如图2.9所示。 Kruskal算法是解决最小生成树问题的一种常用方法，它按照权值从小到大依次选择边，确保每次添加的边都不会形成环路，直到生成一棵连通且权值最小的树。算法步骤包括：首先选择权值最小的边e1，然后逐次加入权值更小的边，同时保持生成子图的连通性。 第三章通过实例和理论阐述了连通度、生成树以及连线问题的具体内容，展示了图论在实际问题中的应用价值，同时介绍了重要的Cayley公式和Kruskal算法等关键概念。