[일반] 그래프가 얼마나 복잡한지 재는 양이 있나요?

[1234(118.235)]

안녕하세요. 제가 요즘 Ising model에서 그래프 문제를 공부하고 있는데 간단히 말해서 그래프들이 있을 때 얘네들이 얼마나 복잡한지 잴수 있는 양이 있나요? 사실 복잡성이란 단어도 러프한거라 모호합니다.

[익명(50.30)]

Ising model은 잘 모르지만 제가 아는건 graph laplacian이나 (특히 이것의 eigenvalue), volume entropy 혹은 kolmogorov complexity가 있네요. 이 중 모델에 맞는거 찾아보세요

[1234(118.235)]

답변 감사합니다!