计算图的退化度？

Question

我正在寻找一种计算给定图形退化度的方法。wikipedia article中概述了一种方法，但它还存储了退化顺序，我认为几周前在网上看到过一种更简单的算法，但现在找不到了。我想知道是否有一种更有效的方法来计算图形的退化度，如果我对存储图形的退化顺序没有兴趣？

如果有影响，我正在使用networkx和Python。

谢谢！

- dwayne

Answer 1

NetworkX拥有Batagelj和Zaversnik的O(m)核心算法，我认为您可以用它来实现您的目的： degeneracy(G) = max(networkx.core_number(G).values())? http://networkx.lanl.gov/reference/algorithms.core.html

- Aric