난 연재에서는 듬성한 그래프 모임을 다루는 데 중요한 나무-폭에 대해 알아보았습니다. 나무-폭이 작은 그래프 모임은 기본적인 듬성한 그래프 모임 중 하나로 최대 독립집합 등의 알고리즘 문제들을 다항식 시간에 해결할 수 있음을 보았습니다. 반면, 나무-폭이 큰 그래프에서는 반드시 큰 격자 그래프를 마이너 포함관계로 찾을 수 있다는 격자 그래프 마이너 정리에 대해서도 알아보았습니다. 나무-폭과 관련된 여러 이론이 형성된 배경에는 바그너의 추측이 있습니다. 1970년에 바그너는 그래프 마이너 포함관계와 관련된 흥미로운 추측을 하였습니다.
|