본문으로 이동

"이분 그래프"의 두 판 사이의 차이

2 바이트 추가됨 ,  4년 전
잔글
편집 요약 없음
잔글
특히, 예를 들어 홀수 길이의 [[순환 그래프]]는 이분 그래프가 될 수 없다.
 
=== 변별 알고리즘 ===
[[File:Complete bipartite graph K32-RG001.svg|thumb|이분 그래프의 변별 알고리즘 적용]]
주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 [[순환 그래프]]는 이분 그래프가 아니다.