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

256 바이트 추가됨 ,  4년 전
편집 요약 없음
잔글 (→‎예)
{{다른 뜻 넘어옴|쾨니그의 정리|[[기수 (수학)|기수]]에 대한 정리|쾨니그의 정리 (집합론)}}
[[그림:Complete bipartite graph K3,2.svg|thumb|200px|이분 그래프의 예]]
[[File:Complete bipartite graph K32-RG001.svg|thumb|이분 그래프의 변별[[그래프 알고리즘 적용색칠]]]]
[[File:Complete bipartite graph K32-001.svg|thumb|2색변 이분 그래프의 예]]
 
 
=== 변별 알고리즘 ===
주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 그래프의 꼭짓점들을 [[깊이 우선 탐색]]으로 나열한 뒤, 각 꼭짓점들을 이웃 꼭짓점들과 다른 색으로 계속해서 칠해 나가면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 여부를 확인하면 된다. 이 알고리즘은 ''O''(|''V''|+|''E''|)이다.
[[File:Complete bipartite graph K32-RG001.svg|thumb|이분 그래프의 변별 알고리즘 적용]]
주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 [[순환 그래프]]는 이분 그래프가 아니다.
 
== 예 ==
0분 그래프는 공(空)그래프 (꼭짓점과 변이 없는 그래프) 밖에 없다. 1분 그래프는 이산 그래프 (즉, 아무런 변이 없는 그래프)와 동치인 개념이다.
 
모든 [[나무 (그래프)|나무]]는 ([[순환 (그래프 이론)|순환]]이 없으므로) 이분 그래프이다. 짝수 길이의 [[순환 (그래프 이론)|순환]]은 이분 그래프이지만, 홀수 길이의 [[순환 (그래프 이론)|순환]]은 이분 그래프가 아니다.
 
=== 완전 <math>k</math>분 그래프 ===