d라이브러리

올해 여름은 날도 덥고, 코로나19 때문에 여행도 못 가서 선풍기 바람 쐬며 시원하게 랜선 여행 중이었는데요, 보기만 해도 시원한 네덜란드 풍차가 제 눈을 사로잡았습니다.

※ 편집자주

LOL, 오버워치, 배그부터 다양한 인디게임까지 섭렵한 게임 인생 6년차 퓨처킴. 하지만 마인크래프트(이하 마크)는 처음이다. 회사에서 게임하는 게 조금 눈치 보이지만 마크 초고수가 되는 그날까지, 나는 달린다!

풍차는 7세기부터 사용한 친환경 발전소예요. 과거엔 날개가 돌아가는 힘을 이용해 곡식을 빻거나 물을 길어 올렸고, 지금은 전기에너지를 만드는 유익한 구조물이죠. 그런데 이 풍차를 ‘그래프’로 나타내도 유용하다는 것을 아나요?

우리 반 인싸의 특징을 가진 풍차 그래프

그래프는 어떤 대상들 사이의 연결성을 표현하는 수학적 방법이에요. 학급의 학생들을 점으로 표현하고, 서로 친한 사람들 사이에 선을 그리면 친구 관계를 나타내는 그래프를 얻을 수 있죠. 풍차 그래프는 오른쪽 그림처럼 2개 이상의 삼각형 그래프가 한 점을 중심으로 붙어있는 그래프를 말해요. 이 그래프의 특징 중 하나는 중심에 있는 점이 다른 모든 점과 연결돼 있다는 거예요. 마치 학급에 하나씩 있는 인싸 친구 같죠?

그래프로 나타내는 우리 관계

이렇게 그래프는 사람들 사이의 관계를 나타내는 데 유용해요. 헝가리 수학자 에르되시 팔과 알프레드 레니, 베러 쇼시는 1966년 풍차 그래프에 관한 정리를 발표했어요. 바로 ‘우정 정리’예요. 만약 학급 내에 어떤 두 학생이 공통으로 알고 있는 친구가 정확하게 한 명뿐이라면 학급의 친구 관계는 무조건 풍차 그래프로 나타난다는 거죠. 그런데 이 정리는 친구 관계보다는 비밀이 새어나가면 안 되는 관계에 적용하면 좋아요. 
예를 들면 두 명의 스파이는 함께 아는 친구가  너무 많으면 자신의 정체를 들킬 수 있어요. 하지만 둘 다 동시에 아는 친구가 하나도 없으면 필요한 정보를 전해주는 것이 불가능하죠. 함께 아는 친구가 단 한 명이면 좋겠죠? 이럴 때 풍차 그래프를 이용해 스파이를 투입할 수 있어요. 김재훈 KAIST 수리과학과 교수는 풍차 그래프가 유용하게 쓰이는 예를 설명하면서, 이름으로 ‘우정 정리’보다는 ‘스파이 정리’가 더 적합할 것 같다고 말씀해주셨답니다(웃음).

완벽한 파티 구성원 수 정하는 그래프

인간 관계를 그래프로 나타낸 또 다른 정리로는 램지 수를 구하는 ‘파티 문제’가 있어요. 램지 수는 서로 아는 m명 또는 모르는 n명이 반드시 존재하는 최소 인원으로, R(m, n)으로 표현해요. 따라서 램지 수를 이용하면 파티에 서로 아는 m명이나 모르는 n명이 반드시 있기 위해서는 몇 명을 불러야 하는지 알 수 있죠. 가장 간단한 파티 문제는 R(3, 3)으로 답은 6명입니다. 

 오늘도 딴 길로 새어버린 퓨처킴! 그래도 그래프 이론의 재밌는 정리들을 소개해 보람있군요. 관심 있는 분들은 ‘디라이브러리’에서 ‘그래프’를 검색해보세요!