지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2013.5
- 수록면
- 113 - 120 (8page)
이용수
초록· 키워드
오류제보하기
본 논문은 지금까지 NP-완전인 난제로 알려진 4-색 정리를 O(n)선형시간 복잡도로 수기식과 컴퓨터를 활용하여 증명하는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프 G=(V₁,E₁)의 정점 집합 V를 최대 독립집합 C₁와 최소 정점 피복 집합 C₁으로 정확히 양분하는 기법을 적용하여 C₁에 첫 번째 색을 배정하고, C₁ 집합의 정점들로 축소된 연결 그래프 G=(V₂,E₂)를 대상으로 C₂와 C₂로 양분하여 C₂에 두 번째 색을 지정하였다. C₂ 집합의 정점들로 축소된 연결 그래프 G=(V₃,E₃)를 대상으로 C₃와 C₃로 양분하여 C₃에 세 번째 색을 지정하였다. 마지막으로C₃를 C₄로 하여 4번째 색을 배정하였다. 2개의 실제 지도 그래프와 2개의 평면 그래프를 대상으로 제안된 알고리즘을 적용한 결과 모든 그래프에서 채색수 χ(G)=4를 찾는데 성공하였다. 결국, 제안된 "4-색 알고리즘"은 평면 그래프의 4-색을 결정하는 일반적인 알고리즘으로 적용할 수 있을 것이다.
목차
등록된 정보가 없습니다.
참고문헌 (18)
참고문헌 신청
1. [단행본] - Wikipedia / 2013 / Graph Coloring / Wikimedia Foundation Inc
2. [단행본] - Wikipedia / 2008 / Four Color Theorem / Wikimedia Foundation Inc
3. [단행본] - R. Thomas / / The Four Color Theorem / School of Mathematics, Georgia Institute of Technology
4. [단행본] - M. Moore / 2006 / Four Color Theorem / Department of Mathematical Sciences, University of Arkansas
5. [인터넷자원] - I. Cahit / / The Four Color Theorem and Three Proofs
2. [단행본] - Wikipedia / 2008 / Four Color Theorem / Wikimedia Foundation Inc
3. [단행본] - R. Thomas / / The Four Color Theorem / School of Mathematics, Georgia Institute of Technology
4. [단행본] - M. Moore / 2006 / Four Color Theorem / Department of Mathematical Sciences, University of Arkansas
5. [인터넷자원] - I. Cahit / / The Four Color Theorem and Three Proofs
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0