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

1 바이트 제거됨 ,  4년 전
잔글
봇: 문단 이름 변경 (바깥 고리 → 외부 링크)
잔글
잔글 (봇: 문단 이름 변경 (바깥 고리 → 외부 링크))
:<math>V=V_1\sqcup V_2\sqcup\dotsb\sqcup V_k</math>
을 가질 수 있다면, <math>\Gamma</math>를 '''<math>k</math>분 그래프'''(-分graph, {{llang|en|<math>k</math>-partite graph}})라고 한다.
* 변으로 연결된 두 꼭짓점은 서로 다른 분할 성분에 속한다. 즉, 임의의 변 <math>(u,v)\in E</math>에 대하여, 만약 <math>u\in V_i</math>이며 <math>v\in V_j</math>라면, <math>i\ne j</math>이다.
즉, <math>\Gamma</math>의 [[색칠수]]가 <math>k</math> 이하이어야 한다.
 
{{각주}}
 
== 바깥외부 고리링크 ==
* {{eom|title=Graph, bipartite}}
* {{eom|title=König theorem}}

편집

1,901,761