グラフの縮退を計算する？

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