브런치 스토리

라이킷 15 댓글

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

파이썬으로 '악수 레마' 시뮬레이션해 보기.

무방향 그래프의 차수 합과 간선 개수

by 맷수달 Jan 23. 2025

인공지능으로 생성한 '악수 레마'를 의인화 한 이미지

0. 들어가며

무방향 그래프 G=(V, E)가 있을 때, 각 정점(vertex) v에는 차수(degree) d(v)가 정의됩니다. 이는 정점 v가 연결(incident)된 간선(edge)의 개수이죠. 이때, ∑v∈Vd(v)(모든 정점의 차수 합)을 구하면, 결과가 2×∣E∣(간선의 개수 ∣E∣의 두 배)와 정확히 같아진다는 사실이 알려져 있습니다. 왜 이런 일이 일어날까요?

그래프 이론에서는 이 사실을 "Handshaking Lemma" 혹은 "악수 레마"라고 부릅니다. "파티에서 한 사람이 '내가 악수한 횟수'를 전부 합하면, 실제 악수 이벤트의 두 배"라는 비유로도 자주 설명되죠.

1. 직관적 설명

위의 내용이 좀 추상적이라서 어렵게 느껴지실 분들을 위해 위에서 언급된 파티에서 한 악수 이벤트로 직관적으로 설명해 보겠습니다. 이 직관적인 설명은 o1 pro의 도움을 받았습니다.

1. 파티 상황 설정

한 방에 여러 명의 사람이 모여 있습니다.(이 사람들이 그래프의 '정점'에 해당).

서로 알고 있거나, 혹은 인사를 하기 위해 "악수"를 합니다(이 악수가 그래프의 '간선'에 해당).

2. 악수는 반드시 2명이 함께

어떤 사람 A가 악수를 할 때, 혼자서는 악수를 할 수 없죠.(물론 할 수도 있으나 여기서는 못한다고 가정하겠습니다.)

악수는 항상 A와 B, 두 사람이 손을 맞잡아야 합니다.

즉, "악수 한 번"이 일어나면 반드시 2명의 손이 동시에 쓰입니다.

3. 악수를 세는 두 가지 방법

각 사람 입장에서 "내가 오늘 몇 번 악수를 했지?"를 모두 세고, 그걸 전부 더하기.

파티 전체에서 "실제로 악수가 일어난 횟수(악수 이벤트)"를 직접 세기.

4. 이 두 방법이 왜 같은가?

악수 1회가 일어날 때마다, 참여한 두 사람은 각각 자신의 "악수 횟수"를 +1번 셉(count) 니다. 합니다.

그렇다면 "각 사람의 악수 횟수를 모두 합한 값"은, 결국 "실제 악수 횟수"를 두 번씩 더한 것과 똑같아집니다.

즉, 악수라는 이벤트는 {사람 A, 사람 B}로 정의되는데

각 악수 하나당 → 사람 A 입장 +1, 사람 B 입장 +1, 총 +2가 반영.

5. 결론

파티에서 "사람들이 개별적으로 세어놓은 악수 횟수를 모아보면" 그것은 결국 "파티 전체에서 발생한 실제 악수 횟수의 2배"가 됩니다.

즉, (모든 사람의 악수 횟수 합) = 2 × (실제 악수 총 횟수).

2. 그래프 이론과의 대응

악수 정리를 그래프 이론에 그대로 옮겨 보면 다음과 같습니다:

사람 ↔ 정점(vertex)

악수(손 맞잡기) ↔ 간선(edge)

"내가 몇 번 악수했나?" ↔ 정점의 차수(degree)

'차수'라는 건 한 정점이 간선과 몇 번 연결되어 있는지를 나타내는 지표입니다.

"전체 사람의 악수 횟수 합" ↔ ∑v∈Vd(v)

"실제 악수 총 횟수" ↔ ∣E∣ (간선의 개수)

결국 "그래프에서 모든 정점 차수를 합한 결과가 간선 수의 두 배"라는 말은, "파티장에서 각 사람이 한 악수 횟수를 전부 더하면, 실제로 이루어진 악수 횟수(이벤트) 보다 정확히 2배가 나온다"는 것과 같은 이야기입니다.

3. 증명

이제 실제로 악수 레마를 증명해 보겠습니다.

3.1. 증명할 명제(Handshaking Lemma)

명제: 무방향 그래프 G=(V, E)에서 모든 정점의 차수를 더한 값은 간선의 개수의 두 배이다. 즉,

∑v∈Vd(v) = 2×∣E∣

우리는 위의 명제를 이중 계수(double counting) 기법으로 증명합니다. 이중 계수법은 어떤 집합의 원소 수를 '두 가지 다른 방법'으로 세어서 양쪽이 같다는 사실을 사용하는 증명 기법입니다. 여기서 '계수'는 다항식에서의 '계수'가 아닌 어떤 오브젝트 등을 '센다(count)'의 의미에서의 '계수'입니다.

3.2. 이중 계수를 위한 집합 정의

핵심 아이디어: 정점과 간선의 "부착(incident) 관계"를 나타내는 순서쌍을 모두 모은 뒤, 그 개수를 "두 가지 방법"으로 세어보면, 두 결과가 같아야 하므로 ∑d(v)=2×∣E∣임을 알 수 있습니다.

먼저 다음과 같은 집합 S를 정의합니다.

S = { (v, e) ∣ v∈V, e∈E, 그리고 v와 e가 incident 한 관계}

여기서 "v와 e가 incident 하다"는 말은, 정점 v가 간선 e의 한 끝점이라는 뜻입니다.

즉, 무방향 간선 e가 {x, y} 형태라면, v=x이거나 v=y일 때 (v, e)∈S(v, e)가 됩니다.

3.3. 집합 S의 크기를 세는 두 가지 방법

3.3.1. (방법 1) 정점을 기준으로 세기

정점 하나 v∈V를 고정하고, "v에 incident 한 간선"을 모두 센다.

무방향 그래프에서 v의 차수 d(v))는 v가 연결된 간선의 개수이므로, "v에 incident 한 간선"의 개수는 d(v)가 됩니다.

따라서 정점 v마다 (v,⋅)에 해당하는 원소가 d(v) 개씩 존재합니다.

정점이 V 전체에 대해 이렇게 세면, 원소의 총합은 ∑v∈Vd(v)

즉, ∣S∣ = ∑v∈Vd(v)

3.3.2. (방법 2) 간선을 기준으로 세기

간선 하나 e∈E를 고정하고, "e에 incident 한 정점"을 모두 센다.

무방향 그래프에서 간선 e는 항상 두 정점(끝점) {u, w}로 이루어져 있습니다. (자기 루프나 멀티그래프가 아니라면, 보통 서로 다른 두 정점으로 간선을 구성한다고 봄)

따라서 간선 e 하나당, incident 한 정점이 정확하게 2개 존재합니다.

간선이 E 전체에 대해 이렇게 세면, 원소의 총합은 2×∣E∣

즉, ∣S∣ = 2×∣E∣

4. 증명 마무리

집합 S의 원소 개수를 두 방식으로 모두 세었으므로, ∣S∣ = ∑v∈Vd(v)와 ∣S∣ = 2×∣E∣ 는 동일한 값을 나타냅니다. 결국, ∑v∈Vd(v) = 2×∣E∣ 가 됩니다.

이를 통해 무방향 그래프에서 모든 정점 차수를 합한 값 = 간선 수의 두 배라는 사실이 증명되었습니다.

5. 파이썬 코드로 시뮬레이션해 보기

아래의 예시에 대해서 파이썬 코드로 시뮬레이션해 보겠습니다.

5.1. 예시로 확인

그래프 G가 다음처럼 다섯 정점 V={A, B, C, D, E}를 가지고, 간선 E={{A, B}, {A, C}, {B, C}, {C, D}, {D, E}}로 구성되어 있다고 하겠습니다. 즉,

정점: A, B, C, D, E

간선: {A, B}, {A, C}, {B, C}, {C, D}, {D, E}

그렇다면,

정점별 차수: d(A)=2, d(B)=2, d(C)=3, d(D)=2, d(E)=1

차수 합 ∑v∈V(G) d(v)=2+2+3+2+1=10

간선의 개수 ∣E(G)∣=5, 따라서 2×∣E(G)∣=2×5=10

이 예시에서 실제로 ∑v∈V(G)d(v)=2×∣E(G)∣가 성립함을 볼 수 있습니다.

5.2. 예시에 대한 파이썬 코드

무방향 그래프에서 ∑v∈Vd(v)와 2×∣E∣가 같음을 "시뮬레이션" 방식으로 확인하는 간단한 파이썬 코드입니다. 이 코드는

작은 예시 그래프(정점 A, B, C, D, E) 정의

정점 차수 합 계산

간선 개수 및 2∣E∣ 계산

이중 계수에 해당하는 집합 S={(v, e)} 구성

각 결괏값을 출력하여 ∑v∈Vd(v)=2×∣E∣ 임을 확인

을 단계별로 수행합니다. 주석을 아주 자세하게 첨부했기 때문에 코드를 쉽게 이해하실 수 있을 것입니다.

https://gist.github.com/otter275/665a77a285d9d8a2b275dd3ac61a0550

코드를 실행하면 세 값이 모두 10으로 동일하게 나옵니다.

5.3. 코드 실행 흐름

1. 그래프 정의

graph 딕셔너리는 각 정점이 어떤 이웃과 연결되어 있는지 set으로 저장합니다.

2. 차수 합 계산

get_sum_of_degrees(graph) 함수를 통해 각 정점에 대해 get_degree(v, graph) 호출 ⇒ 최종적으로 ∑vd(v) 계산.

3. 간선 집합 생성

get_edge_set(graph)에서 frozenset을 이용해 무방향 간선을 유일하게 표현. 중복 없이 {frozenset({'A', 'B'}),...} 형태로 집합을 얻어냄

∣E∣ = 간선 집합의 크기를 세어 얻음.

4. (v, e) 쌍 집합 S 구성

build_incident_pairs(graph) 함수에서, 정점 v와 간선 e가 incident(부착) 관계라면 (v, e)를 S에 추가.

∣S∣를 세면, 이중 계수를 수행했을 때 "정점 기준"과 "간선 기준"에서 원소를 세는 과정이 어떻게 동일 결과로 이어지는지 볼 수 있음.

5. 비교 출력

∑d(v), 2×∣E∣, ∣S∣를 각각 출력해 보고, 세 값(10)이 모두 동일함을 확인.

이 과정을 통해 실제 코드 레벨에서도 무방향 그래프에서 ∑v∈Vd(v)=2×∣E∣가 성립한다는 것을 직접 실험(시뮬레이션) 해 볼 수 있습니다.

6. 결론

1. 이중 계수(double counting)를 이용한 증명

∑v∈Vd(v) = 2×∣E∣

정점을 기준으로 세면 "정점 v마다 d(v)"이고,

간선을 기준으로 세면 "간선 하나당 2개의 정점에 incident"이므로 2×∣E∣

둘 다 같은 집합 S의 원소 개수를 센 것이므로 결과가 동일해야 합니다.

2. 파이썬 코드 시뮬레이션

그래프의 인접 리스트를 정의하고, 정점 차수 합 ∑vd(v)와 간선 개수 ∣E∣ 및 (정점, 간선) 쌍 집합의 크기를 실제로 계산해 보면, 모두 같은 숫자가 나옵니다.

3. 추가적인 직관적 관찰

"파티에서 한 사람이 악수한 횟수를 모두 합하면, 실제 악수 횟수(이벤트)의 2배"라는 비유로도 자주 설명됩니다.

이는 무방향 간선 하나가 정확히 두 정점(사람)과 연결되기 때문입니다.

이상으로, 무방향 그래프의 차수 합이 2×∣E∣와 같다는 Handshaking Lemma를 실제 코드 시뮬레이션과 함께 확인해 보았습니다. 그래프 이론을 공부하거나, 그래프 신경망, 소셜 네트워크 분석("내 친구 수" 등)을 진행할 때도 자주 등장하는 핵심 개념이니, 한 번쯤 직접 코딩해 보며 확실히 이해해 두면 좋겠습니다.

keyword