$$ \begin{aligned} 2E &\geq 3F \ &= 3(2-V+E) \ &= 6-3V+3E \ \Rightarrow E &= 2V-2 \end{aligned} $$什么意思
时间: 2023-11-29 16:25:43 浏览: 142
cs229-cvxopt2.pdf
这是关于图论中欧拉公式的推导过程。欧拉公式表明,对于一个连通的平面图(在平面上可以画出且边不相交),其顶点数 $V$、边数 $E$ 和面数 $F$ 满足 $V-E+F=2$。
上述推导过程从 $2E \geq 3F$ 开始,这是因为每个面至少有三条边,所以 $3F$ 表示所有面的边数之和。然后等号右边使用了欧拉公式,即 $3(2-V+E)$ 表示 $3$ 乘以所有面的边数之和。最后推导出 $E=2V-2$,这是将欧拉公式中的 $F=V-E+2$ 带入到 $2E \geq 3F$ 中得到的。
这个结果告诉我们,如果一个连通的平面图满足 $V$ 个顶点和 $E$ 条边,那么它的面数 $F$ 就可以由 $V$ 和 $E$ 计算出来,即 $F=2V-E+2$。
阅读全文