董玲玉：形式语言计算概论中相等子集最小割的NP完全性研究

董玲玉的结课报告聚焦于"相等子集最小割1"的问题，这是一个在形式语言与计算概论课程中的核心课题。该问题涉及到图论中的分割概念，具体来说，给定一个图G=(N,A)和两个特定的节点s和t，以及一个正整数W，目标是寻找两个相等大小的节点集合𝑆1和𝑆2，使得所有连接这两个集合的边权重之和不超过W，同时确保集合间的交集为空。这个问题的复杂性体现在它是NP-Complete问题，意味着没有多项式时间的算法能够确定其最优解。 报告首先介绍了问题的背景，强调了它的重要性，因为它是NPC（非确定性多项式完全）问题，即证明其他NP问题可以通过某种方式转化为它来求解。例如，通过Karp的21个NPC问题之一，图的最大割问题可以被证明为NPC问题，而相等子集最小割则是在其基础上的一个更复杂版本，其困难程度不亚于最大割。 解决方法部分探讨了针对此问题的策略。可能采取的算法并不总能给出全局最优解，但通常会提供一个近似或良好的解决方案。报告还提到了一些关键步骤，如前处理，可能包括数据预处理和优化，以便更好地适应并行计算。并行求解是针对大图问题的一种策略，通过将细粒度的网格分解成粗粒度的任务，减少通信量，实现负载均衡，这有助于提高计算效率。 报告还涉及到了物理建模和网格生成，这些技术在实际应用中用于构建复杂的几何模型，然后将其转换为计算网格。区域分解是这一过程的重要环节，它将计算区域划分为较小的、易于管理的部分，这对于大型计算问题是必不可少的。 在图的表示中，给出了具体的例子，如节点集合 {$𝑣1,𝑣2,𝑣3,𝑣4$} 和边集A，以及如何应用图的最大割理论来理解相等子集最小割问题。最后，报告详细地概述了整个计算流程，从问题定义、求解策略到软件执行的CFD（计算流体动力学）工具的使用，以及区域分解如何在其中扮演关键角色。 董玲玉的结课报告深入探讨了相等子集最小割问题的理论背景、求解算法以及其实现策略，展示了在形式语言与计算概论课程中如何处理这类具有挑战性的图论问题。