매칭
위키백과 ― 우리 모두의 백과사전.
수학의 한 분야인 그래프 이론에서 매칭(영어: matching)이란, 서로 만나지 않는 변들의 집합을 뜻한다.
[편집] 정의
그래프 G=(V,E)에 대하여 M이 G의 매칭이라는 말은 M이 E의 부분집합이면서 M의 서로 다른 두 변은 서로 인접하지 않는다는 뜻이다.
최대 매칭(영어: maximum matching)이란 변의 개수가 최대인 매칭을 뜻한다.
극대 매칭(영어: maximal matching)이란 더 이상 다른 변을 추가하면 매칭이 되지 않는 매칭을 뜻한다.
완벽 매칭(영어: perfect matching)이란 모든 꼭지점을 덮은 매칭이다.
[편집] 관련 정리
- Berge의 정리: 어떤 매칭이 극대 매칭일 조건에 대한 정리이다.
- Tutte의 정리: 완벽 매칭이 존재할 조건에 대한 정리이다.
- Tutte-Berge 공식: 최대 매칭의 크기를 그래프 상에 정의된 어떤 함수값의 최소값으로 나타낼 수 있다.
 |
이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |
