[일반] 어떤 그래프가 해밀턴회로를 가질 필요충분 명제 아직 모름?

[가우스나죽어(gaussimdie)]

아직 그래프이론 안들어서 모르는데

해밀턴회로는 유명해서 뭔지는 알고있음

해밀턴 그래프 이거 다 노가다로 찾아?

동치명제 없음? ㄹㅇ?

- dc official App

[익명(175.203)]

NP-complete문제기 때문에 동치조건을 찾는다 하더라도 그 동치조건을 만족하는지 판별하는것도 엄청나게 어려워서 별 의미 없을 가능성이 큼. 물론 낮은 확률로 P=NP를 증명해버릴수도 있겠지만

[익명(175.203)]

다만 노가다로 찾냐? 하면 단순노가다 (O(n!))보다는 훨씬 빠르게 찾아볼 방법이 있음

[가우스나죽어(gaussimdie)]

설명 고마우이 - dc App

[익명(1.46)]

동치명제야 많지