그래프 색칠 (Graph Coloring) 알고리즘 - 램지 수 문제 예제

이런! 학회 뱅큇에서 일행을 놓쳐 버렸다! 사람이 너무 많아 찾기를 포기하고 그냥 아무 테이블에 앉아 버리는데.... 이때 테이블에 여섯 명이 앉는 경우 서로 아는 관계인 세 명의 그룹이나 서로 모르는 관계인 세 명의 그룹이 반드시 존재함을 보이시오. (!!)

 

아니, 이게 웬 유학 준비하다 잘 안 풀려서 급하게 준비했던 기업 인적성에서나 보던 문제입니까. 문제집에서 이런 문제를 보면 왜 풀어야 하나 하는 의문을 한 번쯤 가져보신 적이 있을 겁니다. 이런 문제를 수학적으로 모델링할 때는 여러 행위자 (위 예시에서는 사람)가 있고 그것들 간의 관계를 표현할 수 있는 그래프가 사용됩니다. 제가 수학을 전공하지는 않아서 그래프 이론 전반에 대해서는 잘 모르지만, 통신 분야에서는 그래프 안에서 발생하는 연결에 초점을 맞추고, 그래프 이론을 이용하여 그 연결과 관련된 특성을 분석합니다. 여러 유저가 참여하는 네트워크를 분석할 때도 쓰이고, 여러 메모리에 정보를 나누어 저장하는 분산 저장 (Distributed Storage), 여러 컴퓨팅 유닛으로 연산을 나누어하는 분산 컴퓨팅 (Distributed Computing) 등을 분석할 때도 쓰입니다.

 

이번 포스팅에서는 그래프 색칠 알고리즘 관련 문제 중 하나를 풀어볼 텐데요. 위와 같은 상황에 대응해 생각해볼 수 있다는 점이 재미있어 가져와보았습니다. 우선 문제를 정의하고 푼 후 그 문제가 어떻게 뱅큇에서 어쩌고 하는 상황에 대응되는지는 풀이 뒤에 설명하도록 하겠습니다. 

 

문제: 아래와 같이 꼭짓점이 6개이고 모든 꼭짓점이 서로 연결되어 있는 완전 그래프를 가정하자. 임의의 두 꼭짓점을 잇는 모든 선을 빨간색 혹은 파란색으로 색칠할 때, 빨강 삼각형 또는 파랑 삼각형이 항상 존재함을 증명하시오.

그림1. 꼭짓점이 6개이고 임의의 두 꼭짓점이 선으로 연결되어 있는 완전 그래프. (출처: https://en.wikibooks.org/wiki/Discrete_Mathematics/Graph_theory)

문제 증명

그림 1. 에서 한 꼭짓점의 입장에서 문제를 바라봅시다. 나머지 다섯 꼭짓점인 {2, 3, 4, 5, 6}을 꼭짓점 1과 연결된 선의 색이 빨강인 집합과 파랑인 집합으로 나누어봅시다. 그렇다면 비둘기집의 원리에 의해 두 집합 중 하나는 원소가 3개 이상이 됩니다. 일반성을 잃지 않고, 원소가 3개 이상인 집합을 선이 빨간색인 집합이라고 해봅시다. 이제 이 집합에 속한 임의의 두 꼭짓점 사이의 선을 생각해봅시다. 만약 그중 빨간색 선으로 연결된 두 꼭짓점이 있다면 1과 그 두 꼭짓점은 빨강 삼각형을 이루게 됩니다. 만약 그중 빨간색 에지로 연결된 두 꼭짓점이 하나도 존재하지 않는다면, 그 집합 속 모든 꼭짓점이 모두 파란색 에지로 연결되어야 합니다. 집합의 원소가 3개 이상이니 그 집합에 속한 모든 꼭짓점이 파란색 선으로 서로 연결되어 있다면 파랑 삼각형이 존재하겠지요? 그래서 모든 경우에 빨강 삼각형 또는 파랑 삼각형이 존재하게 됩니다. 참 쉽죠?

 

그러면 좀 더 일반적으로 그래프가 어떻게 정의되는지, 그리고 주어진 문제를 위해 어떤 그래프와 어떤 그래프 색칠 문제를 가정하는 것이 좋을지 위 문제를 예시로 알아보도록 하겠습니다. 

 

그래프의 구성과 종류

그래프는 기본적으로 꼭짓점(노드, Node 혹은 Vertex)과 그 점 사이를 잇는 선(에지, Edge)으로 이루어져 있습니다. 이제부터는 편의 상 노드와 에지로 부르겠습니다. 노드에 종류가 있는지, 에지에 방향이 있는지, 아니면 에지마다 다른 값을 매길 수 있는지, 두 노드 사이에 에지가 여럿 존재할 수 있는지, 에지가 출발한 노드로 도착하는 루프가 존재할 수 있는지 등에 따라 그래프의 종류도 달라집니다. 풀고자 하는 문제에 맞는 그래프를 정의해서 사용하는 것이 좋겠지요? 아래 그림은 노드에 종류가 없는 몇 가지 그래프를 에지의 특성에 따라 분류한 것인데요. 오늘의 문제에서는 사람들을 각 노드에 대응시키고, 두 사람이 서로 아는지 모르는지만 에지로 표현하면 되기 때문에 두 노드 사이에 에지가 하나만 존재할 수 있고, 루프가 없는 단순 그래프(Simple Graph)를 가정하겠습니다. 단순 그래프 중에서도 모든 노드가 서로 연결되어있는 그래프를 완전 그래프(Complete Graph)라고 부릅니다. 

 

그래프의 종류 (출처: https://mathworld.wolfram.com/SimpleGraph.html)

그래프 색칠 문제 (Graph Coloring)

그래프 색칠 문제는 노드를 어떻게 색칠할지 정하는 문제일 수도 있고, 에지를 어떻게 색칠할지 정하는 문제일 수도 있습니다. 그리고 칠할 수 있는 색의 개수를 임의로 정할 수 있고요. 오늘의 문제에서는 두 사람이 아는지 모르는지 관계를 구별해야 하기 때문에 에지를 색칠할 것이고, 두 가지 색으로 색칠하는 문제를 정의합니다. 사람이 여섯 명이니 그림 1. 과 같이 노드가 6개인 완전 그래프를 가정합니다. 여섯 명의 사람을 1에서 6까지 숫자가 적힌 노드에 각각 대응시키고, 두 사람이 서로 알 경우에는 두 사람을 잇는 에지를 빨간색으로 칠하고, 모를 경우에는 파란색으로 색칠해봅시다. 그러면 서로 아는 관계인 세 명의 그룹은 빨간 삼각형을 이루게 되고, 서로 모르는 관계인 세 명의 그룹은 파란 삼각형을 이루게 되겠지요? 그런 그래프를 두 가지 색으로 색칠할 때, 어떤 방식으로 색칠하더라도 같은 색으로 이루어진 삼각형이 존재함을 보이면 문제를 증명할 수 있게 됩니다. 이렇게 같은 색으로 이루어진 삼각형을 monochromatic triangle이라고 부르고, 그래프에 존재하는 모든 에지를 monochromatic triangle이 생기지 않도록 색칠하는 문제를 monochromatic triangle problem이라고 합니다. 위의 문제가 당연하게 느껴지시나요? 신기하게도 사람이 6명보다 적거나 많은 경우에는 위와 같은 명제가 성립하지 않게 됩니다. 다시 말해 노드의 개수가 6이 아닌 완전 그래프의 에지를 두 색으로 칠하는 경우, 같은 색으로 이루어진 삼각형이 존재할 수도 있고 존재하지 않을 수도 있습니다. 이 문제를 일반적인 경우에 대해 답한 것이 램지의 정리와 램지 수입니다. 램지의 정리에 따르면, k개의 색으로 n개의 노드가 있는 완전 그래프를 칠할 경우 같은 색으로 이루어진 삼각형이 존재하지 않는 n이 항상 존재한다고 합니다. 이번 포스팅에서 풀어본 문제는 k=2일 때 n=6 임을 증명한 셈이지요. 더 일반적으로는 같은 색으로 이루어진 삼각형뿐만 아니라 같은 색으로 이루어진 임의의 노드 개수를 갖는 완전 그래프(클릭)에 대해서도 정의가 되어있네요! 

 

같은 테이블에 서로 아는 사람이 너무 많으면 그 사람들끼리만 어울리게 될 수도 있고, 서로 모르는 사람만 너무 많다면 대화를 시작하기 어려울 수도 있겠지요? (너드가 많은 분야의 학회라면 그럴 수 있습니다..!) 서로 아는 사람의 수와 서로 모르는 사람의 수가 적절해야 좋은 분위기가 될 텐데요, 이 문제를 거꾸로 파티에서 서로 아는 사람이 k명, 서로 모르는 사람이 t명이려면 총 몇 명의 인원이 파티에 참가해야 하는지 생각해볼 수 있습니다. 분위기 좋은 파티를 만들기 위해 음악이나 대화 주제를 기획하는 것이 아니라 서로 아는 사람, 모르는 사람 수를 세고 초대할 인원을 계산해보는 것이 정말 너무나 수학자스러운 접근이네요..! 이런 문제에 대해 대중적으로 설명한 재미있는 기사를 찾았습니다. 그 기사를 인용하며 이번 포스팅을 마칩니다.

 

조가현, "[주말 N수학] 완벽한 파티 만드는 '램지 수'", 동아사이언스, 2019.01.20, dongascience.donga.com/news/view/26166

[주말N수학]완벽한 파티 만드는 '램지 수'

 

다음 포스팅으로는 네트워크 분석에 많이 쓰이는 min-cut과 cut-set bound에 대해 다루어보려 합니다.