MathLabs

第2题

设 PP 是一个正 20062006 边形。如果 PP 的一条对角线的两个端点将 PP 的边界分成两部分,每部分都由奇数条 PP 的边组成,则称该对角线是好的。PP 的各条边也称为好的。假设用 20032003 条在 PP 内部互不相交的对角线将 PP 剖分成三角形。求在这样的剖分中,具有两条好边的等腰三角形最多可能有多少个。
第 3/5 步:计算森林的叶子数
通俗地说

含两条好边的三角形删去好对角线后成为叶子;不含好边的三角形保留与三条非好对角线的邻接。一个只含度数 11 和 33 的树有 (ni+2)/2(n_i+2)/2 个叶子。

deg⁡F(v)∈{1,3},L(F)=∑i=1k+1ni+22=1003+k\deg_F(v)\in\{1,3\},\qquad L(F)=\sum_{i=1}^{k+1}\frac{n_i+2}{2}=1003+k
详细分析

由第1步,每个三角形含两条或零条好边。边界边全是好边,因此不含好边的三角形有三条非好对角线,在 FF 中度数为 33;含两条好边的三角形恰有一条非好边,度数为 11。若 k+1k+1 个分量顶点数为 n1,…,nk+1n_1,\ldots,n_{k+1},第 ii 个分量有 (ni+2)/2(n_i+2)/2 个叶子。因 ∑ni=2004\sum n_i=2004,FF 有 1003+k1003+k 个叶子。