[ROAD TO ULTIMATE MATHCHUNG] 1. Graph Counting

https://www.acmicpc.net/problem/18453

문제를 아주 간단히 요약하자면, 그래프 자체로는 완전매칭이 없는데, 간선을 아무거나 하나 추가하면 완전매칭이 생기는 non-isomorphic한 정점 \( 2n\)개의 그래프의 개수를 세는 것이다(\(n\le 500000\)).

 

한가지 중요한 정리를 사용한다:

https://en.wikipedia.org/wiki/Tutte%E2%80%93Berge_formula

Tutte–Berge formula - Wikipedia

그냥 간단히 말하면, 완전매칭이 존재하는 그래프라면, 내가 그래프에서 몇개의 정점들을 제거하였을 때, 홀수 컴포넌트의 개수가 제거한 정점보다는 항상 적거나 같다는 것이 필요충분조건이라는 것이다.

 

이제, 문제의 조건을 만족하는 그래프 \(G\)를 생각하자. G에서, 다른 모든 정점들과 연결된 정점들의 집합을 S라고 하자.

 

Claim) S를 제거하였을 때, G의 남은 컴포넌트들은 clique를 이룬다.

pf)

일단, G는 완전매칭이 존재하지 않으므로, 어떤 정점들의 집합 T가 존재해서 T를 제거하였을 때 홀수 컴포넌트의 개수가 T의 크기보다 큰 경우가 존재한다. 한편, S에 속한 정점이 T에 속하지 않는다면 그 정점이 다른 모든 정점들과 연결되어있으므로, 홀수 컴포넌트의 크기는 1보다 작거나 같으므로 모순이 된다. 즉, S는 T에 속한다. 

 

T들중 가장 크기가 작은 것을 고르자.

 

1. T=S인 경우

이 경우, G의 어떤 컴포넌트 C가 완전그래프가 아닌 경우를 생각해보자. 해당 컴포넌트 C에 아무 간선을 추가하면, G-S의 홀수 컴포넌트의 개수는 변화가 없기 때문에, G가 간선을 하나 추가했음에도 불구하고 완전매칭이 존재하지 않게 되어 모순이다.

 

2. T!=S인 경우

이 경우, T-S에 속한 정점 v를 하나 잡고, v와 연결되지 않은 아무 정점 사이에 간선을 추가해주면, G-T의 홀수 컴포넌트의 개수는 변화가 없기 때문에 모순이다.

 

즉, T=S이며, G-T의 모든 컴포넌트 C는 완전그래프이다. Q.E.D.

 

한편, S가 G의 조건을 위배시키는 가장 작은 컴포넌트라는 점으로부터, 모든 G-S의 clique의 크기가 홀수라는 것을 알 수 있는데, 이것의 증명은 유튜브 어딘가에 굴러다니는 KAIST의 그래프이론개론 영상을 시청하면 증명이 가능하다.

 

따라서, 결국 S의 크기가 x라고 하면, 남은 컴포넌트들의 가짓수는 n-x개의 정점들을 x+2(by Tutte-Berge Theorem)개의 홀수로 분할하는 가짓수와 동일하게 되며, 이를 열심히 정리해서 전부 합치면 P(n+1)-1이 된다.

 

이것을 계산하는 방법은 https://cocoachan.tistory.com/28?category=1152015를 참고하라.