완전 이분 그래프

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

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

|X|=m, |Y|=n인 경우 이 그래프를 Km,n으로 표현한다. 따라서 Km,n의 변의 개수는 mn개이다.

[편집]