이 글은 GPT 5가 최종 편집하였다. 썸네일도 마찬가지인데, 예전보다는 좀 발전한 것 같다.그래프에 Euler Circuit이 존재할 조건은 방향그래프, 무방향그래프에서 모두 쉽게 판정할 수 있다. 그렇다면 가능한 Eulerian Circuit의 개수는 몇 개일까? 신기하게도, 이 경우에 대한 답은 방향그래프에서 훨씬 쉽다는 것이 알려져 있다.Directed Graph : BEST theorem결론부터 말해, 방향그래프의 오일러 투어 개수는 $O(n^3)$ (혹은 $O(n^\omega)$) 시간 안에 구할 수 있다."BEST" Theorem: 방향그래프 $G$의 Eulerian Circuit 개수를 $\mathrm{ec}(G)$라 하고, 고정된 $w \in V(G)$에 대해 $w$를 루트로 하는 arb..