graph-theory - 平面グラフ

Question

プレーンをセクションにスライスするノードとエッジを持つ平面グラフがあります。nes

およびと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です。