計算圖的簡併度？

Question

我正在尋找一種方法來計算給定圖的簡併度。 wikipedia article概述了一種方法，但它也存儲退化排序，我想我已經在幾周前的某個地方看到了一個更簡單的算法，但我現在找不到它。如果我沒有興趣存儲圖的退化排序，我想知道是否有更高效的方法來計算圖的退化？

我使用networkx和Python，如果它很重要的話。

謝謝！

Answer 1

NetworkX有Batagelj和Zaversnik的O（m）核心算法，我認爲你可以用於你的目的： degeneracy(G) = max(networkx.core_number(G).values())？ http://networkx.lanl.gov/reference/algorithms.core.html