graph-theory - 平面图

Question

我有一个带有节点和边的平面图，将平原切成部分。nes

作为and和s的函数的上限是多少？nee/n

我试图找出我可以依靠一些代码使用的内存有多少。

---

很容易证明它e不超过n*(n-1)/2，但我有一种感觉，它将是一个小整数。对于n ~= 10我有固定节点位置的情况，这将限制高估了 2 倍。

Answer 1

你应该看看这里 http://en.wikipedia.org/wiki/Euler_characteristic 可能会有所帮助

Answer 2

可以通过归纳证明 e <= 3*n - 6。所以 e/n < 3 和所以 s/n < 2。