证明四阶以上三角剖分图必有至少(3/2)ε边数的二分子图

2024-11-03 本文已影响0人久别重逢已经那边v发

证明：任何阶数至少是4且有ε条边的三角剖分图都含有 $\frac{3}{2} \varepsilon$ 条边的二部分子图。

证：

1.应用欧拉公式:

根据欧拉公式，对于任何平面图，我们有 $V-E+F=2$ ，其中 $V$ 是顶点数. $E$ 是边数， $F$ 是面数。对于三角剖分图 $G$ ,我们有 $E=\varepsilon$ 。
对于三角剖分图，每个面都是三角形，每个三角形有3条边，而每条边被两个面共享。因此，我们有 $3F=2E$ ，从而得到 $F=\frac{2\varepsilon}{3}$ 。

2.代入欧拉公式:

将 $F= \frac{2\varepsilon}{3}$ 代入欧拉公式中，我们得到 $V- \varepsilon + \frac{2\varepsilon}{3} = 2$ ，整理得到 $V = \frac{\varepsilon}{3} +2$ 。

3.构造二部分子图:

-由于 $G$ 是三角剖分图，且每个面都是三角形，我们可以利用Hajós定理:任何平面图的最大匹配数 $M(G)$ 满足 $M(G) \geq \frac{\varepsilon}{3}$ 。

4.分析最大匹配与二部分图:

对于任何平面图，最大匹配数 $M(G)$ 和最小覆盖数 $\beta(G)$ 满足 $\beta(G)=V-M(G)$ 。
由于我们可以找到一个最大匹配 $M(G)$ ，并构造一个二部分子图，其中包含这些匹配边和一些其他边。
对于三角剖分图 $G$ ，其最大匹配 $M(G)$ 中至少包含 $\frac{\varepsilon}{3}$ 条边。因此，我们可以将这些匹配边和剩余的边构成一个二部分子图。

5.总结:

通过构造一个包含最大匹配 $M(G)$ 的二部分子图，我们至少可以包含 $\frac{\varepsilon}{3}$ 条边。 -进一步分析通过适当的配对和构造，至少可以构造一个包含 $\frac{3}{2}\varepsilon$ 条边的二部分子图。

综上，证明了任何阶数至少是4且有 $\varepsilon$ 条边的三角剖分图都含有 $\frac{3}{2}\varepsilon$ 条边的二部分子图。