MathLabs

第2题

设 PP 是一个正 20062006 边形。如果 PP 的一条对角线的两个端点将 PP 的边界分成两部分，每部分都由奇数条 PP 的边组成，则称该对角线是好的。PP 的各条边也称为好的。假设用 20032003 条在 PP 内部互不相交的对角线将 PP 剖分成三角形。求在这样的剖分中，具有两条好边的等腰三角形最多可能有多少个。
第 2/5 步：从三角剖分树中删去好对角线
上一步下一步
通俗地说

20042004 个三角形是树的顶点，共享对角线的两个三角形之间连边。删去 kk 条好对角线后，这棵树分成 k+1k+1 个连通分量。

T=dual tree of the triangulation,F=T∖{edges for good diagonals}T=\text{dual tree of the triangulation},\qquad F=T\setminus\{\text{edges for good diagonals}\}
详细分析

多边形三角剖分的对偶图 TT 是一棵有 20042004 个顶点的树。设使用的好对角线数为 kk，删去对应的 kk 条边后得到由 k+1k+1 棵树组成的森林 FF。