|
이번 글은 “듬성한 그래프” 라는 제목으로 준비한 연재의 마지막 글입니다. 첫 번째 연재에서는 나무-폭이 작은 그래프 모임들에 대해 알아보았고, 두 번째 연재에서는 특정한 그래프를 그래프 마이너 연산으로 가지지 않는 그래프 모임들에 대해 알아보았습니다. 특정한 그래프를 그래프 마이너 연산으로 가지지 않는 그래프 모임들은 평면 그래프 모임이나 특정한 종수의 곡면에 선을 교차하지 않고 그릴 수 있는 그래프들의 모임들을 포함하였습니다. 그 외에 흥미로운 예제를 찾자면, 그래프를 유클리드 3차원 공간에 매립할 때 어떤 두 개의 원 부분그래프도 고리를 만들지 않게 매립할 수 있는 그래프들을 생각해볼 수 있습니다. 이러한 그래프들은 고리 없이 매립가능한 그래프라 불리며 이러한 그래프들의 모임이 그래프 마이너 연산에 닫혀있다는 것이 알려져 있습니다.
|
![듬성한 그래프 [3] : 얕은 마이너로 표현되는 그래프 모임들](https://horizon.kias.re.kr/wp-content/uploads/2022/06/메인이미지_박지연_듬성한그래프-660x371.jpg)