독립간선집합 timer 1s memory 64MB

그래프 이론에서 매칭 또는 독립간선집합이란 공통 정점을 갖지 않는 간선의 집합을 의미한다. 그래프 집합 G = (V, E)가 주어질 때 G의 부분집합 M이 독립간선집합(매칭)이 되기 위해서는 M에 포함되어 있는 간선들은 같은 정점을 공유하지 않아야 한다.

정점의 개수가 n개( 3 <= n <= 10000)인 순환 그래프를 Cn 이라고 하자.

이때 순환 그래프 Cn에서 간선집합은 정점번호의 차가 1인 경우의 간선만 가능하여 E(Cn) = {{a, b} | |a-b| ≡ 1 mod n} 으로 정의 되며, 2정규 그래프로서 간선의 개수가 n개이다.

어렵게 느껴진다면 아래 예를 보자. 아래 그림의 예는 순환 그래프 C3, C4, C5, C6의 예이다.

순환 그래프 C4에서 독립간선집합(매칭) M을 찾아보면 아래와 같이 7가지 경우가 있다. 유의할 것은 간선을 선택하지 않는 경우도 한 가지 경우로 생각한다는 것이다.