【信息科学与工程学】【数据科学】数据科学领域——第三篇 数学08 几何学07 网络几何01

编号类型领域问题问题的数学分析参数列表及参数的数值范围关联知识1组合优化 / 计算几何网络几何（几何图论）欧几里得最小生成树（EMST）：给定平面上的 n 个点（节点），求连接所有点的总边长最小的树。数学模型：设点集 P={p1​,…,pn​}⊂R2，边权为欧氏距离 d(pi​,pj​)=(xi​−xj​)2+(yi​−yj​)2​。目标是找到一棵生成树 T=(P,E)使得 ∑(i,j)∈E​d(pi​,pj​)最小。该问题是经典 MST 在欧氏度量下的特例，属于 NP-hard 吗？不，EMST 可在多项式时间内求解。算法设计思路：先构造完全图的 Delaunay 三角剖分（DT），因为 EMST 一定是 DT 的子图（证明：若某边不在 DT 中，则存在更短边替换）。因此算法分为两步：① 用 Bowyer-Watson 算法或分治法构建 DT（时间复杂度 O(n log n)）；② 在 DT 上运行 Kruskal 或 Prim 算法得到 MST（O(n log n)）。总复杂度 O(n log n)。空间复杂度 O(n)。/