MMSS 4일차 (7/26 Wed)

• Hamiltonian Path : Path where all vertex is passed exactly once
• Bipartite Graph : A graph is bipartite if the vertices are partitioned into 2 independent sets

• Complete bipartite graph : Bipartite graph with all possible edges

• Hamiltonian : 해밀토니언 그래프를 정의하고 해밀토니언 그래프에 대한 필요조건과 충분조건 여러 가지를 배웠다. Eulerian과 다르게 Hamiltonian 그래프는 적당한 필요충분 조건이 발견되어 있지 않다고 한다.
  • Hamiltonian 그래프의 필요조건은 거의 Toughness가 유일하게 사용되고 더 많은 연구가 진행되지 않고 있다고 한다.
    • 그래프 G에서 임의의 Subgraph S에 대해 G-S의 Component 개수보다 S의 크기가 클 때 그래프 G를 Tough하다고 한다.
  • Hamiltonian 그래프의 충분조건은 여러 가지가 있고 충분조건에 대한 연구도 활발하게 진행되고 있다고 한다.
    • 예를 들어, order > 2 and all non-adjacent distinct pairs of vertices x & y, deg(x)+deg(y)>=n 인 임의의 그래프 G는 Hamiltonian이다. 이를 Ore라 한다.
    • order 3이상의 각 vertex에 대해 deg(v)>=n/2인 그래프, degree가 n/3 이상인 regular 그래프 등 다양한 조건이 밝혀져 있다.
• 예전 MMSS 수업 중에 나온 Harris graph라는 그래프를 정의하고 이가 존재하는지 찾아보았다. Harris Graph란 Non-tough Eulerian graph 중 Hamiltonian Path 사이클이 없는 그래프를 이야기하는데, 수업 중에 이러한 그래프를 어떤 조에서도 찾지 못하였다. 다만 여러 가지 Harris graph 후보군에 대한 반례를 찾아보긴 하였다.

조가 바뀌어서 새로운 친구들과 문제를 풀게 되었는데, 그 중 juwonhyme와 같은 조가 되었다. 여전히 조의 다른 친구들과 각자 가지고 있는 ‘엄밀하지는 않지만 핵심 아이디어가 될 수 있는 풀이 방법 같은 것’이 떠올랐을 때 이를 공유하는 것이 좀 어렵다고 느껴졌다. Eulerian이나 Hamiltonian 경로/회로에 대해서 원래도 들어보기는 했는데, 수업을 통해서 각각의 무엇을 나타내는지와 특히 각각이 꽤나 독특한 성질을 가지고 있다는 것을 배웠다. 특히 오일러 경로에 대해서는 (한붓그리기와 같으므로) 간단한 필요충분 조건이 알려져 있는 것과 달리 해밀턴 회로는 여러 가지의 충분조건이 있으면서도 아직 P-complete하게 해밀턴 회로를 판정할 수 없다는 것이 기억에 남았다. 친구들과 함께 증명을 해나가는 수업 진행이 매우 재미있는 것 같다. 칠판에 나가서 서너 명이서 계속 이야기를 해나가며 문제를 풀어나가는데, 친구들별로 알고 있는 것도 다르고 영어 실력도 달라서 조금 어렵기는 하지만 그래도 서로 도우면서 문제를 해결해나가는 그 느낌이 조금 더 강한 것 같다는 생각이 들었다.