Lecture 12. 그래프와 네트워크 — 파이썬 실습 - 선형대수

L12 서술 파트에서 결합행렬의 네 부분공간이 각각 물리적 의미를 갖는 것을 보았다. 이 노트북에서는 그것을 직접 계산하고, 오일러 공식이 정말 언제나 성립하는지 무작위 그래프로 확인해 보도록 하자.

서술 파트의 내용	여기서 확인하는 방법
$A\vv{x}$ 는 전위차	전위를 주고 간선마다 차이를 계산한다
$N(A)$ 는 상수 전위	연결 조각 수와 영공간 차원을 비교한다
랭크 $=$ 신장나무의 간선 수	랭크를 올리는 간선을 골라 나무를 만든다
$N(A^{\mathsf{T}})$ 의 기저는 루프	손으로 찾은 루프와 같은 공간인지 본다
오일러 공식	무작위 그래프 여러 개로 검산한다
$A^{\mathsf{T}}CA$	회로를 실제로 풀어 본다

0. 준비¶

import numpy as np
import networkx as nx
from scipy.linalg import null_space

from linalg_viz import show_matrix

np.set_printoptions(precision=3, suppress=True)
rng = np.random.default_rng(0)
print("numpy", np.__version__, " networkx", nx.__version__)

numpy 2.5.2  networkx 3.6.1

def 결합행렬(간선, n노드):
    """각 행이 하나의 간선. 꼬리에 -1, 머리에 +1 을 넣는다."""
    A = np.zeros((len(간선), n노드))
    for k, (출발, 도착) in enumerate(간선):
        A[k, 출발] = -1.0
        A[k, 도착] = +1.0
    return A

간선 = [(0, 1), (1, 2), (0, 2), (0, 3), (2, 3)]      # 0부터 세므로 노드 1~4 는 0~3
n노드 = 4
m간선 = len(간선)

A = 결합행렬(간선, n노드)
print(show_matrix(A, "A ="))
print(f"크기 : {A.shape}   (간선 {m간선}개 x 노드 {n노드}개)")
print("rank :", np.linalg.matrix_rank(A))

A =
[  -1    1    0    0 ]
[   0   -1    1    0 ]
[  -1    0    1    0 ]
[  -1    0    0    1 ]
[   0    0   -1    1 ]
크기 : (5, 4)   (간선 5개 x 노드 4개)
rank : 3

1. $A\vv{x}$ 는 전위차이다¶

노드마다 전위를 하나씩 주면 $A\vv{x}$ 가 간선마다의 전위차를 돌려준다.

x = np.array([0.0, 3.0, 5.0, 2.0])       # 노드 1~4 의 전위

print("전위 x =", x)
print("A x    =", A @ x)
print()
for k, (출발, 도착) in enumerate(간선):
    print(f"  e{k + 1} : 노드 {출발 + 1} -> {도착 + 1},"
          f"  x[{도착 + 1}] - x[{출발 + 1}] = {x[도착] - x[출발]:g}")

전위 x = [0. 3. 5. 2.]
A x    = [ 3.  2.  5.  2. -3.]

  e1 : 노드 1 -> 2,  x[2] - x[1] = 3
  e2 : 노드 2 -> 3,  x[3] - x[2] = 2
  e3 : 노드 1 -> 3,  x[3] - x[1] = 5
  e4 : 노드 1 -> 4,  x[4] - x[1] = 2
  e5 : 노드 3 -> 4,  x[4] - x[3] = -3

2. 영공간 — 전위의 기준점¶

$A\vv{x} = \vv{0}$ 은 모든 간선의 전위차가 0이라는 뜻이다. 연결된 그래프라면 모든 전위가 같아야 한다.

N = null_space(A)
print(show_matrix(N, "N(A) 의 기저"))
print("차원 :", N.shape[1])
print()
print("첫 성분으로 나누면 :", np.round(N[:, 0] / N[0, 0], 10) + 0.0)

N(A) 의 기저
[  -0.5 ]
[  -0.5 ]
[  -0.5 ]
[  -0.5 ]
차원 : 1

첫 성분으로 나누면 : [1. 1. 1. 1.]

모든 전위를 똑같이 올려도 전위차는 그대로이다.

print("A x         =", A @ x)
print("A (x + 100) =", A @ (x + 100.0))
print("같은가 :", np.allclose(A @ x, A @ (x + 100.0)))

A x         = [ 3.  2.  5.  2. -3.]
A (x + 100) = [ 3.  2.  5.  2. -3.]
같은가 : True

그래프가 두 조각으로 나뉘면 영공간의 차원도 2가 된다. 조각마다 기준점을 따로 정할 수 있기 때문이다.

두조각 = [(0, 1), (1, 2), (3, 4)]        # {1,2,3} 과 {4,5} 로 나뉜다
A2 = 결합행렬(두조각, 5)

print("간선 :", [(a + 1, b + 1) for a, b in 두조각])
print("rank        :", np.linalg.matrix_rank(A2), "  (n - c = 5 - 2 =", 5 - 2, ")")
print("dim N(A)    :", null_space(A2).shape[1], " -> 연결 조각의 개수")
print(show_matrix(null_space(A2), "scipy 가 준 기저"))

간선 : [(1, 2), (2, 3), (4, 5)]
rank        : 3   (n - c = 5 - 2 = 3 )
dim N(A)    : 2  -> 연결 조각의 개수
scipy 가 준 기저
[   0.408   -0.408 ]
[   0.408   -0.408 ]
[   0.408   -0.408 ]
[     0.5      0.5 ]
[     0.5      0.5 ]

scipy 가 준 기저는 두 조각이 섞여 있다. 조각마다 1을 채운 벡터로 바꿔 놓으면 뜻이 분명해진다.

지시1 = np.array([1.0, 1, 1, 0, 0])       # 조각 {1,2,3} 만 1
지시2 = np.array([0.0, 0, 0, 1, 1])       # 조각 {4,5} 만 1

for 이름, v in [("지시1", 지시1), ("지시2", 지시2)]:
    print(f"{이름} = {v}   A v = {np.round(A2 @ v, 10) + 0.0}")

print()
print("scipy 의 기저와 같은 공간인가 :",
      np.linalg.matrix_rank(np.column_stack([지시1, 지시2, null_space(A2)])) == 2)

지시1 = [1. 1. 1. 0. 0.]   A v = [0. 0. 0.]
지시2 = [0. 0. 0. 1. 1.]   A v = [0. 0. 0.]

scipy 의 기저와 같은 공간인가 : True

3. 랭크와 신장나무¶

랭크를 올리는 간선을 앞에서부터 골라 가면 신장나무가 된다.

def 신장나무(A):
    """랭크를 하나씩 올리는 간선만 골라 모은다. 결과는 루프가 없는 간선 집합이다."""
    고른것 = []
    for k in range(A.shape[0]):
        후보 = 고른것 + [k]
        if np.linalg.matrix_rank(A[후보]) == len(후보):
            고른것 = 후보
    return 고른것

나무 = 신장나무(A)
남은간선 = [k for k in range(m간선) if k not in 나무]

print("나무를 이루는 간선 :", [f"e{k + 1}" for k in 나무])
print("  개수 :", len(나무), "  (n - 1 =", n노드 - 1, ")")
print("나무 밖의 간선     :", [f"e{k + 1}" for k in 남은간선])
print("  개수 :", len(남은간선), "  (m - n + 1 =", m간선 - n노드 + 1, ")")

나무를 이루는 간선 : ['e1', 'e2', 'e4']
  개수 : 3   (n - 1 = 3 )
나무 밖의 간선     : ['e3', 'e5']
  개수 : 2   (m - n + 1 = 2 )

서술 파트의 그림은 $e_1, e_3, e_4$ 를 나무로 잡았는데 여기서는 $e_1, e_2, e_4$ 가 나왔다. 간선을 고르는 순서가 다르면 나무도 달라진다. 개수는 언제나 $n - 1$ 이다.

networkx 로 정말 나무인지 확인해 보자. 루프가 없고 모든 노드가 이어져 있어야 한다.

T = nx.Graph()
T.add_nodes_from(range(n노드))
T.add_edges_from([간선[k] for k in 나무])

print("루프가 없는가 :", nx.is_forest(T))
print("모두 이어졌는가 :", nx.is_connected(T))
print("나무인가 :", nx.is_tree(T))

루프가 없는가 : True
모두 이어졌는가 : True
나무인가 : True

나무 밖의 간선을 하나 더하면 루프가 정확히 하나 생긴다.

for k in 남은간선:
    G = T.copy()
    G.add_edge(*간선[k])
    루프들 = nx.cycle_basis(G)
    print(f"e{k + 1} 을 더하면 루프 {len(루프들)}개 :",
          [[v + 1 for v in c] for c in 루프들])

e3 을 더하면 루프 1개 : [[2, 3, 1]]
e5 을 더하면 루프 1개 : [[1, 2, 3, 4]]

4. 좌영공간 — 루프¶

$A^{\mathsf{T}}\vv{y} = \vv{0}$ 은 각 노드에서 들어온 전류와 나간 전류가 같다는 뜻이다.

Y = null_space(A.T)
print(show_matrix(Y, "N(A^T) 의 기저"))
print("차원 :", Y.shape[1], "  (m - n + 1 =", m간선 - n노드 + 1, ")")

N(A^T) 의 기저
[  -0.439   -0.427 ]
[  -0.439   -0.427 ]
[  -0.111    0.698 ]
[   0.549   -0.271 ]
[  -0.549    0.271 ]
차원 : 2   (m - n + 1 = 2 )

서술 파트에서 손으로 찾은 두 루프와 비교해 보자. 루프 1은 $e_1 + e_2 - e_3$ , 루프 2는 $e_3 - e_4 + e_5$ 였다.

루프1 = np.array([1.0, 1, -1, 0, 0])
루프2 = np.array([0.0, 0, 1, -1, 1])

for 이름, y in [("루프1", 루프1), ("루프2", 루프2)]:
    print(f"{이름} = {y}   A^T y = {np.round(A.T @ y, 10) + 0.0}")

손으로 = np.column_stack([루프1, 루프2])
붙임 = np.column_stack([손으로, Y])
print()
print("손으로 찾은 것과 scipy 가 같은 공간인가 :",
      np.linalg.matrix_rank(붙임) == 2)

루프1 = [ 1.  1. -1.  0.  0.]   A^T y = [0. 0. 0. 0.]
루프2 = [ 0.  0.  1. -1.  1.]   A^T y = [0. 0. 0. 0.]

손으로 찾은 것과 scipy 가 같은 공간인가 : True

전류법칙이 정말 성립하는지 노드마다 확인해 보자.

y = 2.0 * 루프1 - 1.5 * 루프2          # 두 루프 전류를 섞은 것
print("간선 전류 y =", y)
print()
for i in range(n노드):
    들어옴 = sum(y[k] for k, (a, b) in enumerate(간선) if b == i)
    나감 = sum(y[k] for k, (a, b) in enumerate(간선) if a == i)
    print(f"  노드 {i + 1} : 들어옴 {들어옴:+.2f}, 나감 {나감:+.2f},"
          f"  차이 {들어옴 - 나감:+.2e}")

간선 전류 y = [ 2.   2.  -3.5  1.5 -1.5]

  노드 1 : 들어옴 +0.00, 나감 +0.00,  차이 +0.00e+00
  노드 2 : 들어옴 +2.00, 나감 +2.00,  차이 +0.00e+00
  노드 3 : 들어옴 -1.50, 나감 -1.50,  차이 +0.00e+00
  노드 4 : 들어옴 +0.00, 나감 +0.00,  차이 +0.00e+00

5. 오일러 공식¶

$n - m + \ell = c$ 이다. 여기서 $\ell$ 은 독립 루프의 개수, $c$ 는 연결 조각의 개수이다. 연결된 그래프면 $c = 1$ 이다. 무작위 그래프로 확인해 보자.

def 오일러검산(G):
    """노드 - 간선 + 루프 가 연결 조각의 개수와 같은지 확인한다."""
    노드목록 = list(G.nodes())
    번호 = {v: i for i, v in enumerate(노드목록)}
    A = 결합행렬([(번호[a], 번호[b]) for a, b in G.edges()], len(노드목록))

    n, m = len(노드목록), G.number_of_edges()
    r = np.linalg.matrix_rank(A) if m else 0
    루프 = m - r
    조각 = nx.number_connected_components(G)
    return n, m, r, 루프, 조각, n - m + 루프

print(f"{'n':>4}{'m':>4}{'rank':>6}{'루프':>6}{'조각':>6}{'n-m+루프':>10}   맞는가")
for _ in range(10):
    n = int(rng.integers(4, 9))
    p = float(rng.uniform(0.25, 0.7))
    G = nx.gnp_random_graph(n, p, seed=int(rng.integers(0, 10000)))
    if G.number_of_edges() == 0:
        continue
    n_i, m_i, r_i, 루프, 조각, 검산 = 오일러검산(G)
    print(f"{n_i:>4}{m_i:>4}{r_i:>6}{루프:>6}{조각:>6}{검산:>10}   {검산 == 조각}")

   n   m  rank    루프    조각    n-m+루프   맞는가
   8  10     6     4     2         2   True
   5   3     3     0     2         2   True
   4   3     3     0     1         1   True
   6  10     5     5     1         1   True
   7  14     6     8     1         1   True
   5   2     2     0     3         3   True
   5   3     3     0     2         2   True
   7   7     5     2     2         2   True
   4   4     3     1     1         1   True
   4   3     3     0     1         1   True

랭크가 $n - c$ 라는 것도 함께 확인된다. 연결 조각이 늘면 랭크가 그만큼 줄고 루프 수가 는다.

정다면체 = {
    "정사면체": nx.tetrahedral_graph(),
    "정육면체": nx.hypercube_graph(3),
    "정팔면체": nx.octahedral_graph(),
}

print(f"{'':>10}{'V':>4}{'E':>4}{'루프':>6}{'F = 루프+1':>11}{'V-E+F':>8}")
for 이름, G in 정다면체.items():
    n_i, m_i, _, 루프, _, _ = 오일러검산(G)
    F = 루프 + 1
    print(f"{이름:>10}{n_i:>4}{m_i:>4}{루프:>6}{F:>11}{n_i - m_i + F:>8}")

             V   E    루프   F = 루프+1   V-E+F
      정사면체   4   6     3          4       2
      정육면체   8  12     5          6       2
      정팔면체   6  12     7          8       2

평면에 그릴 수 있는 다면체에서는 면의 개수가 루프보다 하나 많고, 그래서 $V - E + F = 2$ 가 된다.

6. 열공간 — 전압법칙¶

$\vv{b}$ 가 전위차로 실현되려면 모든 루프에서 합이 0이어야 한다.

b_좋음 = A @ np.array([0.0, 3.0, 5.0, 2.0])       # 전위에서 만들어졌으므로 반드시 열공간 안
b_나쁨 = np.array([1.0, 1.0, 1.0, 1.0, 1.0])      # 아무렇게나 적은 값

for 이름, b in [("b_좋음", b_좋음), ("b_나쁨", b_나쁨)]:
    확장 = np.column_stack([A, b])
    안에있음 = np.linalg.matrix_rank(A) == np.linalg.matrix_rank(확장)
    print(f"{이름} = {b}")
    print(f"  C(A) 안에 있는가 : {안에있음}")
    for j, 루프 in enumerate([루프1, 루프2], 1):
        print(f"  루프 {j} 에서의 합 : {루프 @ b:+.3f}")
    print()

b_좋음 = [ 3.  2.  5.  2. -3.]
  C(A) 안에 있는가 : True
  루프 1 에서의 합 : +0.000
  루프 2 에서의 합 : +0.000

b_나쁨 = [1. 1. 1. 1. 1.]
  C(A) 안에 있는가 : False
  루프 1 에서의 합 : +1.000
  루프 2 에서의 합 : +1.000

루프를 돌아 합이 0이 아니면 그런 전위 배치는 존재하지 않는다. 이것이 키르히호프 전압법칙이다.

7. 회로 풀기 — $A^{\mathsf{T}}CA\vv{x} = \vv{f}$ ¶

간선마다 전도도를 주고, 노드 1로 전류를 넣어 노드 4로 빼 보자.

C = np.diag([1.0, 2.0, 1.0, 1.0, 3.0])       # 간선마다의 전도도
L = A.T @ C @ A

print(show_matrix(L, "A^T C A ="))
print("대칭인가 :", np.allclose(L, L.T))
print("rank     :", np.linalg.matrix_rank(L), "  (n - 1 =", n노드 - 1, ")")
print("영공간이 A 와 같은가 :",
      np.allclose(null_space(L), null_space(A)) or
      np.linalg.matrix_rank(np.column_stack([null_space(L), null_space(A)])) == 1)

A^T C A =
[   3   -1   -1   -1 ]
[  -1    3   -2    0 ]
[  -1   -2    6   -3 ]
[  -1    0   -3    4 ]
대칭인가 : True
rank     : 3   (n - 1 = 3 )
영공간이 A 와 같은가 : True

$L$ 이 특이하므로 그대로는 풀 수 없다. 노드 1을 접지해서 $x_1 = 0$ 으로 고정하면 나머지가 정해진다. 1행과 1열을 지우고 풀면 된다.

f = np.array([1.0, 0.0, 0.0, -1.0])          # 노드 1 로 1A 주입, 노드 4 로 1A 유출
print("f 의 합 :", f.sum(), " (0 이어야 풀린다)")

남은 = [1, 2, 3]                              # 노드 2, 3, 4
x = np.zeros(n노드)
x[남은] = np.linalg.solve(L[np.ix_(남은, 남은)], f[남은])

print()
print("전위 x =", x, "  (노드 1 을 0 으로 잡음)")
print("검산 A^T C A x =", L @ x, "   f =", f)
print("맞는가 :", np.allclose(L @ x, f))

f 의 합 : 0.0  (0 이어야 풀린다)

전위 x = [ 0.    -0.207 -0.31  -0.483]   (노드 1 을 0 으로 잡음)
검산 A^T C A x = [ 1.  0.  0. -1.]    f = [ 1.  0.  0. -1.]
맞는가 : True

y = C @ A @ x                                 # 옴의 법칙으로 얻은 간선 전류
print("간선 전류 y =", y)
print()
print("A^T y =", np.round(A.T @ y, 10) + 0.0, "  (= f 여야 한다)")
print()
for j, 루프 in enumerate([루프1, 루프2], 1):
    print(f"루프 {j} 의 전위차 합 : {루프 @ (A @ x):+.2e}  (전압법칙)")

간선 전류 y = [-0.207 -0.207 -0.31  -0.483 -0.517]

A^T y = [ 1.  0.  0. -1.]   (= f 여야 한다)

루프 1 의 전위차 합 : +0.00e+00  (전압법칙)
루프 2 의 전위차 합 : +0.00e+00  (전압법칙)

전류법칙과 전압법칙이 모두 성립한다. 회로 하나가 $A^{\mathsf{T}}CA\vv{x} = \vv{f}$ 라는 한 줄로 풀렸다.

마치며...¶

서술 파트의 내용	이 노트북의 코드
결합행렬	`결합행렬(간선, n노드)`
$A\vv{x}$ 는 전위차	`A @ x` 와 `x[도착] - x[출발]` 비교
$N(A)$ 의 차원 $=$ 조각 수	두 조각짜리 그래프로 확인
랭크 $=$ 신장나무	`신장나무(A)` 와 `nx.is_tree`
$N(A^{\mathsf{T}})$ 의 기저 $=$ 루프	손으로 찾은 루프와 랭크 비교
오일러 공식	`오일러검산` 과 정다면체 표
전압법칙	루프 벡터와 $\vv{b}$ 의 내적
회로 풀기	접지 후 $L$ 의 일부만 `solve`

더 해 볼 것¶

신장나무 가 간선을 뒤에서부터 고르도록 바꿔 보자. 다른 나무가 나오는가? 간선의 개수는 여전히 $n-1$ 인가?
간선의 방향을 뒤집으면 $A$ 의 그 행의 부호가 바뀐다. 네 부분공간은 달라지는가? 랭크는? 직접 뒤집어 확인해 보자.
7절에서 접지 노드를 4번으로 바꿔 풀어 보자. 전위 $\vv{x}$ 는 달라지지만 간선 전류 $\vv{y}$ 는 같은가?
$C$ 를 바꿔 가며 전류가 어떻게 갈리는지 보자. 전도도가 큰 간선으로 더 많이 흐르는가?

다음 강의에서는 지금까지를 정리한다. 행렬 하나를 받았을 때 무엇부터 확인해야 하는지를 절차로 만들어 둔다.

Lecture 12. 그래프와 네트워크 — 파이썬 실습