매칭

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

수학의 한 분야인 그래프 이론에서 매칭(matching)이란, 서로 만나지 않는 변들의 집합을 뜻한다.

정의[편집]

그래프 G=(V,E)에 대하여 M이 G의 매칭이라는 말은 M이 E의 부분집합이면서 M의 서로 다른 두 변은 인접하지 않는다는 뜻이다.

최대 매칭(maximum matching)은 변의 개수가 최대인 매칭이다. 똑같은 그래프에 대해서 최대 매칭이 여러 개 존재할 수도 있다.

극대 매칭(maximal matching)은 변을 추가하면 더 이상 매칭이 아니게 되는 매칭이다. 최대 매칭은 극대 매칭이지만, 일반적으로 역은 성립하지 않는다.

완벽 매칭(perfect matching)은 모든 꼭지점을 덮는 매칭이다. 따라서 완벽 매칭은 꼭지점이 짝수개인 경우에만 존재할 수 있다. 완벽 매칭은 당연히 최대 매칭이다.

관련 정리[편집]

  • Berge의 정리: 어떤 매칭이 극대 매칭일 조건에 대한 정리이다.
  • Tutte의 정리: 완벽 매칭이 존재할 조건에 대한 정리이다.
  • Tutte-Berge 공식: 최대 매칭의 크기를 그래프 상에 정의된 어떤 함수값의 최소값으로 나타낼 수 있다.