Too simple to be simple
꼭짓점도 변도 없는 빈 그래프는 트리(수형도)일까요? 정의를 떠올리면 그럴듯한데, 답은 아니오입니다. 그 이유를 따라가면 "1은 소수가 아니다"와 똑같은 깊은 사연이 나옵니다.
여기서 빈 그래프(null graph)는 꼭짓점이 0개, 변이 0개인 그래프를 말합니다 (꼭짓점은 있는데 변만 없는 그래프와는 다릅니다).
"트리(수형도)란 무엇인가?"를 대충 떠올리면 흔히 "사이클(순환)이 없는 그래프"가 생각납니다. 빈 그래프엔 사이클이 있을 리 없으니, 이 기준만 보면 트리처럼 보이죠. 하지만 이건 트리가 아니라 숲(forest)의 정의입니다.
트리에는 조건이 둘 있습니다.
| 사이클 없음 | 연결됨 (connected) | |
|---|---|---|
| 트리 (tree) | ✓ 필요 | ✓ 필요 |
| 숲 (forest) | ✓ 필요 | ✗ 불필요 |
즉 트리 = 연결 + 사이클 없음, 숲 = 사이클 없음(연결 성분 각각이 트리인 그래프)입니다. 모든 트리는 숲이지만, 그 역은 성립하지 않죠. 그리고 "연결됨"이란 연결 성분(connected component)이 정확히 1개라는 뜻입니다.
빈 그래프를 두 조건에 대입해 봅니다.
따라서 빈 그래프는 숲은 맞지만(트리 0개를 모은 빈 숲), 트리는 아닙니다.
꼭짓점 \(V\), 변 \(E\), 연결 성분 \(c\)개인 숲은 항상 다음을 만족합니다.
$$ V - E = c \qquad(\text{트리는 } c=1 \text{이므로 } V - E = 1) $$빈 그래프는 \(V=0,\ E=0\) 이라 \(V - E = 0 = c\) — 숲 공식은 만족합니다(\(c=0\)). 하지만 트리가 되려면 \(V - E = 1\)이어야 하는데 \(0 \ne 1\). 한 단계 위인 점 하나짜리 그래프는 \(V=1,\ E=0,\ c=1\)이라 \(V-E=1\) — 이건 어엿한 (자명한) 트리입니다. 빈 그래프는 그보다도 비어 있어서 트리 자격에 딱 한 끗 모자랍니다.
빈 그래프가 트리에서 탈락하는 방식은 1이 소수에서 탈락하는 방식과 똑같습니다. 소수는 "약수가 정확히 둘"이고 1은 약수가 하나뿐이라 미달, 트리는 "연결 성분이 정확히 하나"이고 빈 그래프는 0개라 미달 — 둘 다 경계에서 하나 모자란 경우죠.
왜 굳이 이렇게 빡빡하게 정의할까요? 정리가 깔끔해지기 때문입니다. 1을 소수로 인정하면 소인수분해의 유일성이 깨집니다(\(6 = 2\times3 = 1\times2\times3 = \cdots\)). 마찬가지로 빈 그래프를 트리로 인정하면 "트리는 연결 성분이 하나", "트리는 \(V-E=1\)", "두 꼭짓점을 잇는 경로가 유일하다" 같은 깔끔한 정리들이 줄줄이 예외를 달아야 합니다.
단순군(simple group)은 군의 "기본 입자"입니다. 정의는 이렇습니다 — 자명하지 않은 군 \(G\)로서, 정규부분군이 \(\{e\}\)와 \(G\) 자기 자신, 딱 둘뿐인 군. 더 작은 정규부분군으로 "쪼갤" 수 없는 군이죠.
자명군 \(\{e\}\)(원소가 항등원 하나뿐인 군)는 정규부분군이 \(\{e\}\) 하나뿐입니다. 정의가 요구하는 "둘"에 하나 모자라죠. 게다가 정의에 아예 "자명하지 않은"이라는 단서가 박혀 있어 처음부터 배제됩니다.
왜 그럴까요? 단순군은 정수의 소수에 대응합니다. 임의의 유한군은 합성열(composition series)을 통해 단순군들로 분해되고, 그 단순군 조각들은 순서를 빼면 유일합니다(조르당–횔더 정리) — 정확히 소인수분해의 유일성에 해당하죠. 만약 자명군을 단순군으로 인정하면 분해 사이사이에 \(\{e\}\)를 얼마든지 끼워 넣을 수 있어 유일성이 깨집니다. 소수에 1을 넣는 것과 똑같은 실수입니다.
이건 우리의 빈 그래프 이야기의 위상수학 쌍둥이입니다. 연결 공간(connected space)은 소박하게는 "공집합과 전체 말고는, 두 열린집합으로 쪼갤 수 없는 공간"으로 정의되곤 합니다. 이 소박한 정의만 보면 빈 공간 \(\varnothing\)은 쪼갤 거리가 없으니 공허하게 연결처럼 보입니다.
하지만 더 쓸모 있는 현대적 정의는 "연결 성분이 정확히 하나인 공간"입니다. 빈 공간은 점이 하나도 없어 연결 성분이 0개 — 1개가 아니죠. 그래서 표준적으로 빈 공간은 연결 공간이 아니라고 봅니다. (빈 그래프가 연결 성분 0개라 트리가 아니었던 것과 글자 그대로 같은 상황입니다!)
이유도 같습니다. "모든 공간은 연결 성분들의 분리합집합으로 유일하게 쪼개진다"는 깔끔한 정리를 지키려면, 연결 공간은 성분이 정확히 1개여야 합니다. 빈 공간을 연결로 치면 그 "정확히 1개"라는 기준이 흐물흐물해져 버리죠.
체(field)는 사칙연산이 자유로운 가장 좋은 수 체계입니다. 정의의 핵심 공리 하나가 \(0 \ne 1\) — 덧셈 항등원 0과 곱셈 항등원 1이 서로 달라야 한다는 것. 그리고 0이 아닌 모든 원소가 곱셈 역원을 가져야 합니다.
자명환(zero ring) \(\{0\}\)은 원소가 0 하나뿐이라 \(0 = 1\)이 되는 유일한 환입니다. 바로 그 \(0 \ne 1\) 공리를 어기죠. (\(0=1\)이면 모든 원소가 0과 같아져, "0이 아닌 원소"라는 말 자체가 사라집니다.)
여기서도 \(0 \ne 1\)을 굳이 공리에 박아 넣는 이유는 정리들을 지키기 위해서입니다. 예컨대 "체의 아이디얼은 \(\{0\}\)과 자기 자신 딱 둘뿐", "유한체의 크기는 소수의 거듭제곱" 같은 사실들이 자명환을 체로 끼워주는 순간 줄줄이 예외를 달아야 합니다. 역시 경계에서 하나 모자란 자명한 대상을 빼두는 편이 이깁니다.
그래서 결론은 이렇습니다. 빈 그래프는 트리가 되기 싫어서가 아니라, 되기엔 너무 비어 있어서 트리가 아닙니다. 넌, 간단하다고 하기엔 너무 간단해.