MMSS 5일차 (7/27 Thu)

• Chordal graph: A graph where every cycle has a chord
• Interval graph: A graph where vertices are intervals and two vertices are adjacent if and only if the 2 intervals intersect
• Graph Decomposition: Division of a graph into multiple subgraphs with the same vertex set and disjoint sets of vertices

• Tree: connected acyclic graph

• 이분 그래프, 현 그래프, 구간 그래프 등 여러 가지 특수한 형태의 그래프들에 대해 배웠다. 특히 구간 그래프의 경우 작년에 기초R&E로 연구한 적이 있어 작년에 고민하고 증명하려고 했던 것들을 수업에서 다시 볼 수 있었다.
  • 특히, 구간 그래프가 현 그래프이기 떄문에 O(nlogn) 다항 시간에 채색할 수 있다는 사실이 작년 연구에 필요한 핵심 정리 중 하나였는데, 수업에서 현 그래프와 구간 그래프에 대해 배우고 나서 바로 이 증명을 써먹을 수 있었다.
  • 구간 그래프의 선형적 구조 때문에 일반적 그래프에서 다룰 수 없지만 구간 그래프에서는 사용 가능한 다양한 일고리즘들이 있었는데, 이에 대해 다시 생각해볼 수 있었다.
• 트리의 경우 그래프 중에서도 사이클이 없어서 빠르게 다루가 쉬운 좋은 컴퓨터 자료구조이기도 한데, 그렇기에 트리에 대해 배운 내용 중에서도 알고 있던 내용이 많았다. 그럼에도 코딩을 하면서는 생각해보지 않았던 이런저런 성질이나 정리를 확인하고 증명하는 것이 신기했다.
• n-cube graph, forest, unipancyclic 등 homework 문제를 풀어보면서도 다른 이런저런 그래프에 대해 알아볼 수 있었다. 이외에도 트리 조건의 필요충분조건, Tree decomposition 등 여러 가지 흥미로은 문제들을 접해보고 친구들과 풀어보았다.

아무래도 그래프 이론 수업을 고른 이유가 그래프 이론과 정보과학 내용 중 많은 것이 엮이기 때문인데, 특히 오늘 배운 내용이 문제 해결 프로그래밍과는 가장 큰 연관이 있었던 것 같다. 주제가 그래프 이론이 아닌 구간 활용 문제 중에서도 이들 구간을 구간 그래프로 옮겨서 그 안에서 최대 클리크를 찾는다던가 구간을 채색한다던가 하는 구간 그래프를 응용하는 여러 문제가 있고, 이분 그래프나 트리의 경우 주제가 ‘트리’인 문제, ‘이분 그래프’(혹은 이분 매칭 등)인 문제들을 따로 모아둔 태그가 있을 정도로 매우 많이 쓰이며(그래프 이롱 아이디어를 완전히 배제하고 자료구조 그 자체로만 사용하기도 한다) 내 작년 연구도 구간 그래프로 옮겨 알고리즘의 최적성을 증명하는 과정을 거쳤었다. 이처럼 그래프 이론 중에서도 굉장히 관심 있어하던 부분의 여러 가지 문제들을 오늘 다루어서, 매우 흥미롭게 수업을 들을 수 있었다. 실제로 오늘 배운 내용들은 아미 첫 1주간 들었던 내용 중에서는 가장 나중에 잘 활용할 수 있을 내용들인 것 같다.