云南大学算法图论实验：有向图弧连通度及Menger定理应用

在本次实验中，刘鹏同学针对20151910042课程的《算法图论实验》进行了一项关于有向图弧连通度的深入研究。实验的主要目标是加深对图的连通度概念的理解，包括点连通度和弧连通度的定义，以及Menger定理及其推论的应用。 首先，实验强调了连通图的基本概念。点连通度（vertex-connectivity）衡量的是图中最小的顶点集合，其删除后会导致图变得不连通。-连通图是指至少需要删除-1个顶点才能将其分割开。类似地，边连通度（edge-connectivity）关注的是最小边集合，其删除将导致图不连通。 Menger定理是关键的理论工具，它指出对于任何两个图的子集A和B，存在不相交的-链的数量等于每个分离点截集（或边截集）中的最小点（或边）数量。这个定理有两个推论，其中一个与点的Menger型极大极小定理相关，表明在图G中，两点之间的点不交的-链的最大数量等于局部点连通度；另一个则是关于边的极大极小定理，涉及边不交的-链与局部边连通度的关系。 算法设计部分，学生利用Menger定理的原理，通过网络流算法来实现计算图的点连通度。网络流算法在此处起到了桥梁作用，因为它能够处理图中节点间的流量分配问题，而点不交的限制条件恰好符合这一方法。具体实现时，学生可能需要构建一个模型，确保在每一步操作中，没有两个链共享相同的路径，从而达到找出点连通度的目的。 实验环境包括Windows10 Pro 1803操作系统和MacOS Mojave，这些平台的选择反映了实验在不同系统上的兼容性和适应性。学生需要熟练掌握C语言编程，以将理论知识转化为可执行的代码。 此次实验不仅要求学生掌握图论基本概念，还锻炼了他们的编程技能，特别是算法设计和应用网络流理论解决实际问题的能力。通过实验，学生可以更好地理解有向图的连通性，并能运用Menger定理来分析和处理复杂的图结构。