Matching과 Vertex cover

Matching이란, 어떠한 그래프에서 간선을 잘 고른 것이다.
이 때 이 간선들은 서로 어떠한 점에서도 만나지 않아야 한다.
즉, 그래프에서 한 간선을 잡고, 그 간선과 양 끝 점을 제외한 그래프에서 또 간선을 잡고, ... 이렇게 매칭시키는 것이다.

일반적으로 우리가 매칭이라는 단어를 들었을 때 드는 느낌대로 생각하면 된다. 위 그림에서 빨간색으로 색칠된 것이 매칭이다.

아무것도 선택하지 않아도 매칭이다. 임의의 갯수로 간선을 잡아도 안 겹치게 잡기만 하면 매칭이다.
그러나 정점을 선택하면 할수록 점점 정점이 채워지므로(?) 그 다음 매칭을 찾는 것이 점점 힘들어진다.
따라서 computational graph theory에서는 '최대 matching'을 찾는 것에 관심을 둔다.

Vertex cover이란, 어떠한 그래프에서 정점을 잘 고른 것이다.
이 때 이 정점들은 모든 간선을 커버해야 한다. 즉 모든 간선들은 이 정점들과 연결되어있다.
다음 그림은 vertex cover의 예이다.

모든 정점을 선택하는 것 또한 자명한 vertex cover이다.
따라서 computational graph theory에서는 '최소 vertex cover'를 찾는 것에 관심을 둔다.

이분(bipartite) 그래프에서, maximum matching과 minimum vertex cover의 갯수는 같다. 이 정리를 König's theorem이라고 한다.

Jenő Egerváry는 이 정리를 weighted graph로 확장시켰고, 헝가리의 수학자인 König과 Egerváry의 정리를 이용한 알고리즘이 Hungarian algorithm이다.