이분 그래프: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) 잔글편집 요약 없음 |
|||
7번째 줄: | 7번째 줄: | ||
== 성질 == |
== 성질 == |
||
홀수 길이의 [[순환 그래프]]가 이분 그래프가 아니라는 점은 쉽게 증명할 수 있다. 아울러 다음과 같은 더 강력한 정리가 쉽게 증명된다. 그래프가 이분 그래프일 필요충분조건은 홀수 길이의 [[순환 (그래프 이론)|순환]]이 없다는 것이다. |
홀수 길이의 [[순환 그래프]]가 이분 그래프가 아니라는 점은 쉽게 증명할 수 있다. 아울러 다음과 같은 더 강력한 정리가 쉽게 증명된다. 그래프가 이분 그래프일 필요충분조건은 홀수 길이의 [[순환 (그래프 이론)|순환]]이 없다는 것이다. |
||
엥 이거 누구나 고칠수이씀? |
|||
== 알고리즘 == |
== 알고리즘 == |
2016년 6월 3일 (금) 05:53 판
그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 변이 X에 있는 꼭짓점과 Y의 꼭짓점을 잇는 형태로 되도록 꼭짓점의 집합을 두 개의 부분집합 X, Y로 나눌 수 있는 그래프이다. 다르게 표현하자면, 그래프의 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 경우 이분 그래프라고 한다. 같은 말로 색칠수 χ(G)가 2이하인 경우이다.
성질
홀수 길이의 순환 그래프가 이분 그래프가 아니라는 점은 쉽게 증명할 수 있다. 아울러 다음과 같은 더 강력한 정리가 쉽게 증명된다. 그래프가 이분 그래프일 필요충분조건은 홀수 길이의 순환이 없다는 것이다. 엥 이거 누구나 고칠수이씀?
알고리즘
주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 순환 그래프는 이분 그래프가 아니다.
바깥 고리
- “Graph, bipartite”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.