측지거리 — 거듭제곱에서 최단거리 읽어내기

1. 오늘의 질문 (Today's Question)

단원 1-3에서 $A^k$의 값은 걷기의 개수일 뿐 경로가 아니라는 것을 배웠다. 값 자체는 부풀려져 있다. 그런데 이렇게 물으면 얘기가 달라진다:

답: $A, A^2, A^3, \dots$를 차례로 보며 $[i,j]$ 칸에 0이 아닌 값이 처음 나타나는 $k$를 찾으면 된다. 개수는 부정확하지만 "처음 등장하는 시점"은 정확하다. 왜 그런지가 오늘의 핵심이다.

단원 1-3에서 이미 구해 둔 세 행렬을 그대로 쓴다. $A^4$만 새로 필요하다:

2. 측지거리의 정의 (Definition of Geodesic Distance)

3. 왜 "처음 등장하는 $k$"는 정확한가 (Why the First Hit Is Exact)

단원 1-3의 결론은 "$A^k$는 걷기를 센다"였다. 걷기는 경로보다 많으니 $(A^3)[1,3]=2$처럼 실제 경로가 0개인데도 값이 2일 수 있었다. 그런데도 최단거리를 읽는 데는 문제가 없다. 근거는 다음 한 줄이다:

왜 그런가. 만약 최단 걷기가 같은 학생 $v$를 두 번 지난다고 하자. 그러면 그 걷기는 $i \to \cdots \to v \to \cdots \to v \to \cdots \to j$ 모양이다. 가운데 $v$에서 $v$로 돌아오는 부분은 잘라내도 여전히 $i$에서 $j$로 가는 걷기다. 잘라낸 쪽이 더 짧으므로, 원래 걷기가 최단이었다는 가정에 모순이다. 따라서 최단 걷기에는 재방문이 없다. ∎

구체적으로 확인해 보자. 단원 1-3에서 본 M1→M3의 재방문 걷기들:

4. 손 계산 ① $d(M_2, M_5)$ (Reading One Cell)

M2에서 M5로 가는 최단거리를 구한다. 네 행렬의 $[2,5]$ 칸을 $k$가 커지는 순서로 확인한다:

경로 복원. $k=3$에서 값이 1이므로 걷기는 하나뿐이다. 단원 1-3 §6의 전수 목록에서 $[2,5]$에 해당하는 걷기는 M2→M3→M1→M5였고, 세 걸음 모두 새 사람을 밟는 경로였다. §3의 정리가 말한 대로다 — 최단 걷기는 경로다.

5. 손 계산 ② 거리행렬 전체 채우기 (Filling the Whole Matrix)

같은 절차를 20개 칸(대각선 제외)에 모두 적용한다. 표에는 각 칸에서 처음 1이 나온 $k$를 적는다.

정리하면 거리행렬 $D$는:

6. 거리는 대칭이 아니다 (Distance Is Not Symmetric)

방향 네트워크에서 $d(i,j)$와 $d(j,i)$는 다를 수 있다. $D$에서 짝을 찾아보면:

7. 지름과 평균거리 (Diameter & Mean Distance)

거리행렬을 하나의 숫자로 요약하는 두 방법이 있다. 둘 다 $\infty$를 어떻게 처리하는가가 관건이다.

지름 (Diameter)

$D$에서 $\infty$를 뺀 가장 큰 값을 찾는다. 3이 두 개 있다 ($d(M_2,M_5)=3$, $d(M_5,M_4)=3$) → 지름 = 3. "도달 가능한 두 학생 사이라도 최대 3단계면 소식이 전해진다"는 뜻이다.

평균 측지거리 (Mean Geodesic Distance)

$\infty$는 평균에 넣을 수 없으므로 도달 가능한 순서쌍만 평균한다. $D$에서 대각선(0)과 $\infty$ 4칸을 빼면 남는 칸은 $20 - 4 = 16$개다. 값별로 개수를 세어 더한다:

8. R 검증 (Verification in R)

library(igraph)
g <- graph_from_adjacency_matrix(A, mode = "directed")

distances(g, mode = "out")
#     M1  M2  M3 M4  M5
#  M1   0   1   1  2   1
#  M2   2   0   1  2   3
#  M3   1   2   0  1   2
#  M4 Inf Inf Inf  0 Inf     ← M4에서 나갈 수 없다
#  M5   1   2   2  3   0

diameter(g)                # 3
mean_distance(g)           # 1.6875   ← Inf 제외한 16쌍의 평균

# mode 인자 주의: "out"은 나가는 방향(내가 남에게), "in"은 들어오는 방향
distances(g, mode = "in")["M4", ]   # M4로 들어오는 거리: 2 2 1 0 3

§2의 정의를 그대로 코드로 옮겨 손 계산과 맞춰 볼 수도 있다:

# A^k에서 처음 0이 아닌 k 찾기 — 정의를 직접 구현
D <- matrix(Inf, 5, 5, dimnames = dimnames(A))
diag(D) <- 0
P <- diag(5)
for (k in 1:4) {
  P <- P %*% A                      # P = A^k
  D[D == Inf & P > 0] <- k          # 아직 안 채워진 칸만 채운다
}
D                                    # distances(g, mode="out")와 동일

# sna 패키지
library(sna)
geodist(A)$gdist    # 위 distances(g,"out")와 동일 (도달 불가는 Inf)
geodist(A)$counts   # 최단 경로가 몇 개인지 — 단원 2-3(매개 중심성)의 재료

9. 교실 해석 (Classroom Interpretation)

10. 연습문제 (Exercises)

11. 연습문제 해설과 답 (Solutions)

11-1. 문제 1 — $d(M_5,M_4)$ (One More Cell)

① 세 행렬의 $[5,4]$ 칸. §1의 행렬들에서 5행 4열만 뽑아 온다:

② 판정. 처음 0이 아닌 값이 $k=3$에서 나왔으므로

③ 경로 복원. M4를 지명한 사람은 M3 한 명뿐이므로 마지막 걸음은 반드시 M3→M4다. 그렇다면 앞의 2걸음은 M5에서 M3까지 가는 길이어야 하고, $(A^2)[5,3]=1$이 그것이다 — M5→M1→M3(단원 1-2 연습문제 1). 이어 붙이면:

11-2. 문제 2 — 비대칭의 원인과 회복 (Why M4's Row Is All Infinite)

① 원인. 단원 1-4에서 구한 값을 그대로 쓴다:

② $A[4,3]=1$을 추가하면. 힌트대로, M4에서 나가는 유일한 지명이 M3이므로 M4에서 어디로 가든 첫 걸음은 M3이고 그 뒤는 M3에서 가는 길과 똑같다. 따라서 각 목적지 $j$에 대해

$D$의 M3 행 $(1,\,2,\,0,\,1,\,2)$를 가져와 하나씩 더한다:

# 문제 1
A2 <- A %*% A; A3 <- A2 %*% A
c(A[5,4], A2[5,4], A3[5,4])       # 0 0 1  → d = 3
all_simple_paths(g, from="M5", to="M4")
# [[1]] M5 M1 M2 M3 M4   ← 길이 4
# [[2]] M5 M1 M3 M4      ← 길이 3 = 최단 경로

# 문제 2
Ax <- A; Ax[4,3] <- 1
gx <- graph_from_adjacency_matrix(Ax, mode="directed")
distances(gx, mode="out")["M4", ]   # M1 M2 M3 M4 M5 → 2 3 1 0 3  ✓
mean_distance(gx)                   # 1.8    ← 1.6875에서 늘어났다
diameter(gx)                        # 3      ← 그대로
is_connected(gx, mode = "strong")   # TRUE   ← 모든 쌍이 서로 도달 가능

다음 단원 — 1-7: 도달가능성 행렬과 강한/약한 컴포넌트. 오늘 $\infty$로 표시한 칸들을 0/1로만 요약하면 도달가능성 행렬이 되고, 거기서 "서로 오갈 수 있는 학생 집단"이 드러난다. · 이 문서: notes/06_단원1-6_측지거리_Ak에서_최단거리.html