MMSS 11일차 (8/2 Wed)

• 그래프를 응용해서 그래프 위에서 할 수 있는 게임 이론적인 몇몇 아이디어에 대해 배웠다. 조합론이나 게임 이론, 문제 해결 프로그래밍 쪽에는 어느 정도 잘 알려져 있는 Nim 게임과 ‘Sprague-Grundy Theorem’ 등에 대해 배우고 cutthroat 게임의 각 상태를 Grundy 수로 표현하여 어떤 플레이어가 게임에서 이기는지를 확인하는 법에 대해 배웠다.
  • 스프라그-그런디 정리는 정보과학에서 많이 사용하는 Exclusive or 연산을 사용하는 등 문제 해결 프로그래밍 쪽에서는 많이 익숙한 알고리즘이다. 다만 그래프와는 조금 거리가 있는 게임 이론 중심의 문제라서 그래프를 배우면서 다시 공부할 줄은 몰랐다.
  • 사실 아직도 왜 굳이 스프라그-그런디에 대한 이야기를 그래프 수업 중에 끼운 것인지는 잘 모르겠다. 지난주 금요일에 시카고에 갔을 때 트리/그래프 위에서의 게임 이론에 대해 짧게 이야기를 했다는 것 같다.
• 평면 그래프에 대해 이런저런 성질을 배웠다. 평면 그래프란 그래프의 간선이 교차하지 않도록 간선을 적절히 그리는 것을 의미한다.
  • 오일러 지표(이를 우리나라에서는 임의의 입체도형의 점, 선, 면에 대해서 성립하는 성질으로 배웠다. 평면 그래프는 그 정점을 적절히 배치해서 각 정점과 간선으로 이루어진 그래프가 입체도형을 나타낸다는 사실을 증명할 수 있기 때문에 그래프와 입체도형에서의 성질은 곧 동치이다)에 대해 배웠다.
  • 모든 non-planar한 그래프는 그 subgraph로 K_5 혹은 K_{3,3} 그래프를 가진다는 사실을 배웠다. 이 사실을 증명하지는 못했지만 K_5 그래프와 K_{3,3} 그래프가 각각 nonplanar하다는 사실은 증명하였다.
  • 기타 평면 그래프가 가지는 여러 가지 성질에 대해 배웠다.
• Peterson graph를 통해 유도해낼 수 있는 그래프인 Brualdi graph에 대해 배우고, 이 그래프가 가지는 이런저런 성질에 대해 배웠다.
• 그래프 분할, 스프라그-그런디 등 다양한 주제를 가지고 문제를 풀어보았다.

확실히 수업이 막바지에 다가가다 보니 조금 더 그래프에 대한 지엽적인? 것들을 공부하는 것 같다. 또한, 처음 수업 때에 비해서 풀이를 쓸 때 이에 대해 논리적인 오류를 범하는 부분이 줄어들어서, 그래프 이론만이 아닌 수학 전반적 - 특히 명제나 논리적 증명 - 인 것들에 대한 노하우가 조금씩 생기는 것 같다. 그래프외는 약간 거리가 떨어져 있지만 게임 이론 쪽도 어느 정도 발을 담구어봤는데, 그래프 위에서의 게임에 대해서 배우는 것은 약간 색다른 아이디어였던 것 같다. 스프라그-그런디를 통해 표현할 수 있는(그리고 그에 따라 각 게임별 상태(position)의 순서) 것이 매우 다양하고 또 일정해서인지, 트리에서도 그런디 수를 통한 수열을 계산하면 같은 형태로 상태가 표현됨을 볼 수 있었던 게 기억에 남았다. 수업이 끝자락에 접어드니 좀 아쉬운 것 같다. 생각했던 것보다 더 높은 수준의 아이디어들을 폭넓게 다루고, 그중에서도 아름답다거나 신기한 성질들이 믾이 있어서 재미있게 수업을 들을 수 있었던 것 같다.