최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.18 no.5, 2013년, pp.113 - 120
This paper proposes an algorithm that proves an NP-complete 4-color theorem by employing a linear time complexity where
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
4-색 정리에 대한 증명을 종결하기 위해 필요한 것은? | 결국, 컴퓨터의 등장으로 해법이 제시되었지만 컴퓨터 해법은 논쟁의 대상이 되고 있다. 4-색 정리에 대한 증명을 종결하기 위해서는 수기식으로 증명할 수 있는 알고리즘 제안이 필수적이라 할 수 있다. 본 연구의 목적은 4-색 정리에 대해 수기식으로 증명할 수 있는 알고리즘을 제시함으로서 4-색 정리에 대한 논쟁을 종식시키고자 한다. | |
Appel과 Harken은 4-색 정리를 어떻게 증명하였는가? | [4] 이후 100년이 지난 1977년 Appel과 Harken[8]이 4-색 정리를 증명하였다. Appel과 Harken[8]은 수천 라인의 컴퓨터 프로그램을 작성하여 1,200 시간 동안 수행한 결과 4-색 정리를 증명하였다. 이 방법에 대해 많은 논쟁이 있었지만 결국은 수기식으로 증명할 방법이 없어 모든 수학자들이 이를 받아들였다. | |
수기식으로 증명할 수 있는 휴리스틱 알고리즘에 적용되는 개념은 무엇인가? | 본 논문은 모든 지도는 4-색 으로 칠할 수 있다는 4-색 정리를 수기식으로 증명할 수 있는 휴리스틱 알고리즘을 제안한다. 본 알고리즘은 그래프 정리에서 적용되고 있는 최대 독립 집합 (Maximum Independent Set, MIS)과 최소 정점 피복 (Minimum Vertex Cover, MVC) 개념을 적용한다. 먼저, 지도에서 주 (도)를 정점으로, 서로 인접한 주 (도)간에는 간선으로 연결하면 이를 그래프로 표현할 수 있다. |
Wikipedia, "Graph Coloring," http://en.wikipedia.org/wiki/Graph_Coloring, Wikimedia Foundation Inc., 2013.
Wikipedia, "Four Color Theorem," http://en.wikipedia.org/wiki/Four_Color_Theorem, Wikimedia Foundation Inc., 2008.
R. Thomas, "The Four Color Theorem," School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, http://www.math.gatech.edu/ -thomas/FC/ fourcolor.html, 2007.
M. Moore, "Four Color Theorem," Department of Mathematical Sciences, University of Arkansas, 2006.
I. Cahit, "The Four Color Theorem and Three Proofs," http://www.emu.edu.tr/-cahit/The Four Color Theorem - Three Proofs.html, 2005.
K. Brown, "The Four Color Theorem," http:// www.mathpages.com/home/kmath266/kmath26 6.htm, 2008.
E. W. Weisstein, "The Four-Color Theorem," Wolfram MathWorld, http://mathworld.wolfram.com /Four-ColorTheorem.html, 2013.
K. Appel and W. Haken, "Every Planar Map is Four-Colorable, II: Reducibility," Illinois Journal of Math., Vol. 21, pp. 491-567, 1977.
M. Gardner, "Mathmatical Games: On Tessellatings the Plane with Convex Polygons," Science American, Vol. 232, pp. 112-117, 1975.
S. Wagon, "Mathematica in Action, 2nd Ed.," New York: Springer-Verlag, pp. 535-536, 1999.
S. Wagon, "A Machine Resolution of a Four-Color Hoax," Proceedings of the 14th Canadian Conference on Computational Geometry, pp. 174-185, 2002.
A. B. Kempe, "On the Geographical Problem of the Four Colors," American Journal of Math., Vol. 2, pp. 193-200, 1879.
P. J. Heawood, "On the Four-Color Map Theorem," Quart. Journal Pure Math, Vol. 29, pp. 270-285, 1898.
N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas, "A New Proof of the Four-Colour Theorem," Electronic Research Announcements of the American Mathematical Society, Vol. 2, No. 1, 1996.
A. Dharwadker, "A New Proof of the Four Colour Theorem," http://www.geocities.com/dharwadker/, 2000.
A. Dharwadker, "The Vertex Coloring Algorithm,"http://www.geocities.com/dharwad ker/vertex_coloring/, 2006.
Wikipedia, "Degree (Graph Theory)," http://en. wikipedia.org/wiki/Degree_(graph-theory), Wikimedia Foundation Inc., 2013.
Wikipedia, "Hadwiger-Nelson Problem," http://en.wikipedia.org/wiki/Hadwiger_Nelson_Problem, Wikimedia Foundation Inc., 2013.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.