꼭짓점끼리는 다른 색이 되도록 색을 칠할 때 필요한 색의 수의 최솟값을 그 그래프의 ‘채색수’라고 부릅니다. 참에 더 가까워진 하트비거의 추측! 엄상일 교수는 KAIST 수학과를 졸업하고, 미국 프린스턴대학교에서 박사 학위를 받았습니다. 현재 기초과학연구원과 KAIST에서 연구와 강의를 ...
만에 박사 학위를 받고, 1959년에 미국 프린스턴대학교 수학과 교수가 됩니다. 한편 평면 채색수는 항상 3 이상입니다. 어떻게 알 수 있을까요? 한 변의 길이가 1인 정삼각형을 그려봅시다. 그러면 정삼각형의 세 꼭짓점은 서로 다른 색이 돼야 하므로 3색 이상이 필요합니다. 4 이상일 수는 없을까요? ...
영역을 꼭짓점, 국경을 맞대고 있는 이웃한 나라는 선으로 연결해 나타낸 평면그래프의 채색수가 항상 4 이하라는 것을 증명하라는 문제로, 1852년에 제기됐습니다. 무려 100년 동안 풀리지 않다가 지난 1976년 케네스 아펠과 볼프강 하켄이 컴퓨터를 이용해 증명했습니다.실생활 문제 해결하는 그래프 ...