python - グラフの縮退を計算しますか？

Question

与えられたグラフの縮退を計算する方法を探しています。ウィキペディアの記事には方法の概要が記載されていますが、縮退の順序も格納されており、数週間前にオンラインのどこかでより単純なアルゴリズムを見たと思いますが、今は見つかりません。グラフの縮退順序を保存することに関心がない場合、グラフの縮退を計算するためのより効率的な方法があるかどうか疑問に思っていますか？

重要な場合は、networkxとPythonを使用しています。

ありがとう！

Answer 1

NetworkXには、バタジェリとZaversnikのO（m）コアアルゴリズムがあり、目的に使用できると思います degeneracy(G) = max(networkx.core_number(G).values())。 http://networkx.lanl.gov/reference/algorithms.core.html