László Babai

László Babai는 헝가리의 컴퓨터과학자이자 수학자다. 괴델 상을 받았고, 계산 이론과 알고리즘, 조합론, 군론을 연구한다. 그는 그래프 동형 판정(Graph Isomorphism)을 $\exp((\log n)^{O(1)})$ 시간에 푸는 알고리즘을 내놓았다. 그전까지 알려진 가장 좋은 시간은 $\exp(O(\sqrt{n \log n}))$이다.

그래프 동형 판정은 다음 문제다. 무방향 그래프 $A = (V_A, E_A)$와 $B = (V_B, E_B)$가 주어지고, $V_A = \{a_1, a_2, \ldots, a_{n_A}\}$, $V_B = \{b_1, b_2, \ldots, b_{n_B}\}$다. 두 조건이 모두 성립할 때, 그리고 그때만 $A$와 $B$는 동형이다.

1. $A$와 $B$의 정점 수가 같고 간선 수도 같다.
2. $\{u, v\} \in E_A$일 때, 그리고 그때만 $\{f(u), f(v)\} \in E_B$인 전단사 함수 $f : V_A \to V_B$가 있다.

즉 $A$의 정점에 이름을 다시 붙여 $B$를 만들 수 있다.

그래프 동형 판정이 P에 속하는지는 아직 모르고, NP-완전인지도 모른다. 그 도전의 첫걸음으로, 정점이 3개인 무방향 단순 그래프 두 개가 동형인지 판정하자.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어진다.

각 테스트 케이스는 그래프 두 개를 같은 형식으로 차례로 준다. 한 그래프의 설명은 1번부터 3번까지 번호가 붙은 정점 3개로 이루어진 무방향 단순 그래프의 간선 수 $m$ ($0 \le m \le 3$)으로 시작한다. 이어서 $m$개의 줄에 서로 다른 정수 $u$와 $v$ ($u \ne v$, $u, v \in \{1, 2, 3\}$)가 주어지고, 이는 정점 $u$와 정점 $v$를 잇는 간선이 있다는 뜻이다. 어떤 두 정점을 잇는 간선은 많아도 하나다.

각 테스트 케이스마다 두 그래프가 동형이면 yes를, 아니면 no를 한 줄에 출력한다.