이분 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
이분 그래프의 예
위 그래프의 그래프 색칠
2색변 이분 그래프의 예

그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

정의[편집]

그래프 자연수 가 주어졌다고 하자. 만약 가 다음과 같은 조건을 만족시키는 집합의 분할

을 가질 수 있다면, 분 그래프(-分graph, 영어: -partite graph)라고 한다.

  • 변으로 연결된 두 꼭짓점은 서로 다른 분할 성분에 속한다. 즉, 임의의 변 에 대하여, 만약 이며 라면, 이다.

즉, 색칠수 이하이어야 한다.

일 때, 이를 이분 그래프라고 한다. 마찬가지로, 일 때, 이를 삼분 그래프(三分graph, 영어: tripartite graph)라고 한다.

성질[편집]

임의의 유한 그래프 에 대하여 다음 두 조건이 서로 동치이다.

  • 이분 그래프이다.
  • 홀수 길이의 순환이 존재하지 않는다.

특히, 예를 들어 홀수 길이의 순환 그래프는 이분 그래프가 될 수 없다.

이분 그래프의 색칠수는 2 이하이므로, 비징의 정리에 대하여, 이분 그래프는 항상 1종 그래프이다. (꼭짓점의 최대 차수가 1 이하인 그래프는 자명하게 1종 그래프이다.)

쾨니그 정리[편집]

쾨니그 정리에 따르면, 이분 그래프에서, 최대 부합의 변(청색) 수는 최소 꼭짓점 덮개의 꼭짓점(적색) 수와 같다.

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

구체적으로, 어떤 그래프 꼭짓점 덮개(영어: vertex cover) 는 다음을 만족시키는 집합이다.

  • 모든 변 에 대하여, 와 접하는 가 존재한다.

최소 꼭짓점 덮개(영어: minimal vertex cover)는 포함 관계에 대하여 최소 원소인 꼭짓점 덮개이다.

쾨니그 정리에 따르면, 유한 이분 그래프 최대 부합 및 최소 꼭짓점 덮개 에 대하여,

이다.[1]:289

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

변별 알고리즘[편집]

주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 그래프의 꼭짓점들을 깊이 우선 탐색으로 나열한 뒤, 각 꼭짓점들을 이웃 꼭짓점들과 다른 색으로 계속해서 칠해 나가면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 여부를 확인하면 된다. 이 알고리즘은 O(|V|+|E|)이다.

[편집]

0분 그래프는 공 그래프 (꼭짓점과 변이 없는 그래프) 밖에 없다. 1분 그래프는 이산 그래프 (즉, 아무런 변이 없는 그래프)와 동치인 개념이다.

모든 나무는 (순환이 없으므로) 이분 그래프이다. 짝수 길이의 순환은 이분 그래프이지만, 홀수 길이의 순환은 이분 그래프가 아니다.

완전 분 그래프[편집]

집합 조각 분할

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

데생당팡[편집]

리만 곡면에 대하여, 어떤 유한 평면 이분 그래프를 대응시킬 수 있다. 이를 데생당팡이라고 한다.

역사[편집]

쾨니그 정리는 쾨니그 데네시[2]에게르바리 예뇌[3]가 각자 독자적으로 1931년에 증명하였다.

참고 문헌[편집]

  1. 윤영진 (2007). 《새로운 조합수학》. 교우사. ISBN 978-89-8172-379-8. 
  2. Kőnig Dénes (1931). “Gráfok és mátrixok”. 《Matematikai és Fizikai Lapok》 (헝가리어) 38: 116–119. Zbl 0003.32803. 
  3. Egerváry, Jenő (1931). “Matrixok kombinatorius tulajdonságairól”. 《Matematikai és Fizikai Lapok》 (헝가리어) 38: 16–28. 

외부 링크[편집]