둘러보기 메뉴
검색
바뀐글
임의글
개인 도구
가입하기
로그인
도움말
도움말
질문게시판
자주 묻는 질문
커뮤니티
실시간 채팅방
가입인사게시판
자유게시판
뉴스게시판
제재안게시판
최근 토론
페미위키
공지사항
개선 요청
바뀐글
임의글
파일 올리기
다면 분류 목록
특수 문서 목록
오색 정리 문서 원본 보기
이름공간
문서
토론
주시
도구
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
위키베이스 항목
행위
보기
읽기
원본 보기
역사 보기
←
오색 정리
문서 편집 권한이 없습니다. 다음 이유를 확인해주세요.
요청한 명령은 다음 중 하나의 권한을 가진 사용자에게 제한됩니다:
사용자
,
Seeders
.
문서를 고치려면 이메일 인증 절차가 필요합니다.
사용자 환경 설정
에서 이메일 주소를 입력하고 이메일 주소 인증을 해주시기 바랍니다.
문서의 원본을 보거나 복사할 수 있습니다.
== 진술 == '''오색 정리(Five color theorem)'''은 임의의 [[평면그래프]]를 다섯 가지 색을 이용하여 칠할 수 있다는 [[명제]]다. 다시 말해, 평면그래프 ''G''의 색의 개수를 <math>\chi(G)</math>라 하면, : <math>\chi(G)\le 5</math> 이다. == 증명 == [[파일:fouredge.png|섬네일|250px|<math>\deg v \le 4</math>이면 ''v''에는 언제나 인접한 꼭짓점과 다른 색을 칠하면 된다.]] 그래프의 모서리의 수 ''v''에 대한 [[수학적 귀납법]]으로 증명하려고 한다. * 기본 단계: <math>v=1</math>이면 평면그래프를 한 가지 색을 이용하여 칠할 수 있다. * 귀납법 단계: <math>v=n-1</math>인 평면그래프를 다섯 가지 색을 이용하여 칠할 수 있다고 가정하자. <math>v=n</math>일 때, [[오일러의 다면체 정리]]에 의하여, 평면그래프 ''G''는 차수가 5 이하인 꼭짓점을 반드시 하나 가진다.<ref>박승안 (2012). 『이산수학』(제3판). 경문사. p. 242. {{ISBN|9788961055345}}</ref> 이 꼭짓점을 ''x''라 하자. ''G''에서 ''x''를 제거한 그래프 <math>G' = G\setminus x</math>의 꼭짓점은 ''n''-1개이므로, ''G' ''는 다섯 가지 색을 이용하여 칠할 수 있다. 따라서 ''G''를 다섯 개 색으로 칠할 수 있음을 보이려면 ''x''를 잘 색칠하면 된다. ** <math>\deg x \le 4</math>일 때, v와 인접한 꼭짓점의 색은 최대 네 가지에 불과하므로, 인접한 꼭짓점의 색이 아닌 걸 골라서 ''x''에 색칠하면 된다. ** <math>\deg x =5 </math>라고 하자. 이때, ''x''와 인접한 꼭짓점을 시계방향으로 <math>v_1,v_2,v_3,v_4,v_5</math>로 지정하고, 색을 1, 2, 3, 4, 5로 부여하자. ''G' ''의 부분그래프 <math>G_{1,3}</math>을 ''G' ''에서 색이 1과 3인 것을 모두 고르고 모서리로 연결한 그래프라고 하자. 이때 <math>G_{1,3}</math>에서 ''v''<sub>1</sub>에서 ''v''<sub>3</sub>로 가는 길이 없다면, ''v''<sub>1</sub>의 색을 ''v''<sub>3</sub>의 색으로 바꾸고 ''v''<sub>1</sub>과 연결된 점의 색 1, 3을 서로 바꾸면 된다. 이때 ''v''<sub>1</sub>과 ''v''<sub>3</sub>의 색이 모두 3이므로, ''x''를 1로 칠할 수 있다. [[파일:Proofwhennotcycle.png|400px|가운데]] [[파일:proof13connected.png|섬네일|250px|음... <math>v_2,v_4</math>를 다른 모서리에 닿지 않고 연결하려면 {{ㅊ|지면을 뚫으면 되겠군}}그런 거 없다.]] :: <math>G_{1,3}</math>에서 ''v''<sub>1</sub>에서 ''v''<sub>3</sub>로 가는 길이 있다고 하자. 그러면 이제 얘 말고 ''G' ''에서 색이 2와 4인 것을 모두 고르고 모서리로 연결한 그래프인 <math>G_{2,4}</math>에 대해 생각하자. <math>G_{2,4}</math>에서 ''v''<sub>2</sub>에서 ''v''<sub>4</sub>로 가는 길이 없다면 <math>G_{1,3}</math>의 경우처럼 색을 바꾸면 되는데, ''v''<sub>2</sub>에서 ''v''<sub>4</sub>로 가는 길이 있다면 ''G''가 평면그래프라는 것에 [[모순]]이다! 따라서 <math>G_{2,4}</math>에서 ''v''<sub>2</sub>에서 ''v''<sub>4</sub>로 가는 길은 없다. 따라서 ''G''를 다섯 가지 색으로 칠할 수 있으므로 언제나 원하는 결론을 얻는다. 위와 같은 방법을 [[켐페 사슬]]이라고 부른다. [[알프레드 켐페]]가 원래 [[사색 정리]]의 증명을 발표(?)하면서 쓰인 개념이었으나, 오류가 있음이 발견되었지만 오색 정리를 쉽게 증명하는 등의 다른 곳에 매우 유용함이 알려졌다. == 같이 보기 == * [[사색 정리]]: 오색 정리보다 강력한 정리로, 임의의 평면그래프는 네 가지 색을 이용해 칠할 수 있다. [[1976년]]에 컴퓨터를 이용해 증명하였다. * [[토마슨의 정리]]: 오색 정리를 함의하는 또 하나의 정리로, 임의의 고리 없는 평면그래프가 5-선택 가능하다는 정리이다. 채색 수는 언제나 선택 수 이하이므로, 오색 정리가 도출된다. == 외부 링크 == * [https://proofwiki.org/w/index.php?title=Five_Color_Theorem&oldid=191398 Five Color Theorem]. (2014, August 13). ''ProofWiki'', . Retrieved 14:39, May 5, 2015. * [http://mapa-kodow-pocztowych.pl/ Mapa kodów pocztowych - Polska]: [[폴란드]] 구역을 다섯 가지 색으로 칠해 보여준다. 2015년 9월 12일 확인. ==출처== <references /> [[분류:분류수정중]] [[분류:그래프 이론]] [[분류:수학 정리]]
이 문서에서 사용한 틀:
틀:Catalog lookup link
(
원본 보기
)
틀:Error-small
(
원본 보기
)
틀:ISBN
(
원본 보기
)
틀:Main other
(
원본 보기
)
틀:Trim
(
원본 보기
)
틀:Yesno-no
(
원본 보기
)
틀:ㅊ
(
원본 보기
)
모듈:@ko/Arguments
(
원본 보기
)
모듈:@ko/Catalog lookup link
(
원본 보기
)
모듈:@ko/Check isxn
(
원본 보기
)
모듈:Citation/CS1/styles.css
(
원본 보기
)
오색 정리
문서로 돌아갑니다.
다른 언어