악수의 수
모두와 악수를 나누면
교실에 5명의 친구가 모여 있습니다. 모든 사람이 서로 빠짐없이 한 번씩 악수를 나눈다고 해 보세요.
악수는 총 몇 번 이루어질까요? 5명이 각각 4번씩 하니까 20번일까요? 둘이 손을 맞잡을 때 악수 한 번이 동시에 완성된다는 사실을 생각하면 진짜 악수의 수는 몇 번일까요?
이야기
1736년, 스물아홉의 오일러가 쾨니히스베르크의 다리 문제를 풀며 이 사실을 처음 적었습니다. 그러니 이것은 악수 이야기가 아니라 다리 이야기에서 태어난 것입니다.
다리를 한 번씩만 건너 한 바퀴 돌 수 있느냐 — 오일러는 「없다」고 답하면서, 땅마다 붙은 다리의 수를 세어 보라고 했습니다. 그것이 곧 악수 횟수를 세는 일과 같습니다.
그런데 이 단순한 셈에서 그래프 이론이라는 학문이 통째로 시작됩니다. 지하철 노선도, 인터넷 연결망, 사람들의 관계망 — 오늘 우리가 「망」이라 부르는 모든 것이 그 다리 일곱 개에서 뻗어 나왔습니다.
왜 홀수 번 악수한 사람이 짝수 명일까요. 악수 한 번에 두 사람의 횟수가 하나씩 늘어납니다. 그러니 모두의 횟수를 합하면 언제나 악수 수의 두 배, 곧 짝수입니다.
짝수인 사람들끼리 더한 것은 이미 짝수입니다. 그러니 남은 홀수들끼리 더한 것도 짝수여야 하는데, 홀수를 홀수 개 더하면 홀수가 되어 버립니다. 그래서 홀수인 사람은 짝수 명일 수밖에 없습니다.
그는 이 논문에서 「길이나 넓이는 하나도 상관이 없다」고 못 박았습니다. 다리가 얼마나 긴지, 섬이 얼마나 큰지는 답과 무관하고 무엇이 무엇에 붙어 있는가만 문제라는 것이었습니다. 이렇게 크기를 버리고 연결만 보는 눈이 위상수학의 시작이 됩니다.
사람이 늘면 연결이 제곱으로 늡니다. 10명이면 45쌍, 100명이면 4,950쌍입니다.
회의 참석자가 두 배가 되면 소통 비용이 네 배가 되는 것 — 조직 설계와 프로젝트 관리에서 실제로 쓰이는 계산입니다.
계단 넷 — 같은 사실을 네 깊이로
교실에서 악수를 세어 본다
원 위에 점 5개를 찍고, 모든 점끼리 자를 대고 선을 그어 보세요. 오각형의 테두리 선 5개와 안쪽의 별 모양 대각선 5개가 생깁니다.
선을 모두 세어 보면 총 10개입니다. 3명이면 3번, 4명이면 6번, 5명이면 10번… 사람이 늘어날 때마다 악수가 몇 번씩 늘어나는지 손으로 직접 세어 보세요.
모두와 한 번씩 악수해 보세요
그래서 반으로 나눕니다.
n(n−1)/2 로 세기
명이 모였을 때, 1명당 자기 자신을 뺀 명과 악수를 하므로 전체 악수의 시도는 번입니다.
하지만 A와 B가 악수하는 것은 B와 A가 악수하는 것과 같은 1번의 악수이므로 정확히 2로 나누어야 합니다. 따라서 악수의 총 횟수는 조합 공식 이 됩니다.
악수의 총합은 짝수입니다
합이 짝수여야 하기 때문입니다 — 이것이 그래프 이론의 첫 정리입니다.
차수 합 정리로 증명
각 사람을 그래프의 꼭짓점, 악수를 변으로 두면 각 꼭짓점에 연결된 선의 개수를 차수(Degree)라고 합니다.
모든 꼭짓점의 차수를 다 더하면 변 하나가 양 끝 꼭짓점에 차수 1씩을 보태므로 정확히 (변의 수의 2배)가 됩니다. 이로부터 「홀수 차수를 갖는 꼭짓점의 개수는 항상 짝수 개여야 한다」는 악수 보조정리(Handshaking lemma)가 증명됩니다.
몇 명씩 뽑을까요
세 명이 함께 하는 모임은 nC3, 그렇게 이어집니다.
그래프의 기본 보조정리
악수 정리는 그래프 이론에서 오일러 경로의 존재성 증명의 출발점이자, 대수적 위상수학에서 단체 복합체(Simplicial complex)의 1차 사슬 경계 연산 의 성질과 연결됩니다.
차수 열(Degree sequence)이 실제 단순 그래프로 실현 가능한지를 판정하는 에르되시-갈라이 정리(Erdős-Gallai theorem)와 하벨-하키미 알고리즘의 기초가 됩니다.
점이 많아지면 선이 얼마나
이것이 「연결이 늘면 복잡함은 제곱으로 는다」는 말의 정확한 뜻입니다.
풀어 보기
악수의 수와 차수 합 정리. 다음 물음에 답하시오.
(1) 10명이 모인 모임에서 모든 사람이 서로 한 번씩 악수를 할 때 총 악수 횟수를 구하시오.
(2) 어떤 파티에 모인 7명의 사람이 각각 악수한 횟수가 3, 3, 3, 3, 3, 3, 3 번일 수 있는지 판정하고 그 까닭을 서술하시오.
(3) 축구 리그에 8개 팀이 참가하여 모든 팀이 서로 두 번씩 경기(홈 앤드 어웨이)를 치를 때 전체 경기 수를 구하시오.
(2) 는 모든 차수의 합이 홀수가 될 수 없다는 악수 정리를 적용하세요.
답과 풀이 보기
(1) 45 번입니다.
두 사람을 고르는 경우의 수이므로 .
⭐ 한 사람이 아홉 번씩 하니 인데, 악수 한 번을 두 사람이 함께 세었으므로 2 로 나눕니다.
(2) 있을 수 없습니다.
악수 횟수를 모두 더하면 로 홀수입니다.
그런데 악수 한 번은 두 사람의 횟수를 하나씩 올리므로 총합은 언제나 짝수여야 합니다 (악수 정리 : ).
홀수 = 짝수는 될 수 없으므로 그런 파티는 없습니다.
(3) 56 경기입니다.
한 번씩만 붙으면 경기이고, 홈과 어웨이로 두 번씩이므로 .
달리 보면 각 팀이 나머지 일곱 팀의 홈으로 한 번씩 가므로 — 이때는 나누지 않습니다. 홈과 어웨이는 다른 경기이니까요.
(1) 은 나누고 (3) 은 안 나눕니다. 같은 것을 두 번 세었는가만 물으면 됩니다.
이 간단한 정리 하나로 「홀수 번 악수한 사람은 반드시 짝수 명」이라는 것도 바로 나옵니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「두 배로 세기」는 강력한 증명 수법입니다.
- 한붓그리기 — 홀수점의 개수만 세면 판정됩니다
- 망 설계 — 연결의 총합을 두 가지로 세어 성질을 밝힙니다
- 직접 해 보기 — 다섯 사람이 서로 한 번씩 악수하면 열 번입니다. 각자 네 번씩이니 홀수인 사람이 없습니다
이어지는 장
한 번의 악수는 두 사람의 손을 동시에 채우므로, 홀수 개의 다리를 가진 땅이 홀수 개일 수 없다는 쾨니히스베르크의 규칙과 완전히 같은 원리입니다 — 제6장 의 다리 건너기가 교실의 악수로 모습을 바꿉니다.
영감을 받은 곳
레온하르트 오일러가 1736년 쾨니히스베르크 다리 문제를 해결하면서 그래프의 모든 꼭짓점 차수의 합이 변의 수의 정확히 2배가 됨을 증명한 그래프 이론의 기초 정리(악수 보조정리)에서 왔습니다.