부합 (그래프 이론)

위키백과, 우리 모두의 백과사전.
(매칭에서 넘어옴)
이동: 둘러보기, 검색
극대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다.
최대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다.

그래프 이론에서, 부합(附合, 영어: matching 매칭[*])은 서로 만나지 않는 변들의 집합이다.

정의[편집]

그래프 \Gamma부합 M\subset E(\Gamma)은 다음을 만족시키는, 변들의 부분집합이다.

  • 임의의 e_1,e_2\in M에 대하여, e_1e_2가 하나 이상의 꼭짓점을 공유한다면 e_1=e_2이다.

\Gamma의 부합들은 포함 관계에 따라서 부분 순서 집합을 이룬다. 이 부분 순서에 대하여 극대인 부합을 극대 부합(영어: maximal matching)이라고 한다. 최대 부합(영어: maximum matching)은 극대 부합 가운데, 변의 수가 최대인 부합이다.

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

성질[편집]

  • 베르주 보조정리(영어: Berge’s lemma): 어떤 부합이 극대 부합일 조건에 대한 정리이다.
  • 텃 정리(영어: Tutte’s theorem): 완벽 부합이 존재할 조건에 대한 정리이다.
  • 텃-베르주 공식(영어: Tutte–Berge formula): 최대 부합의 크기를 그래프 위에 정의된 어떤 함수값의 최솟값으로 나타낼 수 있다.

바깥 고리[편집]

같이 보기[편집]