交叉數不等式
交叉數不等式是數學的圖論分支中的一条不等式，給出了一幅图画在平面上时交叉數的下界；这一结论又名交叉数引理。給定一幅圖，該下界可由其邊數和頂點數計算出。不等式斷言，若邊數e与頂點數n的比值大于某个常数，則交叉數不小于e^3/n^2乘以另一个固定的常数。 交叉數不等式在超大规模集成电路設計與組合幾何方面有應用。其由、、、塞邁雷迪·安德烈四人以及分別獨立發現。 敍述及歷史 交叉數不等式說明，若無向簡單圖G恰有n個頂點和e條邊，且e>7n，則交…
标签：#拓撲圖論
共 1 篇文章