위키백과

그래프 색칠: 두 판 사이의 차이

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
3번째 줄:
 
== 정의 ==
(단순 무향) 그래프 <math>\Gamma</math>의 '''색칠''' <math>(C,c)</math>은 집합 <math>C</math> 및 함수 <math>c\colon V(\Gamma)\to C</math>의 순서쌍이된다순서쌍이다. 이 경우, 임의의 변 <math>v_1v_2\in E(\Gamma)</math>에 대하여 <math>c(v_1)\ne c(v_2)</math>이어야만 한다. 색칠 <math>(C,c)</math>에서, <math>C</math>의 원소를 '''색'''(色, {{llang|en|colo(u)r}})이라고 한다.
 
그래프 <math>\Gamma</math>의 두 색칠 <math>(C,c)</math>, <math>(C',c')</math>이 주어졌을 때, 만약 [[전단사함수]] <math>f\colon C\to C'</math>가 존재하여 <math>c'=f\circ c</math>인 경우, 두 색칠이 서로 [[동형]]이라고 한다.
원본 주소 "https://ko.wikipedia.org/wiki/그래프_색칠"