12. Graphs, Networks, Incidence Matrices

 

 

여기서 배우는 그래프는 객체들의 관계를 나타내는 구조를 말합니다.

 

 

 

위의 사진을 보면 그래프는 노드(node)와 엣지(edge)로 이루어져 있습니다. 방향을 가지는 엣지는 directed graph 방향이 없으면 undirected graph라고 합니다. 방향이 있는 경우 -, +를 표현할 수 있습니다.

 

 

- 노드는 사진에서 동그란 원 입니다.

 

 

그리고 그래프의 연결을 행렬로 표현할 수 있습니다. 위 사진을 표현하면 node = 4, edge = 5 이므로 $5\times 4$ 형태의 행태인 행렬이 만들어집니다. edge가 column에 들어가는 방향인지 나오는 방향인지에 따라서 원소 부호가 정해지게 됩니다.

 

 

사진을 보면 노드들끼리 연결된 화살표들이 존재하는데 이런 연결 관계를 행렬로 표현할 수 있습니다. 연결 관계에 대한 행렬을 Incidence matrix라고 합니다.

 

 

 

루프는 총 3개가 있습니다. 

1. Loop1 : edge1, edge2, edge3
2. Loop2 : edge3, edge4, edge5
3. Loop3 : edge1, edge2, edge4, edge5

 

간단하게 생각하면 해당 그래프에서 만들어지는 도형의 개수만큼 루프가 만들어진다고 생각하면 됩니다. 지금은 삼각형 2개 평행사변형 1개가 만들어지니 총 3개의 루프가 나오게 됩니다.

 

 

여기서 엣지들이 모여 만든 삼각형들은 사각형안에 존재하고 있습니다. 두 삼각형 루프의 Incidence matrix는 사각형 루프 Incidence matrix의 subspace가 됩니다. 그리고 루프에 속하는 엣지들은 서로 선형종속입니다.

 

 

 

 

 

각 성분들은 엣지가 노드에 연결되어 있으면 1 그리고 들어가는 방향이면 + 나가는 방향이면 - 가 됩니다. 각 노드로 들어가고 나가는 엣지는 1개만 존재하므로 row 당 2개의 원소만 가질 수 있습니다. 그래서 크기가 커지면 희소 행렬이 됩니다.

 

 

- 희소 행렬 내부 구조를 분석하는 방법으로 null space를 찾는 방법이 있는데 이것을 통해 column에 해당하는 노드가 독립인지 아닌지 알 수 있습니다.

 

 

위에 행렬을 완성시킨 후 null space를 구해보겠습니다.

 

 

$Ax=\left[\begin{array}{cccc}-1& 1& 0& 0\\ 0& -1& 1& 0\\ -1& 0& 1& 0\\ -1& 0& 0& 1\\ 0& 0& -1& 1\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]=\left[\begin{array}{c}{x}_2-x_1\\ x_3-x_2\\ x_3-x_1\\ x_4-x_3\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right]$

 

 

조금 더 자세히 알아보기 위해서 전자 회로를 예시로 들어보겠습니다. 노드들을 전자 회로에서 전압을 측정하는 지점이라고 하고 $Ax=0$에서 x벡터의 원소들을 각 노드에서의 전압이라고 한다면

 

 

- $Ax$을 통해 노드 간의 전위차를 계산할 수 있습니다.

- null space는 전위차가 모두 0인 경우입니다. 

 

 

영벡터인 경우도 null space에 해당하지만 A의 각 column들을 보면 -1, 1이 하나씩만 존재해서 전부 다 더하면 0이 나온다는 것을 알 수 있습니다.

 

 

• 3개의 column은 독립이지만 마지막 column이 종속입니다.

 

 

$Ax=0$

$x=c\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]$

- dim N(A) = 1

 

 

node는 전압을 측정하는 장소이고 x는 전압이라고 했었습니다. ground는 어떤 의미를 가질까요?

node들 중 하나를 ground라고 설정하겠습니다. 그러면 이 node에서 측정되는 x는 0이 되게 됩니다.

 

마지막 노드를 ground로 설정해보겠습니다.

 

$Ax=x_1\left[\begin{array}{c}-1\\ 0\\ -1\\ -1\\ 0\end{array}\right]+x_2\left[\begin{array}{c}1\\ -1\\ 0\\ 0\\ 0\end{array}\right]+x_3\left[\begin{array}{c}0\\ 1\\ 1\\ 0\\ -1\end{array}\right]+0\left[\begin{array}{c}0\\ 0\\ 0\\ 1\\ 1\end{array}\right]$

 

- 하나만 ground로 설정하는 이유는 Incidence matrix의 rank가 3이기 때문입니다.

 

 

Null space of $A^T$

 

이번에는 $A^T$의 null space를 구해보겠습니다. 이 부분은 키르히호프의 전류 법칙과 관련이 있습니다.

left null space는 $m\times n$의 경우 $m-rank$로 알 수 있기 때문에 $5-3=2$즉 $A^T$를 소거했을 때 free column이 2개가 나온다는 것을 알 수 있습니다. (left null space은 rank 2)

 

- rank의 경우 $A^T$와 A가 같습니다.

 

$A^{T}y=\left[\begin{array}{ccccc}-1& 0& -1& -1& 0\\ 1& -1& 0& 0& 0\\ 0& 1& 1& 0& -1\\ 0& 0& 0& 1& 1\end{array}\right]\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\\ y_5\end{array}\right]=\left[\begin{array}{c}-y_1-y_3-y_4\\ y_1-y_2\\ y_2+y_3-y_5\\ y_4+y_5\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right]$

 

 

부호로 전류의 방향을 알 수 있습니다. node1에서는 edge1, edge3, edge4에서 다른 곳으로 전류가 나가는 것을 알 수 있습니다.

 

 

그리고 $y_1-y_2=0$을 보고 $y_1=y_2$, $y_2+y_3=5$을 통해서 node2, node3에서 들어오는 전류와 나가는 전류가 같은 것을 알 수 있습니다. (키르히호프의 전류 법칙)

 

 

 

 

left null space의 기저는 

 

$\left[\begin{array}{c}1\\ 1\\ -1\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 0\\ 1\\ -1\\ 1\end{array}\right]$

 

left null space의 해는

 

$\left[\begin{array}{c}1\\ 1\\ 0\\ -1\\ 1\end{array}\right]$이 나오게 됩니다.

 

 

- 이해하기 쉽게 해준다며 전자회로 내용으로 들어갔는데 오히려 이해하기가 더 힘들어진거 같습니다;;