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

6 바이트 추가됨 ,  14년 전
잔글 (robot Adding: fr:Graphe biparti; cosmetic changes)
== 이분 그래프인지 확인하는 [[알고리즘]] ==
주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭지점 하나를 빨강으로 칠한 후 이웃 꼭지점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭지점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어 삼각형 모양으로 세 개의 꼭지점이 세 개의 간선으로 연결된 그래프는 이분 그래프가 아니다.
by ICU
 
[[분류:그래프 이론]]
 
익명 사용자