평면 그리기

이 문제에서는 유한하고 단순하며 연결된 무향 그래프만 다룬다. 평면 그래프는 두 변이 서로 가로지르지 않도록, 즉 변끼리 끝점에서만 만나도록 평면에 그릴 수 있는 그래프다. 그런 그림을 그 그래프의 평면 그리기라고 부른다. 평면 그래프와 평면 그리기의 예는 그림 1에 있다. 모든 평면 그래프는 변이 전부 서로 만나지 않는 선분인 평면 그리기를 가진다는 사실이 알려져 있다.

그림 1. 평면 그래프와 평면 그리기: (a) 꼭짓점이 네 개인 완전 그래프, (b) 곡선 변으로 그린 평면 그리기, (c) 선분으로만 그린 평면 그리기.

주어진 그래프가 평면인지 판정하는 문제는 오래 연구되었고, 알려진 알고리즘은 대부분 꼭짓점 수에 선형인 시간에 동작한다. 평면성 판정 프로그램을 쓰는 사람은 예 또는 아니오라는 답만으로 만족하지 못할 때가 있다. 옳다고 증명된 알고리즘도 구현하는 과정에서 실수가 들어가기 때문이다. 인증 알고리즘 연구가 여기서 출발한다.

사용자가 입력 $X$를 주고 프로그램이 $Y$를 출력했을 때, $Y$가 $X$에 대한 올바른 출력인지 버그로 망가진 값인지 사용자는 보통 알 수 없다. 인증 알고리즘은 출력마다 그 출력이 버그로 망가지지 않았음을 보이는 인증서 $Z$를 함께 내놓는다. 사용자는 $Z$를 직접 살펴보거나 프로그램으로 검사해서 출력이 옳다고 확신하거나, 버그가 있다고 판단해 출력을 버린다. $Z$를 확인하는 과정은 검사기로 자동화한다. 검사기는 $Z$가 입력 $X$에 대해 출력 $Y$가 옳음을 증명하는지 검증하는 알고리즘이다.

평면성 판정 문제의 인증 알고리즘이 내놓아야 할 인증서를 생각해 보자. 입력 그래프가 평면이면 평면 그리기가 그대로 인증서가 된다. 평면이 아니면 쿠라토프스키 정리를 쓴다. 이 정리에 따르면 그래프가 평면일 필요충분조건은 $K_5$의 세분이거나 $K_{3,3}$의 세분인 부분그래프를 갖지 않는 것이다. 그림 2(a)의 $K_5$는 꼭짓점이 다섯 개인 완전 그래프이고, 그림 2(b)의 $K_{3,3}$은 양쪽에 꼭짓점이 세 개씩 있는 완전 이분 그래프다. 그래프의 세분은 그림 2(c)와 2(d)처럼 변 위에 차수가 2인 꼭짓점을 끼워 넣는 조작을 반복해서 얻는다. 즉 그래프의 각 변을 두 끝점을 잇는 경로로 바꾸되, 어떤 경로의 내부 꼭짓점도 다른 경로 위나 원래 그래프 위에 놓이지 않게 한 것이다. 따라서 그래프가 평면이 아니면 $K_5$의 세분이거나 $K_{3,3}$의 세분인 연결 부분그래프가 좋은 인증서다.

그림 2. $K_5$, $K_{3,3}$, 그리고 두 그래프의 세분: (a) $K_5$, (b) $K_{3,3}$, (c) $K_5$의 세분, (d) $K_{3,3}$의 세분.

$K_5$나 $K_{3,3}$의 세분인지 확인하는 일과 달리, 어떤 그림이 정말 평면인지 확인하는 일은 쉽지 않다. 그래서 긍정 답의 인증서로는 평면 그리기 대신 아래에 정의하는 조합적 매장을 쓴다. 세 꼭짓점이 한 직선 위에 놓이지 않는 선분 그리기는 각 꼭짓점 $v$마다 $v$에 인접한 꼭짓점의 순환 순서를 하나로 정한다. 여기서는 시계 방향 순서를 쓴다. 이런 순환 순서 전체를 조합적 매장이라고 한다. 그림 3은 평면 그리기와 거기에 대응하는 조합적 매장을 보여 준다. 예를 들어 순환 순서 $(2,3,4)$에서 2 다음은 3, 3 다음은 4, 4 다음은 2다.

그림 3. 평면 그리기와 조합적 매장: (a) 평면 그리기, (b) 대응하는 조합적 매장, (c) 조합적 매장의 경계 순환 네 개.

조합적 매장이 정말 평면인지 확인하려면 경계 순환이라는 개념이 필요하다. 무향 변 하나를 방향이 반대인 유향 변 두 개로 바꾼 유향 그래프를 생각한다. 유향 변 $(u, v)$에서 시작하는 경계 순환은 이렇게 정의한다. $v$의 순환 순서에서 $u$ 다음 꼭짓점이 $u'$이면 다음 변은 $(v, u')$이다. 시작 변으로 돌아올 때까지 이 과정을 반복한다. 그림 3(c)의 유향 그래프에서 $(5,4)$로 시작하면, 꼭짓점 4의 순환 순서 $(5,2,1,3)$에서 5 다음이 2이므로 다음 변은 $(4,2)$다. 계속하면 경계 순환 $(5,4) \to (4,2) \to (2,3) \to (3,4) \to (4,5) \to (5,4)$를 얻는다.

조합적 매장은 언제나 유향 변 전체를 경계 순환들로 분할한다. 또 꼭짓점이 $n > 1$개이고 변이 $m$개인 연결 그래프에서, 경계 순환이 $f$개인 조합적 매장이 평면일 필요충분조건은 $n - m + f = 2$다. 두 사실 모두 증명되어 있다. 그러므로 경계 순환의 개수를 세어 이 식이 성립하는지 보면 충분하다.

입력 그래프 $X$와 평면성 판정 인증 알고리즘의 출력 $Y$, 인증서 $Z$가 주어졌다고 하자. $Y$는 예 또는 아니오이고, $Z$는 답에 따라 조합적 매장이거나 $X$의 부분그래프다. 검사기 프로그램은 두 모듈로 나눌 수 있다. 첫째 모듈은 긍정 답이면 조합적 매장 $Z$가 평면인지 검사하고, 부정 답이면 부분그래프 $Z$가 $K_5$의 세분이거나 $K_{3,3}$의 세분인지 검사한다. 둘째 모듈은 답에 따라 $Z$가 $X$의 조합적 매장인지 또는 $X$의 부분그래프인지 검사한다. 첫째 모듈을 작성하라. 그래프 $X$의 꼭짓점에는 1번부터 $n$번까지 번호가 붙어 있다.

첫째 줄에 인증 알고리즘의 출력을 나타내는 정수가 주어진다. 긍정 답이면 1, 부정 답이면 -1이다. 둘째 줄에 그래프 $X$의 꼭짓점 수 $n$이 주어진다 ($2 \le n \le 5000$).

긍정 답이면 이어서 $n$개의 줄에 조합적 매장이 주어진다. $k$번째 줄은 $d_k$와 꼭짓점 번호 $x_1, x_2, \dots, x_{d_k}$로 이루어지고, 꼭짓점 $k$의 순환 순서 $(x_1, x_2, \dots, x_{d_k})$를 뜻한다. 이 $n$개의 줄은 꼭짓점이 $n$개인 연결 단순 그래프의 조합적 매장을 나타낸다. 한 줄 안에 같은 번호가 두 번 나오지 않고, $u$가 $v$의 목록에 있으면 그때에만 $v$가 $u$의 목록에 있다. 이 그래프의 변 수 $m$은 $1 \le m \le 50000$을 만족한다.

부정 답이면 이어서 부분그래프의 꼭짓점 수 $n'$과 변 수 $m'$이 한 줄에 주어지고 ($1 \le n' \le n$, $1 \le m' \le 50000$), 그다음 $m'$개의 줄에 각각 두 정수 $u$와 $v$가 주어져 꼭짓점 $u$와 꼭짓점 $v$를 잇는 변을 나타낸다. 모든 꼭짓점 번호는 $\{1, \dots, n\}$에 들어 있다. 인증서에는 버그가 있을 수 있다. 같은 변이 두 번 나올 수도 있고, 두 끝점이 같은 변이 있을 수도 있으며, 그래프가 연결이 아닐 수도 있고, 목록에 나오는 서로 다른 꼭짓점의 개수가 $n'$과 다를 수도 있다.

한 줄을 출력한다.

긍정 답이면 주어진 조합적 매장이 평면일 때 1을, 아니면 -1을 출력한다. 즉 변 수를 $m$, 경계 순환의 개수를 $f$라고 할 때 $n - m + f = 2$이면 1, 아니면 -1이다.

부정 답이면 주어진 $m'$개의 변이 $K_5$의 세분이나 $K_{3,3}$의 세분을 이룰 때 1을, 아니면 -1을 출력한다. 다음 조건을 모두 만족할 때에만 세분으로 인정한다. 같은 변이 두 번 나오지 않는다. 두 끝점이 같은 변이 없다. 변 목록에 나오는 서로 다른 꼭짓점의 개수가 $n'$과 같다. 그래프가 연결이다. 모든 꼭짓점의 차수가 2 이상이다. 내부 꼭짓점의 차수가 모두 2인 극대 경로를 각각 변 하나로 줄였을 때 결과가 정확히 $K_5$이거나 정확히 $K_{3,3}$이다. 줄인 결과에 고리나 평행한 변이 생기면 세분이 아니다.