이분 그래프: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) 편집 요약 없음 |
|||
1번째 줄:
[[그림:Complete bipartite graph K3,2.svg|thumb|200px|이분 그래프의 예]]
[[그래프 이론]]에서, '''이분 그래프'''(二分graph, {{llang|en|bipartite graph}})란
다르게 표현하자면, 그래프의 꼭지점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭지점을 포함하도록 색칠할 수 있는 경우 이분 그래프라고 한다.
같은 말로 [[색칠수]] χ(G)가 2이하인 경우이다.
== 성질 ==
홀수 길이의 회로가 이분 그래프가 아니라는 점은 쉽게 증명할 수 있다. 아울러 다음과 같은 더 강력한 정리가 쉽게 증명된다. 그래프가 이분그래프일 필요충분조건은 홀수 길이의 회로가 없다는 것이다.
==
주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭지점 하나를 빨강으로 칠한 후 이웃 꼭지점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭지점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어 삼각형 모양으로 세 개의 꼭지점이 세 개의 간선으로 연결된 그래프는 이분 그래프가 아니다.
== 바깥 고리 ==
* {{eom|title=Graph, bipartite}}
[[분류:그래프 이론]]
|