MMSS 9일차 (7/31 Mon)

• Graph coloring: Coloring of vertices with minimum colors where any adjacent vertices has a different color
• Chromatic number: Fewest colors needed to color a graph
• Independence number: Order of the largest independent subgraph of a graph
• Clique number: Order of the largest ‘clique’(complete subgraph)
• Clique partition number: Fewest number of partitions in a graph such that every subgraph is complete(aka clique)

• Domination number: Smallest set of vertices such that every vertices of the graph is in the set or a neighbor of a vertex in the set

• 그래프 채색과 그래프 내 (최대) 클리크 등, 각 그래프가 가지는 성질 5가지에 대해 배우고 여러 가지 그래프에 대한 이 5가지 성질변수를 찾아보았다.
  • 그래프의 채색과 그래프의 최대 클리크 개념은 작년 기초R&E 때 알고리즘의 최적성 증명에서도 사용했고 실제 알고리즘에서도 그래프를 채색하고 최대 클리크를 찾는 과정을 그현했어서, 몇 가지 변수는 이미 잘 알고 있었다. 그러나 domination number 등 따로 알고 있지 않았던 변수도 있어서 나름 흥미롭게 배울 수 있었다.
  • 아무래도 작년에 연구한 것은 구간 그래프에 한정한 내용이라서, 각 변수와 그 관계에 대해 조금 더 일반적인 내용에대해 배울 수 있었다.
• 그래프를 임의의 수의 색으로 채색하는 경우의 수를 사용할 색의 수에 따른 (그래프에 대응될 수 있는) 다항식으로 표현할 수 있다는 것을 배웠다. 이때 이 식을 chromatic polynomial이라고 한다. 이를 배우면서 그래프의 채색 수(chromatic number)에 대한 좀 더 자세한 성질들을 배울 수 있었다.

지난주 목요일 수업 때 배운 것이 ‘나중에 문제 해결 프로그래밍에서 가장 많이 응용할 수 있을 것 같은 유용한 부분’이었다면, 이번 수업 내용은 작년에 내가 이미 (그래프 이론 내 다른 분야들보다도 조금 더 깊게) 다루었던 쪽이었다. 내가 알고 있는 것에 비해서는 조금 더 일반적인 성질에 대해서 배웠어서, 그럼에도 꽤나 흥미롭게 수업을 들을 수 있었다.