쾨니그의 정리

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

그래프 이론조합론에서, 쾨니그의 정리(Kőnig의定理, 영어: Kőnig’s theorem)는 이분 그래프에 대한 최소 꼭짓점 덮개 문제와 최대 부합 문제가 서로 동치라는 정리다.

정의[편집]

최대 부합의 변(청색) 수는 최소 꼭짓점 덮개의 꼭짓점(적색) 수와 같다.

어떤 그래프 \Gamma꼭짓점 덮개(영어: vertex cover) C\subset V(\Gamma)는 다음을 만족시키는 집합이다.

  • 모든 변 e\in E(\Gamma)에 대하여, e와 접하는 c\in C가 존재한다.

최소 꼭짓점 덮개는 크기가 최소인 꼭짓점 덮개이다.

쾨니그의 정리에 따르면, 이분 그래프 \Gamma최대 부합 M\subset E(\Gamma) 및 최소 꼭짓점 덮개 C\subset V(\Gamma)에 대하여,

|M|=|C|

이다.

조합적 집합론에서는 쾨니그의 정리를 일반화하는 홀 결혼 정리가 존재한다. 쾨니그의 정리와 홀의 정리는 서로 동치이며, 이들은 딜워스의 정리와도 동치이다.

역사[편집]

헝가리의 수학자 쾨니그 데네시1931년에 증명하였다.[1][2]:289

참고 문헌[편집]

  1. (헝가리어) Kőnig Dénes (1931년). Gráfok és mátrixok. 《Matematikai és Fizikai Lapok》 38: 116–119. Zbl 0003.32803.
  2. (한국어) 윤영진 (2007년). 《새로운 조합수학》. 교우사. ISBN 978-89-8172-379-8

바깥 고리[편집]