두 표찰, 한 나무에 함께 붙일 수 있을까요?

네 끝점이 각각 한 번만 나오는 종이 나무예요. AB와 BC를 한 가지 아래의 전체 명단으로 함께 붙일 수 있는지 판단하고, 정해진 B→D 한 글자 수선 뒤 두 갈래를 그려 검산해요.

밝은 나무 탁자 위 여러 갈래로 나뉜 마른 나뭇가지

이미지: AI 생성 · 수학 이야기

계통도에서 한 가지의 무리는 공통 조상과 그 자손 전체를 포함해요. 이를 네 끝점 A, B, C, D의 종이 나무로 바꿔 볼까요? 뿌리는 하나이고, 뿌리 아닌 점의 부모는 하나예요. 끝점은 각각 한 번만 나와요. 선이 합쳐지는 그물은 쓰지 않아요.

점 v 아래에 있는 끝점 이름의 집합을 K(v)라 해 볼까요? 표찰은 그 명단 전체를 적어야 하며 이름을 빼거나 덧붙일 수 없어요. S={A,B}, T={B,C} 두 표찰을 한 나무의 두 가지에 함께 붙일 수 있을까요? 나무의 모양은 자유롭게 만들 수 있어요.

두 명단은 B를 공유해요. 따라서 두 가지의 시작점은 뿌리에서 B로 가는 한 경로에 함께 있어요. 아래 점의 끝점들은 위 점의 끝점 명단에 모두 들어가야 해요. 그런데

S∩T={B},S∖T={A},T∖S={C}.S\cap T=\{B\},\qquad S\setminus T=\{A\},\qquad T\setminus S=\{C\}.

S에는 T에 없는 A가 있고, T에는 S에 없는 C가 있어요. 서로 포함되지 않으므로 두 가지를 동시에 만들 수 없어요. 표찰을 따로 그럴듯하게 그리는 것만으로는 충분하지 않아요.

이제 S는 유지하고 T의 B만 D로 고쳐 T′={C,D}로 만들어 봐요. 뿌리를 두 갈래로 나누어 왼쪽 가지 u의 끝을 A, B, 오른쪽 가지 v의 끝을 C, D로 붙이면 돼요.

K(u)=S,K(v)=T′,S∩T′=∅.K(u)=S,\qquad K(v)=T^{\prime},\qquad S\cap T^{\prime}=\varnothing.

바뀐 글자는 한 곳이에요. 안 고치면 불가능하고 한 곳을 고치면 구성되므로 최소 수정 수는 1입니다. 유일한 수선법을 찾는 문제는 아니에요. 두 표찰을 함께 만족시키는 나무를 그리고 각 가지 아래 명단으로 검산해 봐요. 실제 생물의 혈연을 판정하는 활동은 아니에요.

착안: UC Berkeley Understanding Evolution, Understanding phylogenies의 모든 자손과 중첩 관계 설명. 네 이름·동시 가능성 질문·한 글자 수선은 자체 구성했으며 원전 도판은 옮기지 않았어요.

이 글 공유하기

개인정보 및 방문 통계 안내