그래프의 축퇴를 계산 하시겠습니까?

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