이번 시간에는 maximal과 maximum에 대해서 각각이 어떤 의미를 갖는지 정리해 보도록 하겠습니다. 두 단어는 매우 비슷하게 생겼지만 그 의미는 많이 다른데요, 어떻게 다른 것인지 예시를 통해 짚어 보도록 하죠. 본문에는 크거나 많은 것이 척도인 maximal과 maximum에 대해서만 적을 예정이나, 작거나 적은 것이 척도인 minimal과 minimum도 비슷하게 적용할 수 있습니다.
저는 현재 대학원생이며, 학부 자료구조 과목과 알고리즘 과목의 조교를 맡고 있습니다. 평소에는 과제를 채점하는 것이 주된 조교 일이지만, 시험 기간에는 시험을 감독하는 것도 제가 해야하는 일 중 하나입니다. 학기마다 시험을 치는 장소가 달라지기도 하지만 대개 저희가 배정 받는 장소는 다음 그림과 같이 아홉 석의 긴 책상 여러 개로 구성된 강의실입니다. 이 책상은 바닥에 고정되어 있어서 움직일 수 없습니다.
이 강의실을 배정 받으면 개인적으로는 약간 짜증이 나는데, 왜냐하면 학생들이 아무렇게나 앉기 때문입니다. 다들 아실 테지만 시험을 칠 때는 나름의 커닝 방지를 위해서 두 사람이 서로 붙어 앉지 못하게 합니다. 그런데 이 강의실은 그렇게 크지 않아서 아무렇게나 앉으면 학생들이 전부 앉지 못하는 경우가 발생합니다. 따라서 최대한 꽉꽉 채워 앉아야 합니다. 그러면 이 책상에서는 어떻게 앉아야 할까요? 네, 다음 그림과 같이 앉는 것이 최선입니다.
그런데 매 학기 보면 제가 시험 감독 준비하러 강의실에 들어가기도 전에 일찌감치 와서 꼭 다음 그림과 같이 앉는 학생들이 있습니다.
사실 한둘이 아닙니다. 꽤 많죠. 아무튼 학생이 이렇게 앉아 버리면 무슨 문제가 발생할까요? 네, 이 학생이 자리를 옮기지 않는 이상에야 이 책상에 다섯 명을 서로 한 칸씩 띄어서 앉힐 방법이 없습니다. 아무리 잘해도 네 명이 최선입니다.
그러면 저는 해당 자리에 앉은 학생들에게 자리를 좀 옮겨 달라고 열심히 부탁을 하고 다닙니다. 하, 공대생이 많이 듣는 공대 수업인데 알아서 딱 최적의 자리에 앉아 주면 참 고맙겠군요. 아무튼 이 예시에 오늘의 주제인 maximal과 maximum의 비밀(?)이 숨어있습니다.
먼저 maximum부터 알아 보겠습니다. 이는 우리가 고려하는 것 중에서 가장 많은 것을 의미합니다. 위 예시에서 아홉 석의 책상에 최대로 많은 학생을 한 칸씩 띄어서 앉히는 방법은 그림 2와 같이 다섯 명을 앉히는 것입니다. 그러므로 그 방법이 학생이 한 칸씩 띄어서 책상에 앉는 여러 방법 중에서 maximum을 이루는 방법이 됩니다.
이제 maximal에 대해서 알아 보죠. 사실 대개의 경우 maximal이라는 단어의 앞에는 inclusion-wise라는 단어가 생략되어 있습니다. 직역을 해보자면 '포함 관계에 따라 최대'인 것이죠. 우리 말로는 '극대(極大)'로도 쓰이는 것 같습니다. 즉, maximal은 그림 4처럼 주어진 것에서 더이상 무언가를 넣을 수 없는 상태를 의미합니다. 반대로 그림 3에서 주어진 방법은 maximal이 아니죠. 여기에는 서로 붙어있지 않도록 하면서 학생을 한 명 더 앉히는 방법이 존재하기 때문입니다.
몇 가지 쉽게 알 수 있는 성질에 대해서 간략하게 짚고 넘어 가죠.
- Maximum인 것은 maximal이기도 합니다. 하지만 maximal이라고 maximum인 것은 아닙니다. 당장에 그림 4는 maximal한 방법이지만 maximum을 이루지는 않습니다.
- 정의에 의해 maximum을 이루는 것들의 크기는 모두 동일합니다. 하지만 maximal이라고 하여 그 크기가 모두 동일한 것은 아닙니다. 당장 그림 2와 그림 4의 학생의 수가 다릅니다. 좀더 생각하면 세 명의 학생으로도 maximal한 방법을 만들 수 있습니다.
비슷하게 minimum과 minimal에 대해서 정의를 하자면, minimum은 고려하는 것 중에서 가장 크기가 작은 것을 의미하며 반대로 minimal은 어떤 주어진 것에서 무언가를 빼면 더이상 원하는 성질을 만족하지 못하는 경우를 뜻합니다.
마지막으로 maximal matching과 maximum matching에 대해서 알아 보면서 글을 마무리짓도록 하겠습니다. 제 블로그의 글 중 태반이 matching에 관련된 것이니 만큼 matching의 정의에 대해서는 잘 아시겠지만, 간단히 짚고 넘어가자면, 어떤 그래프 \(G = (V, E) \)가 주어졌을 때, 어떤 \(M \subseteq E\)에 대해 \(M\)에 속한 임의의 서로 다른 두 간선이 서로 정점을 공유하지 않으면 우리는 \(M\)을 matching이라고 부릅니다. 크기가 작은 matching은 구하기 쉽기 때문에 대개 우리의 관심사는 maximum matching, 즉 matching 중에서 크기가 가장 큰 것을 구하는 것입니다.
그러면 maximal matching은 무엇일까요? 위 정의에 따르면 어떤 matching에 더 이상 간선을 넣지 못하는 때에 그 matching을 maximal matching이라고 부릅니다. 좀더 엄밀히 말하면 어떤 matching \(M\)이 주어졌을 때, \(M\)에 속하지 않은 임의의 간선 \(e \in E \setminus M\)에 대해, \( M \cup \{ e \} \)가 matching이 아니면 우리는 \(M\)을 maximal matching이라고 부른다는 겁니다.
앞에서 살펴 본 대로 maximal matching이라고 maximum matching은 아닙니다. 당장 그림 5에 주어진 그래프에서 maximum matching은 다음과 같이 크기가 4인 perfect matching입니다.
그렇다면 maximal matching은 얼마큼 클까요? 흥미롭게도 항상 maximum matching의 절반보다는 크거나 같다는 것을 보일 수 있습니다.
정리 1. Maximal matching과 maximum matching의 관계
임의의 그래프 \(G = (V, E)\)에 대해, \(M\)을 \(G\)의 임의의 maximal matching, \(M^\star\)를 \(G\)의 임의의 maximum matching이라고 하자. 그러면 항상 \( |M| \geq \frac{|M^\star|}{2} \)가 성립한다.
[증명] 임의의 정점 \(v \in V\)에 대해서 \( M^\star(v) \)를 \(M^\star\)에서 \(v\)와 짝지어진 정점이라고 하겠습니다. 만약 \(v\)가 \(M^\star\)에 대해 짝지어지지 않았다면 그냥 무시하도록 하겠습니다. 증명의 방법은 간단합니다. 이제부터 \(M\)의 간선을 하나씩 꺼내서 지우도록 하겠습니다. 매번 간선 \( (u, v) \in M \)을 지울 때마다 \( (u, M^\star(u)) \)와 \( (v, M^\star(v)) \)를 함께 삭제할 것입니다. 그러면 매번 \(M\)의 간선을 하나 뺄 때마다 최대 두 개의 간선이 \(M^\star\)에서 삭제됩니다. 그런데 만약 \( |M| < \frac{|M^\star|}{2} \)라면, 즉 \( |M^\star| > 2 |M| \)이라면, 분명 \(M^\star\)에는 아직 삭제되지 않은 간선이 하나는 존재할 것입니다. 이 간선은 원래 \(M\)에 있던 어떤 간선과도 정점을 공유하지 않았기 때문에 아직 살아남은 것입니다. 따라서 \(M \cup \{ e \}\)도 matching이라는 사실을 알 수 있고, 이는 \(M\)이 원래 maximal matching이었다는 조건에 위배가 됩니다. ■
이번 시간에는 간단히 maximal과 maximum(그리고 minimal과 minimum)에 대해서 알아 보았습니다. 많이 사용되는 단어들임에도 불구하고 학부 자료구조 시간이나 알고리즘 시간에 제대로 짚고 넘어가는 경우가 잘 없는 것 같아서 간단히 정리해 보았습니다.
잘못된 점이 있거나 궁금하신 점이 있으시면 알려주시기 바랍니다. 고맙습니다. :)
'수학적 도구 > Basic' 카테고리의 다른 글
| 이산 푸리에 변환 (Discrete Fourier Transform) (0) | 2023.10.08 |
|---|
