42、图论中的三角形覆盖接触图与图同构算法研究

图论中的三角形覆盖接触图与图同构算法研究

在图论的研究领域中，三角形覆盖接触图（TCCG）以及图同构问题一直是重要的研究方向。本文将深入探讨三角形覆盖接触图的连通性、外平面图的可实现性，以及有界树深度图的图同构问题，并介绍相关的算法。

三角形覆盖接触图的连通性

对于给定的一组种子点集 (S)，若其中任意两个种子点既不在垂直线上也不在水平线上，我们可以构建不同连通性的三角形覆盖接触图。

首先，构建路径 TCCG 较为简单。我们只需按照 (x) 坐标值对种子点进行排序，然后用三角形覆盖这些种子点，使得每个三角形（除第一个和最后一个）都与前一个和后一个三角形接触，这样三角形的接触图就形成了一条路径。

然而，构建具有更高连通性的 TCCG 则更具挑战性。下面我们重点介绍构建 4 - 连通 TCCG 的方法：
1. 排序与选择特殊点 ：将种子点 (p_1, p_2, \cdots, p_n) 按从左到右的顺序排序，然后在除 (p_1) 和 (p_n) 之外的种子点中，分别选出最顶部和最底部的种子点 (p_t) 和 (p_b)。
2. 构建梯形 ：用一个梯形 (trap(l_1, l_2, l_3, l_4)) 包围 (S - {p_1, p_n, p_t, p_b})，该梯形需满足以下性质：
- (l_2) 和 (l_4) 为水平线。
- (l_1) 和 (l_3) 不平行。
- (l_1) 将种子点分为 ({p_1}) 和 (S - {p_1})。
- (l_2) 将种子点分为 ({p_t}) 和 (S - {p_t})。