본 논문은 지금까지 NP-완전인 난제로 알려진 4-색 정리를 $O(n)$선형시간 복잡도로 수기식과 컴퓨터를 활용하여 증명하는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프 $G=(V_1,E_1)$의 정점 집합 V를 최대 독립집합 $\bar{C_1}$와 최소 정점 피복 집합 $C_1$으로 정확히 양분하는 기법을 적용하여 $\bar{C_1}$에 첫 번째 색을 배정하고, $C_1$ 집합의 정점들로 축소된 연결 그래프$G=(V_2,E_2)$를 대상으로 $\bar{C_2}$와 $C_2$로 양분하여 $\bar{C_2}$에 두 번째 색을 지정하였다. $C_2$ 집합의 정점들로 축소된 연결 그래프 $G=(V_3,E_3)$를 대상으로 $\bar{C_3}$와 $C_3$로 양분하여 $\bar{C_3}$에 세 번째 색을 지정하였다. 마지막으로$C_3$를 $\bar{C_4}$로 하여 4번째 색을 배정하였다. 2개의 실제 지도 그래프와 2개의 평면 그래프를 대상으로 제안된 알고리즘을 적용한 결과 모든 그래프에서 채색수${\chi}(G)=4$를 찾는데 성공하였다. 결국, 제안된 "4-색 알고리즘"은 평면 그래프의 4-색을 결정하는 일반적인 알고리즘으로 적용할 수 있을 것이다.
본 논문은 지금까지 NP-완전인 난제로 알려진 4-색 정리를 $O(n)$선형시간 복잡도로 수기식과 컴퓨터를 활용하여 증명하는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프 $G=(V_1,E_1)$의 정점 집합 V를 최대 독립집합 $\bar{C_1}$와 최소 정점 피복 집합 $C_1$으로 정확히 양분하는 기법을 적용하여 $\bar{C_1}$에 첫 번째 색을 배정하고, $C_1$ 집합의 정점들로 축소된 연결 그래프 $G=(V_2,E_2)$를 대상으로 $\bar{C_2}$와 $C_2$로 양분하여 $\bar{C_2}$에 두 번째 색을 지정하였다. $C_2$ 집합의 정점들로 축소된 연결 그래프 $G=(V_3,E_3)$를 대상으로 $\bar{C_3}$와 $C_3$로 양분하여 $\bar{C_3}$에 세 번째 색을 지정하였다. 마지막으로$C_3$를 $\bar{C_4}$로 하여 4번째 색을 배정하였다. 2개의 실제 지도 그래프와 2개의 평면 그래프를 대상으로 제안된 알고리즘을 적용한 결과 모든 그래프에서 채색수 ${\chi}(G)=4$를 찾는데 성공하였다. 결국, 제안된 "4-색 알고리즘"은 평면 그래프의 4-색을 결정하는 일반적인 알고리즘으로 적용할 수 있을 것이다.
This paper proposes an algorithm that proves an NP-complete 4-color theorem by employing a linear time complexity where $O(n)$. The proposed algorithm accurately halves the vertex set V of the graph $G=(V_1,E_1)$ into the Maximum Independent Set (MIS) $\bar{C_1}$ and...
This paper proposes an algorithm that proves an NP-complete 4-color theorem by employing a linear time complexity where $O(n)$. The proposed algorithm accurately halves the vertex set V of the graph $G=(V_1,E_1)$ into the Maximum Independent Set (MIS) $\bar{C_1}$ and the Minimum Vertex Cover Set $C_1$. It then assigns the first color to $\bar{C_1}$ and the second to $\bar{C_2}$, which, along with $C_2$, is halved from the connected graph $G=(V_2,E_2)$, a reduced set of the remaining vertices. Subsequently, the third color is assigned to $\bar{C_3}$, which, along with $C_3$, is halved from the connected graph $G=(V_3,E_3)$, a further reduced set of the remaining vertices. Lastly, denoting $C_3$ as $\bar{C_4}$, the algorithm assigns the forth color to $\bar{C_4}$. The algorithm has successfully obtained the chromatic number ${\chi}(G)=4$ with 100% probability, when applied to two actual map and two planar graphs. The proposed "four color algorithm", therefore, could be employed as a general algorithm to determine four-color for planar graphs.
This paper proposes an algorithm that proves an NP-complete 4-color theorem by employing a linear time complexity where $O(n)$. The proposed algorithm accurately halves the vertex set V of the graph $G=(V_1,E_1)$ into the Maximum Independent Set (MIS) $\bar{C_1}$ and the Minimum Vertex Cover Set $C_1$. It then assigns the first color to $\bar{C_1}$ and the second to $\bar{C_2}$, which, along with $C_2$, is halved from the connected graph $G=(V_2,E_2)$, a reduced set of the remaining vertices. Subsequently, the third color is assigned to $\bar{C_3}$, which, along with $C_3$, is halved from the connected graph $G=(V_3,E_3)$, a further reduced set of the remaining vertices. Lastly, denoting $C_3$ as $\bar{C_4}$, the algorithm assigns the forth color to $\bar{C_4}$. The algorithm has successfully obtained the chromatic number ${\chi}(G)=4$ with 100% probability, when applied to two actual map and two planar graphs. The proposed "four color algorithm", therefore, could be employed as a general algorithm to determine four-color for planar graphs.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문은 150년 이상 증명되지 못한 4-색 정리를 수기식으로 증명할 수 있는 휴리스틱 알고리즘을 제안하였다. 제안된 알고리즘은 수행 복잡도 O(n)으로 컴퓨터를 활용하거나 수기식으로도 쉽게 증명할 수 있다.
본 논문은 모든 지도는 4-색 으로 칠할 수 있다는 4-색 정리를 수기식으로 증명할 수 있는 휴리스틱 알고리즘을 제안한다. 본 알고리즘은 그래프 정리에서 적용되고 있는 최대 독립 집합 (Maximum Independent Set, MIS)과 최소 정점 피복 (Minimum Vertex Cover, MVC) 개념을 적용한다.
4-색 정리에 대한 증명을 종결하기 위해서는 수기식으로 증명할 수 있는 알고리즘 제안이 필수적이라 할 수 있다. 본 연구의 목적은 4-색 정리에 대해 수기식으로 증명할 수 있는 알고리즘을 제시함으로서 4-색 정리에 대한 논쟁을 종식시키고자 한다.
제안 방법
그래프는 각 정점의 차수 deg(v)는 3,4,5,6, 10, 14로 이상점 (Outliners)이 2개 존재한다. 따라서 이 경우 제안된 알고리즘을 약간 변형시켜 적용하였다. 즉, deg(1) =14, deg(3) = 10으로 정점 ①과 ③을 제외시킨 그래프를 대상으로 첫 번째와 두 번째 색을 배정한다.
제안된 알고리즘은 수행 복잡도 O(n)으로 컴퓨터를 활용하거나 수기식으로도 쉽게 증명할 수 있다. 제안된 알고리즘은 그래프 이론에서 주어진 그래프 G = (V,E)의 정점 집합 V 를 MIS # 와 MVC C 집합으로 정확히 양분하는 방법을 적용하여 채색수 X(G) = 4를 구하였다. 제안된 알고리즘을 2개의 실제 지도 그래프와 2개의 평면 그래프에 적용한 결과 X(G) = 4를 얻을 수 있었다.
평면 그래프의 채색수 X(G) = 4를 찾기 위해 본 장에서는 정점 집합 V 를 단계적으로 4개의 MIS # , k = 1,2,3,4로 정확히 분할하는 방법을 제안한다. 이 알고리즘은 2장에서 제시한 “MIS 집합을 얻는 방법”을 적용한다.
이론/모형
본 논문은 모든 지도는 4-색 으로 칠할 수 있다는 4-색 정리를 수기식으로 증명할 수 있는 휴리스틱 알고리즘을 제안한다. 본 알고리즘은 그래프 정리에서 적용되고 있는 최대 독립 집합 (Maximum Independent Set, MIS)과 최소 정점 피복 (Minimum Vertex Cover, MVC) 개념을 적용한다. 먼저, 지도에서 주 (도)를 정점으로, 서로 인접한 주 (도)간에는 간선으로 연결하면 이를 그래프로 표현할 수 있다.
성능/효과
C3가 #로 되어 4번째 색이 지정된다. 결국, 제안 알고리즘은 O(n)회의 수행 복잡도로 X(G) = 4를 정확히 얻을 수 있다.
본 논문에서 제안된 4-색 알고리즘은 지금까지 NP-완전(non-deterministic polynomial-complete)인 난제로 여겨졌던 채색수 문제를 선형 시간으로 푸는 다항시간 (polynomial) 알고리즘이 존재함을 보였다. 따라서, 4-색 알고리즘은 NP문제가 아닌 P-문제임을 증명하였다.
제안된 알고리즘은 4개 그래프 데이터 모두에서 4-색 칼라를 배정하는데 100% 성공하였다. 비록 G2의 Δ(G) = 9 (⑦), G3의 Δ(G) = 8 (⑰과 29), G5의 Δ(G) = 14 (①)로 최대 인접 정점이 8,9 또는 14개가 존재하더라도 “모든 평면 그래프는 4-색으로 가능하다.
본 논문은 150년 이상 증명되지 못한 4-색 정리를 수기식으로 증명할 수 있는 휴리스틱 알고리즘을 제안하였다. 제안된 알고리즘은 수행 복잡도 O(n)으로 컴퓨터를 활용하거나 수기식으로도 쉽게 증명할 수 있다. 제안된 알고리즘은 그래프 이론에서 주어진 그래프 G = (V,E)의 정점 집합 V 를 MIS # 와 MVC C 집합으로 정확히 양분하는 방법을 적용하여 채색수 X(G) = 4를 구하였다.
제안된 알고리즘은 그래프 이론에서 주어진 그래프 G = (V,E)의 정점 집합 V 를 MIS # 와 MVC C 집합으로 정확히 양분하는 방법을 적용하여 채색수 X(G) = 4를 구하였다. 제안된 알고리즘을 2개의 실제 지도 그래프와 2개의 평면 그래프에 적용한 결과 X(G) = 4를 얻을 수 있었다.
후속연구
본 알고리즘은 채색수 문제를 풀 수 있는 일반적인 휴리스틱 알고리즘으로 적용할 수 있을 것이다.
질의응답
핵심어
질문
논문에서 추출한 답변
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) 개념을 적용한다. 먼저, 지도에서 주 (도)를 정점으로, 서로 인접한 주 (도)간에는 간선으로 연결하면 이를 그래프로 표현할 수 있다.
참고문헌 (18)
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.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.