본문으로 이동

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

241 바이트 추가됨 ,  4년 전
편집 요약 없음
0분 그래프는 공(空)그래프 (꼭짓점과 변이 없는 그래프) 밖에 없다. 1분 그래프는 이산 그래프 (즉, 아무런 변이 없는 그래프)와 동치인 개념이다.
 
모든 [[나무 (그래프 이론)|나무]]는 ([[순환 (그래프 이론)|순환]]이 없으므로) 이분 그래프이다. 짝수 길이의 [[순환 (그래프 이론)|순환]]은 이분 그래프이지만, 홀수 길이의 [[순환 (그래프 이론)|순환]]은 이분 그래프가 아니다.
 
=== 완전 <math>k</math>분 그래프 ===
| volume = 38
| 날짜 = 1931
| pages = 116–119 | zbl = 0003.32803 | 언어=hu}}</ref>와 에게르바리 예뇌({{llang|hu|Egerváry Jenő}}, 1891~1958)<ref>{{저널 인용|성=Egerváry|이름=Jenő|날짜=1931|제목=Matrixok kombinatorius tulajdonságairól|저널=Matematikai és Fizikai Lapok|권=38|쪽=16–28|언어=hu}}</ref>가 각자 독자적으로 1931년에 증명하였다.
 
== 참고 문헌 ==
* {{매스월드|id=KoenigsLineColoringTheorem|title=König's Line Coloring Theorem}}
* {{매스월드|id=Koenig-EgevaryTheorem|title=König-Egeváry Theorem}}
* {{nlab|id=bipartite graph|title=Bipartite graph}}
 
[[분류:그래프 이론]]