The graph grabbing game on some special graphs = 특별한 구조를 지닌 그래프 위에서의 그래빙 게임

국문 초록 (Abstract)

그래프 그래빙 게임이란 주어진 연결된 가중그래프 위에서 앨리스와 밥이라는 두 명의 참가자가 꼭짓점을 하나씩 선택하여 가중치만큼의 점수를 획득한 후 그 꼭짓점을 제거하는 방식의 게임을 의미한다. 단 게임 중 그래프는 항상 연결된 상태여야 하며, 따라서 앨리스와 밥은 어떤 스테이지에서도 단절 꼭짓점을 선택할 수 없다. 앨리스가 먼저 게임을 시작하며 그래프의 모든 꼭짓점이 제거되었을 때 게임이 종료된다. 종료 후 앨리스와 밥이 획득한 총점을 비교하여, 더 높은 사람이 승리한다. 만약 동점일 경우에는 앨리스가 승리하는 것으로 규정한다.
본 연구논문에서는 특별한 가중그래프를 지정한 후, 그 위에서 그래프 그래빙 게임을 진행하였을 때 앨리스에게 필승전략이 존재하는지에 대한 여부를 조사한다.