Lecture 12. 그래프와 네트워크, 결합행렬

L5부터 L11까지 우리는 부분공간이라는 언어를 만들었다. 열공간, 영공간, 행공간, 좌영공간을 정의하고 차원을 세고 기저를 구했다. 그런데 이 넷은 대체로 추상적이었다.

이번 강의에서는 그것들이 한꺼번에 착지하는 예를 본다. 전기 회로 하나를 행렬로 옮겨 놓으면 네 부분공간이 전부 물리적인 뜻을 갖는다. 영공간은 전위의 기준점이 되고, 좌영공간은 키르히호프 전류법칙이 되며, 랭크는 그래프의 나무가 된다. 그리고 오일러가 다면체를 세며 발견한 공식이 차원 정리에서 그대로 나온다.

1. 결합행렬 (Incidence matrix)¶

점(노드)과 그 사이를 잇는 선(간선)으로 이루어진 것을 그래프라 한다. L11에서는 연결 여부만 1과 0으로 적은 인접행렬을 썼는데, 이번에는 다른 행렬을 쓴다.

행이 간선이고 열이 노드이다. L11의 인접행렬은 $n \times n$ 이었으므로 완전히 다른 행렬이다.

방향은 아무렇게나 정해도 된다. 방향을 뒤집으면 그 행의 부호가 통째로 바뀔 뿐이고, 행이 만드는 공간은 달라지지 않는다.

$A\vv{x}$ 는 무엇인가¶

$\vv{x}$ 의 각 성분을 노드의 전위라고 하자. $k$ 번째 행은 $-\vv{e}_i^{\mathsf{T}} + \vv{e}_j^{\mathsf{T}}$ 이므로

이다. 즉 $A\vv{x}$ 의 각 성분은 그 간선 양 끝의 전위차이다. 노드에 붙은 값을 간선에 붙은 값으로 옮겨 주는 행렬인 셈이다.

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

$A\vv{x} = \vv{0}$ 은 무슨 뜻인가. (1)에 의해 모든 간선에서 $x_j = x_i$ 라는 뜻이다. 즉 이어진 두 노드의 전위가 같다.

그래프가 연결되어 있다면 어떤 두 노드도 간선을 따라 이어지므로, 그 길을 따라가며 값이 계속 같아진다. 따라서 모든 노드의 전위가 같다.

물리적으로 읽으면 이렇다. 전위는 절댓값이 아니라 차이만 뜻이 있다. 모든 노드의 전위를 똑같이 5만큼 올려도 간선의 전위차는 그대로이고, 따라서 전류도 그대로이다. 회로에서 접지점을 어디로 잡아도 상관없는 이유가 이것이고, 그 자유도가 영공간의 차원 1로 나타난다.

3. 랭크와 신장나무¶

연결된 그래프에서 $\dim N(A) = 1$ 이므로, L7의 $\dim N(A) = n - r$ 에서 랭크가 바로 나온다.

$A$ 의 행이 간선이므로 행공간의 기저는 독립인 간선 $n-1$ 개이다. 그 간선들이 어떤 모양인지 보자.

루프가 있으면 종속이다¶

간선들이 루프를 이룬다고 하자. 루프를 따라 한 바퀴 돌면서 방향이 맞는 간선에는 +1, 반대인 간선에는 -1 을 주어 더해 보자. 각 행이 $\vv{e}_{\text{머리}}^{\mathsf{T}} - \vv{e}_{\text{꼬리}}^{\mathsf{T}}$ 이고 루프에서는 각 노드가 한 번 들어오고 한 번 나가므로, 모든 항이 상쇄되어

이 된다. 루프를 이루는 간선들의 행은 종속이다.

루프가 없으면 독립이다¶

거꾸로 간선 집합에 루프가 없다고 하자. 루프가 없는 그래프를 숲이라 하는데, 이때는 간선을 하나씩 놓아 가되 놓을 때마다 새 노드가 하나씩 붙도록 순서를 정할 수 있다. 이미 있는 노드끼리 잇는 간선을 놓으면 그 순간 루프가 생기기 때문이다.

그러면 각 간선의 행에는 그때 새로 붙은 노드의 열에 $\pm1$ 이 있고, 그 열은 앞서 놓인 행들에서 모두 0이다. 따라서 행들의 결합이 영벡터라면 그 열을 보아 계수가 0이어야 하고, 이것이 모든 간선에 대해 성립하므로 독립이다.

노드 $n$ 개를 모두 잇는 루프 없는 간선 집합을 신장나무(spanning tree)라 한다. (3)에 의해 그 간선의 개수는 정확히 $n - 1$ 이다.

4. 좌영공간 — 키르히호프 전류법칙¶

이제 $A^{\mathsf{T}}\vv{y} = \vv{0}$ 을 보자. $\vv{y}$ 의 각 성분을 그 간선에 흐르는 전류라고 하자.

$A^{\mathsf{T}}$ 의 $i$ 번째 행은 $A$ 의 $i$ 번째 열이고, 그 열에는 노드 $i$ 로 들어오는 간선에 +1, 나가는 간선에 -1 이 들어 있다. 따라서

이고, 이것이 0이라는 것은 각 노드에서 들어온 전류와 나간 전류가 같다는 뜻이다. 키르히호프 전류법칙이 그대로 $A^{\mathsf{T}}\vv{y} = \vv{0}$ 이다.

기저는 루프이다¶

이 방정식의 해는 무엇인가. 루프를 하나 잡아 그 위로만 전류를 흘려 보자. 루프를 따라 도는 전류는 각 노드에서 하나로 들어와 하나로 나가므로 (5)의 조건을 자동으로 만족한다. (4)에서 이미 확인한 사실이다.

차원은 L10의 결과에서 바로 나온다.

Figure 2에서 본 것과 맞는다. 신장나무가 $n-1$ 개의 간선을 쓰고 남은 간선이 $m - n + 1$ 개인데, 그 하나하나가 루프를 하나씩 만들었다. 그 두 루프를 벡터로 적으면 다음과 같다.

$\vv{y}_1$ 은 $e_1 + e_2 - e_3$ 이고 $\vv{y}_2$ 는 $e_3 - e_4 + e_5$ 이다. $e_3$ 의 부호가 반대인 것은 루프를 도는 방향과 간선의 방향이 어긋나기 때문이다.

신장나무를 어떻게 잡느냐에 따라 루프의 모양은 달라진다. 하지만 개수는 언제나 $m - n + 1$ 이고 만들어지는 공간도 같다.

오일러 공식¶

(6)의 식을 옮겨 쓰면 다음이 된다. 독립 루프의 개수를 $\ell$ 이라 하자.

즉 (노드) − (간선) + (루프) = 1 이다. 평면에 그릴 수 있는 그래프라면 루프 하나가 면 하나에 대응하고 바깥쪽 면이 하나 더 있으므로 면의 개수는 $F = \ell + 1$ 이다. 이것을 넣으면

가 되어 흔히 쓰는 $V - E + F = 2$ 가 나온다.

Figure 1의 그래프로 확인하면 $n = 4$, $m = 5$, $\ell = 5 - 4 + 1 = 2$ 이고 $4 - 5 + 2 = 1$ 이다.

조각이 $c$ 개면 $r = n - c$ 이므로 $\ell = m - n + c$ 가 되고, 오일러 공식은 $n - m + \ell = c$ 로 바뀐다. 오른쪽의 1이 조각의 개수였던 것이다.

5. 열공간 — 키르히호프 전압법칙¶

마지막 공간이다. $C(A)$ 는 $A\vv{x}$ 로 만들어지는 것들의 집합이므로, (1)에 의해 실제로 어떤 전위 배치에서 나올 수 있는 전위차의 모임이다.

간선마다 아무 숫자나 적어 놓는다고 그것이 전위차가 되지는 않는다. 어떤 조건이 필요한가.

L8에서 답을 이미 얻었다. $\vv{b} \in C(A)$ 일 조건은 $\vv{y}^{\mathsf{T}}A = \vv{0}$ 인 모든 $\vv{y}$ 에 대해 $\vv{y}^{\mathsf{T}}\vv{b} = 0$ 이라는 것이었다. 그런데 그런 $\vv{y}$ 들이 바로 4절의 루프이다. 그러므로 조건은 다음과 같다.

루프를 한 바퀴 돌면 전위차의 합이 0이어야 한다. 키르히호프 전압법칙이다. 출발한 곳으로 돌아왔으니 전위가 제자리여야 한다는 당연한 이야기이고, 그것이 열공간의 조건으로 나타난다.

차원은 $\dim C(A) = r = n - 1$ 이다.

정리하면 네 부분공간이 모두 물리적인 뜻을 갖는다.

6. $A^{\mathsf{T}}CA$ 와 그래프 라플라시안¶

회로를 끝까지 풀려면 옴의 법칙이 필요하다. 간선 $k$ 의 전도도를 $c_k$ 라 하면 전류는 전위차에 비례한다.

여기서 $C$ 는 $c_k$ 를 대각에 놓은 대각행렬이다. 이것을 전류법칙에 넣되, 바깥에서 노드로 흘려 넣는 전류 $\vv{f}$ 가 있다고 하면

가 된다. 회로 전체가 이 한 줄로 정리된다.

이 행렬은 대칭이다. L5의 (8)의 성질을 두 번 쓰고, 대각행렬은 전치해도 그대로라는 것을 쓰면 된다.

L5에서 $R^{\mathsf{T}}R$ 이 언제나 대칭이라고 한 것이 여기서 처음으로 쓰인다.

라플라시안의 성분¶

$C = I$ 인 경우, 즉 모든 간선의 전도도가 1인 경우를 보자. L5의 (15)에서 $(A^{\mathsf{T}}A)_{ij}$ 가 $A$ 의 $i$ 열과 $j$ 열의 내적이라고 했다.

$i = j$ 이면 $i$ 열의 성분 제곱의 합인데, 각 성분은 노드 $i$ 에 닿는 간선에서만 $\pm1$ 이므로 제곱하면 1이다. 따라서 대각 성분은 그 노드에 닿는 간선의 개수, 즉 차수이다.

$i \neq j$ 이면 두 열의 같은 자리가 모두 0이 아닌 경우만 남는데, 그것은 그 간선이 $i$ 와 $j$ 를 잇는 경우이다. 그때 한쪽은 -1 이고 다른 쪽은 +1 이므로 곱은 -1 이다.

이 행렬을 그래프 라플라시안(graph Laplacian)이라 한다.

이 행렬도 특이하다. $A\vv{x} = \vv{0}$ 이면 당연히 $A^{\mathsf{T}}A\vv{x} = \vv{0}$ 이고, 거꾸로 $A^{\mathsf{T}}A\vv{x} = \vv{0}$ 이면 양변에 $\vv{x}^{\mathsf{T}}$ 를 곱해

이 되는데, 이것은 $A\vv{x}$ 의 성분 제곱의 합이므로 $A\vv{x} = \vv{0}$ 이다. 두 영공간이 같다.

그러므로 라플라시안의 영공간도 상수 벡터가 만드는 직선이고, 회로 방정식 (12)의 해도 상수만큼의 자유도를 갖는다. 접지점을 하나 정해 주면 그 자유도가 사라진다.

마치며...¶

이번 강의에서 네 부분공간이 전부 물리적인 뜻을 갖는 예를 보았다.

추상적으로만 보이던 개념들이 회로 하나에서 모두 착지했다. 특히 오일러가 다면체를 세며 발견한 공식이 사실은 $\dim N(A^{\mathsf{T}}) = m - r$ 이라는 차원 정리였다는 것이 이 강의에서 가장 눈에 띄는 결과이다.

여기까지가 부분공간에 대한 이야기이다. 다음 강의에서는 잠시 멈춰, 행렬 하나를 마주쳤을 때 무엇부터 확인해야 하는지를 절차로 정리한다. 그다음부터는 지금까지 한 번도 쓰지 않은 개념을 들여온다. 길이와 각도이다.

이번 강의의 내용을 파이썬으로 확인해 보려면 L12 실습 노트북으로 넘어가면 된다. 간선을 하나씩 더해 가며 랭크와 루프 수가 어떻게 변하는지 보고, 오일러 공식이 언제나 성립하는지 무작위 그래프로 확인할 수 있다.