图的圆包装与圆接触表示 图论中，图的几何表示有助于直观理解其结构。圆包装（circle packing）与圆接触表示（circle contact representation）研究如何用圆来表示图，使得顶点对应圆，边对应圆的相切关系。下面逐步介绍这一概念。 1. 基本定义 圆包装 ： 对一个平面图 \( G \)，若存在一组互不重叠的圆（允许相切），每个圆对应一个顶点，且两个圆相切当且仅当对应的顶点相邻，则这组圆称为 \( G \) 的一个圆包装。 圆接触表示 ： 若要求所有圆互不重叠且仅通过相切连接，则称为 圆接触表示 。这种表示是圆包装的一种特例，要求圆的边界恰好接触而不交叉。 2. 历史背景与经典定理 柯比-施瓦茨定理（Koebe–Andreev–Thurston theorem） ： 任何平面图都存在一个圆接触表示，且若图是3-连通的，则表示在拓扑意义下唯一（需忽略莫比乌斯变换的影响）。 该定理将图的结构与几何紧密联系，成为圆包装理论的基石。 3. 构造方法 圆包装的构造常通过迭代优化实现： 初始布局 ： 将每个顶点对应的圆随机分配位置和半径。 优化目标 ： 定义能量函数（如圆的交叠误差），通过梯度下降或牛顿法调整圆的半径和位置，使不相邻的圆分离，相邻的圆恰好相切。 收敛条件 ： 当所有圆的边界距离满足相切条件时停止迭代。 4. 应用领域 图的可视化 ： 圆包装生成美观的图形布局，避免边交叉，适用于网络可视化。 共形映射 ： 通过圆的排列逼近复平面上的共形变换，用于几何函数论。 离散解析函数 ： 圆包装为离散拉普拉斯方程提供几何背景，用于离散微分几何。 5. 扩展与变体 高维推广 ： 将圆推广为球体，研究三维空间中球的接触表示（如球包装问题）。 加权圆包装 ： 为顶点分配权重，调整圆的半径比例，表示图中顶点的属性（如节点重要性）。 非平面图的表示 ： 对非平面图，允许圆重叠，但通过优化最小化重叠区域（近似圆包装）。 6. 计算复杂性 构造圆包装是多项式时间可解的，但高精度计算需数值迭代（如柯林-德费尔算法）。 若要求圆的半径为整数，问题变为NP难（与整数流相关）。 通过圆包装，图的结构与几何直观结合，成为图论与离散几何交叉的重要工具。