Lecture 12: Graphs, networks, incidence matrices

 

Graph, Nodes, Edges

 

그림1

 

그래프 (Graph)는 꼭짓점 (node)와 변 (edge)로 이루어져 있습니다. 

 

위와 같이 방향이 있는 edge로 구성된 그래프를 directed graph라고 합니다.

 

Node가 4개 (n=4), Edge가 5개 (m=5)

 

 

근접행렬 (Incidence Matrix)

 

위의 그래프를 토대로 node의 개수 n을 column으로, edge의 개수 m을 row로 하여 5 by 4 근접행렬을 만들 수 있습니다.

 

edge가 방향을 가지고 있기 때문에 원소들에 나타내야합니다.

 

출발점을 -1, 끝점을 1로 지정합니다.

 

  node1  node2 node3 node4

A = $\begin{bmatrix} 
-1 & 1 &0 &0 \\
0 & -1 & 1 &0 \\  
-1 & 0 & 1 & 0\\  
-1 & 0 & 0 & 1\\  
0 & 0 &-1  &1  
\end{bmatrix}$

 

node 1은 node2와 node3로 각각 연결되어 있습니다.

 

node 2는 node 3와 연결되어 있습니다.

 

node들이 연결되어 있는 부분 그래프 (subgraph)를 Loop라고 합니다. 

 

 

Loop

 

위의 그래프의 예에서 Loop는 다음과 같습니다. 

 

edge 1,2,3이 loop 1

 

edge 3,4,5가 loop 2

 

edge 1,2,4,5가 loop 3

 

loop1은 근접 행렬 A의 row 1, 2, 3입니다. 

 

이 loop의 row는 row1과 row2를 더하면 row3가 나오기 때문에 종속입니다. 

 

즉, loop에 속하는 근접행렬의 row는 선형종속입니다.

 

 

전위차 (Potential Difference)

 

인접 행렬의 크기가 커지면 많은 0을 가지게 될 것입니다.

 

즉, 희소 (sparse)한 원소를 가지게 되는데, 이러한 행렬을 희소 행렬 (sparse matrix)라고 합니다. 

 

희소 행렬의 구조를 찾는 방법으로 근접행렬의 null space를 찾는 것이 있습니다.

 

null space는 node를 나타내는 column 벡터들의 독립 여부를 알려줍니다.

 

$A\mathbf{x} = \begin{bmatrix} 
-1 & 1 &0 &0 \\  
0 & -1 & 1 &0 \\  
-1 & 0 & 1 & 0\\  
-1 & 0 & 0 & 1\\  
0 & 0 &-1  &1  
\end{bmatrix}\begin{bmatrix} 
x_{1}\\x_{2}  
\\x_{3}  
\\x_{4}  
\end{bmatrix} = \begin{bmatrix} 
x_{2} - x_{1}\\x_{3} - x_{2}  
\\x_{3} - x_{1}  
\\x_{4} - x_{1} \\ 
x_{4} - x_{3}\end{bmatrix} = \begin{bmatrix} 
0\\0  
\\0  
\\0  
\\ 0 
\end{bmatrix}$

 

전자회로의 관점에서 생각해보면 벡터 x는 

 

$\begin{bmatrix} 
x_{1}\\x_{2}  
\\x_{3}  
\\x_{4}  
\end{bmatrix} $

 

각 node에서의 전압 (potentials)입니다.

 

행렬 A를 곱하면 각 node들의 전위차 (potential differences)를 계산할 수 있습니다.

 

$\begin{bmatrix} 
x_{2} - x_{1}\\x_{3} - x_{2}  
\\x_{3} - x_{1}  
\\x_{4} - x_{1} \\ 
x_{4} - x_{3}\end{bmatrix}$

 

모든 node들의 전위차가 0이 되는지 찾습니다. 전류가 흐르지 않는 0은 관심대상이 아닙니다. 

 

즉, 전류가 흐를 때 null space를 구해야합니다. 

 

근접 행렬 A는 column을 다 더하면 0이됩니다.

 

즉, $\mathbf{x} = c\begin{bmatrix} 
1\\1  
\\1  
\\1  
\end{bmatrix}$입니다. 

 

null space는 4차원 공간상에 존재하는 1차원의 line입니다. 

 

기저는 1개 뿐이므로 차원은 1입니다. (dim N(A) = 1)

 

null space에 의해 상수 c를 설정하면 모든 노드의 전압이 한 번에 동일하게 설정되어 전위차가 없습니다. 

 

전위차가 없으면 어떠한 전류의 흐름도 일어나지 않습니다. 따라서 전위차를 만들어 주기 위해 node 중 하나를 ground로 설정합니다.

 

$x_{4} = 0$를 ground로 설정합니다.

 

$A\mathbf{x} = x_{1}\begin{bmatrix} 
-1\\ 0 
\\-1  
\\-1  
\\0 
\end{bmatrix} + x_{2}\begin{bmatrix} 
1\\ -1 
\\0  
\\0  
\\0 
\end{bmatrix} + x_{3}\begin{bmatrix} 
0\\ 1 
\\1 
\\0  
\\-1 
\end{bmatrix} + 0\begin{bmatrix} 
0\\ 0 
\\0  
\\1 
\\1 
\end{bmatrix}$

 

node 중 하나를 0으로 만드는 것은 전압(potential)을 0으로 한다는 뜻입니다. 

 

이제 나머지 node에 대해 해를 구하면 됩니다. 

 

예시에서 하나의 node를 ground로 만들고 나머지 3개의 node를 이용해 해를 구하는 것은 근접 행렬의 rank가 3이기 떄문입니다. 

 

dim N(A) = n - r 상기하면 4 - r = 1로부터 r이 3임을 알 수 있습니다. 

 

 

Kirchoff's Current Law

 

$A^{T}$의 null space를 구해보겠습니다.

 

$A^{T}\mathbf{y} = \begin{bmatrix} 
-1 & 0 & -1 &-1  &0 \\  
1 & -1 & 0 & 0 &0 \\  
0 & 1 & 1 & 0 &-1 \\  
0 & 0 & 0 & 0 & 1 
\end{bmatrix}\begin{bmatrix} 
y_{1}\\y_{2}  
\\y_{3}  
\\y_{4}  
\\ y_{5} 
\end{bmatrix} = \begin{bmatrix} 
0\\0  
\\0  
\\0 
\end{bmatrix}$

 

$dim N(A^{T})$ = m -r 이고 m=5, r=3이니 Left null space의 차원은 2입니다. 

 

Left null space가 의미하는 것은 키르히호프의 전기회로 법칙입니다. 

 

키르히호프의 전기회로 1법칙은 전류가 흐르는 길에서 들어오는 전류와 나가는 전류의 합이 같다입니다. 

 

Left null space $N(A^{T})$

 

$A^{T}\mathbf{y} = 0  $

 

-> $\begin{bmatrix} 
-1 & 0 & -1 &-1  &0\\  
1 &-1  & 0 & 0 & 0\\  
0 & 1 &1  &0  &-1 \\  
0 & 0 & 0 & 1 & 1 
\end{bmatrix}\begin{bmatrix} 
y_{1}\\y_{2}  
\\y_{3}  
\\y_{4}  
\\ y_{5} 
\end{bmatrix}$

 

$\begin{bmatrix} 
-y_{1}-y_{3}-y_{4}\\  
y_{1}-y_{2}\\y_{2}+y_{3}-y_{5}  
\\y_{4}+y_{5} 
\end{bmatrix} 
= \begin{bmatrix} 
0\\0  
\\0  
\\0  
\end{bmatrix}$

 

$-y_{1}-y_{3}-y_{4}=0$에서 마이너스는 node에서 전류가 흘러나가는 것을 의미합니다. 

 

즉, edge 1, 3, 4를 의미합니다. 

 

row1이 의미하는 것은 node1에서 흘러나간 전류의 총합은 0이란 뜻입니다. 

 

Left null space의 기저를 구할 때는 loop를 사용할 수 있습니다.

 

Left null space의 차원이 2이미므로 기저는 두 개의 special solution 입니다. 

 

loop 1을 기준으로 하곘습니다. 

 

$y_{1}$을 1로 하면 $y_{2}$도 1이고 $y_{3}$는 -1입니다. 나가는 전류를 1로 설정하였기 떄문에 들어오는 전류는 -1이 됩니다. 

 

loop 1이 기준이기 때문에 $y_{4}$와 $y_{5}$는 0이됩니다. 

 

따라서 첫 번째 special solution은 $\mathbf{y} = \begin{bmatrix} 
1\\1  
\\-1  
\\0  
\\0 
\end{bmatrix}$입니다.

 

두 번째 spcial solution은 loop 2 기준으로 구해줍니다.

 

$\mathbf{y} = \begin{bmatrix} 
0\\0  
\\1  
\\-1  
\\1 
\end{bmatrix}$

 

위 두 개의 special solution이 left null space의 기저입니다. 

 

처음에 loop는 3개가 있었습니다. loop 3는 기저가 될 수 있는지 살펴보겠습니다.

 

$\mathbf{y} = \begin{bmatrix} 
1\\1  
\\0  
\\-1  
\\1 
\end{bmatrix}$

 

앞의 두 special solution을 더하면 이 결과가 나오기 때문에 종속입니다. 

 

 

전자회로에 대한 그래프 모델

 

그림2

 

이전에 배웠던 4개의 주요 부분 공간이 전자회로의 그래프 모델에서 찾고자 하는 것과 일치합니다. 

 

 

Tree : No Loop

 

Row space를 살펴보면 pivot column은 col1, col2, col4 입니다.

 

독립인 column edge만 연결하면 loop가 생성되지 않게 됩니다.

 

loop가 없는 그래프를 Tree라 합니다.

 

 

결론

 

node, edge, loop의 관계는 다음과 같습니다.

 

# loops = # edges - (# nodes - 1)

 

$dim N(A^{T})$ = m - r

 

nodes -1은 rank를 의미합니다. 

 

이 공식을 다르게 쓰면 오일러의 공식이 됩니다.

 

# nodes - # edges + # loops = 1