4-색 알고리즘

서지반출

기타언어초록

본 논문은 지금까지 NP-완전인 난제로 알려진 4-색 정리를 $O(n)$선형시간 복잡도로 수기식과 컴퓨터를 활용하여 증명하는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프 $G=(V_1,E_1)$의 정점 집합 V를 최대 독립집합 $ar{C_1}$와 최소 정점 피복 집합 $C_1$으로 정확히 양분하는 기법을 적용하여 $ar{C_1}$에 첫 번째 색을 배정하고, $C_1$ 집합의 정점들로 축소된 연결 그래프 $G=(V_2,E_2)$를 대상으로 $ar{C_2}$와 $C_2$로 양분하여 $ar{C_2}$에 두 번째 색을 지정하였다. $C_2$ 집합의 정점들로 축소된 연결 그래프 $G=(V_3,E_3)$를 대상으로 $ar{C_3}$와 $C_3$로 양분하여 $ar{C_3}$에 세 번째 색을 지정하였다. 마지막으로$C_3$를 $ar{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) $ar{C_1}$ and the Minimum Vertex Cover Set $C_1$. It then assigns the first color to $ar{C_1}$ and the second to $ar{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 $ar{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 $ar{C_4}$, the algorithm assigns the forth color to $ar{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.

키워드

최소 정점 피복 최대 독립 집합 최소 차수 채색수 Minimum Vertex Cover (MVC)Maximum Independent Set (MIS)Minimum Degree Chromatic Number

다운URL