꼬인 전선

각 전선 $i$를 현재 두 끝점 사이의 구간으로 생각하자.

도달 가능한 배치

다음 보조정리를 사용한다.

처음에 $i$번 전선이 $[a_i,b_i]$를 연결한다고 하자. 길이 $2N$의 수열 $C$에서 각 번호가 정확히 두 번 나타난다. 각 $i$에 대해 $i$가 나타나는 두 위치가 모두 $[a_i,b_i]$ 안에 있는 것과, $C$가 연산으로 도달 가능한 것은 동치이다.

한 번의 연산에서 두 전선의 새 끝점은 각각 그 전선의 기존 두 끝점 사이에 있다. 따라서 도달 가능한 모든 배치는 위 조건을 만족한다.

역방향은 표준적인 uncrossing 보조정리로 증명할 수 있다. 현재 배치와 목표 배치의 같은 번호 간선을 겹쳐 그리면 짝수 길이의 교대 사이클들로 분해된다. 현재 배치와 목표 배치가 다르면, 어떤 교대 사이클에는 현재의 교차 간선 두 개가 존재하며 그 교차를 문제의 방향으로 풀어도 각 목표 간선은 같은 번호의 새 구간 안에 남는다. 이 연산은 현재 구간 길이의 합을 엄격히 감소시킨다. 이를 반복하고 구간 길이의 합에 대해 귀납하면 목표 배치에 도달한다.

따라서 문제는 다음 스케줄링 문제와 같다.

• 전선 $i$는 번호가 $i$인 동일한 작업 두 개를 가진다.
• 두 작업은 각각 $a_i$ 이상 $b_i$ 이하의 위치에 배치해야 한다.