완전 이분 그래프

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

그래프 이론에서 완전 이분 그래프(完全二分graph, 영어: complete bipartite graph)란 꼭짓점의 집합이 서로 겹치지 않는 두 집합 X와 Y의 합집합이고 X의 모든 꼭짓점이 Y의 각각의 꼭짓점과 하나의 변으로 연결되어 있는 이분 그래프이다.

정의[편집]

집합 조각 분할

가 주어졌다고 하자. 이 집합의 분할에 대응하는 완전 분 그래프(영어: complete -partite graph)는 위와 같은 분할에 대하여 분 그래프를 이루는, 가장 변을 많이 갖는 그래프이다. 즉, 그 변의 집합은 다음과 같은 꼴이다.

집합의 크기가 각각 일 때, 이에 대응하는 완전 분 그래프는 로 표기한다.

일 경우, 이는 완전 그래프와 같다. 일 경우 이를 완전 이분 그래프(完全二分graph, 영어: complete bipartite graph), 일 경우 이를 완전 삼분 그래프(完全三分graph, 영어: complete tripartite graph)라고 한다.

성질[편집]

색칠[편집]

정의에 따라, 완전 분 그래프는 분 그래프이며, 그 채색수 이하이다.

특히, 만약 일 경우, 그 채색수이다.

크기[편집]

완전 분 그래프 의 꼭짓점의 수는

이며, 변의 수는

이다.

그래프의 평면성[편집]

평면 그래프그래프 마이너로 가질 수 없다. 반대로, 평면 그래프가 아닌 모든 그래프는 또는 그래프 마이너로 갖는다 (바그너 정리 영어: Wagner’s theorem)

[편집]

역사[편집]

이미 1669년에 아타나시우스 키르허가 완전 이분 그래프의 그림을 출판하였다.[1]

참고 문헌[편집]

  1. Knuth, Donald E. (2013). 〈Two thousand years of combinatorics〉. Wilson, Robin; Watkins, John J. 《Combinatorics: Ancient and Modern》 (영어). Oxford University Press. 7–37쪽. 

바깥 고리[편집]