학습목표
- Graph and Networks
- Insidence Matrices
- Kirchhoff’s Laws
- Graph: Nodes, Edges
- nodes \(n = 4\)
- edges \(m = 5\)
- node 1 \(\to\) node 2
- node 1 \(\to\) node 3
- node 1 \(\to\) node 4
- node 2 \(\to\) node 3
- node 3 \(\to\) node 4
directed graph: 방향이 있는 edge로 구성된 그래프
undirected graph: 방향이 없는 edge로 구성된 그래프
- Incidence Matrix 근접행렬
\(A = \begin{bmatrix} -1 & 1 & 0 & 0 & \text{Edge 1} \\ 0 & -1& 1 & 0 & \text{Edge 2}\\ -1 & 0 & 1 & 0 & \text{Edge 3}\\ -1 & 0 & 0 & 1 & \text{Edge 4}\\ 0 & 0 & -1& 1 & \text{Edge 5}\end{bmatrix}\)
- 각 행을 노드 번호로, 각 열은 엣지로 봤을때, 노드 1 -> 노드 2라면 1행 1열에서 1이 나가서(-1, 출발) 1행 2열로 1이 들어오는(1, 도착)방식
loop루프 : 노드들이 연결되어져 있는 부분 그래프 subgraph(노드 간 엣지로 연결된 후 나오는 중복되지 않는 부분의 삼각형 또는 부분면적이라 보기도 함)
- \(\star\) 여기서 Edge 1, Edge 2, Edge 3 은 Edge 1+ Edge 2 = Edge 3의 linear dependent선형 종속 관계를 갖는 loop라고 할 수 있다.
- loop 1(Edge 1, Edge 2, Edge 3)의 row는 dependent(종속)하다.
- 행마다 0이 2개
- Potential difference and null space of A A의 0공간과 전위차(전자 회로 관점에서 해석)
위처럼 incidence matrix 근접행렬을 구하면 행렬은 엣지당 0을 두 개씩 가지게 된다. 근데, 행렬이 커진다면, 0이 행마다 2개씩 존재하여 행렬의 대부붑이 0이라는 원소를 가지게 되는 sparse matrix, 희소행렬 이 된다.
- 희소행렬이고, 행 및 열으로 그래프 형태를 추측할 수 있다면 실제 문제를 linear algebra 적으로 행렬에 의해 분석할 수 있는 가능성이 있고, 그 방법 중 하나가 incidence matrix 에서 null space 찾는 것.
- 만약, column끼리 독립이면, x 행렬은 0행렬만이 존재할 것.
- 만약, column끼리 독립이 아니라면, 종속이라면 null space를 만드는 공간의 집합이 나올 것.
\(Ax = 0\)
\(Ax = \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}\)
이렇게 표현한게 potental difference
- 전기로 해석하자면, x가 모두 0이면(해가 없으면) 전기가 흐르지 않는 것과 같음
edge 는 -1또는 1 하나랑 0 두개를 가진 행이므로, 합은 꼭 0이다.
- 결국 0공간의 해는 아래와 같다.
\(x = c \begin{bmatrix} 1 \\1\\1\\1 \end{bmatrix}\)
- \(\begin{bmatrix} 1 \\1\\1\\1 \end{bmatrix}\) basis of nullspace
하지만 위는 상수 c에 따라 \(x_1,x_2,x_3,x4\)가 같은 값을 가지게 된다는 말이 된다 (전위차가 없다는 말이 된다.)
- 전위차를 만들기 위해서 ground 개념 등장
- 하나의 노드를 그라운드로 설정하고(\(x_n\)중 하나) 나머자의 해를 구하는 것이다.
- 전위차가 있다는 말이 전기가 흐른다느 말과 같음
dimension of null space = dim N(A) = n-r = 1, n = 4 , therefore r(rank) = 3 and \(x_1,x_2,x3\) are independent
- Kirchoff’s current law and null space of A transpose
\(A^T y = \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}0\\0\\0\\0\\0 \end{bmatrix}\)
dimension of left null space = dim \(N(A^T) = m-r = 2, m=5, r=3\)
\(-y_1 - y_3 -y_4 = 0\)
\(y_1 - y_2 = 0\)
\(y_2 + y_3 -y_5 = 0\)
\(y_3 +y_5 = 0\)
키르히르프 법칙 = 전기는 들어온만큼 나간다.
\(y\)의 해 \(\begin{bmatrix} 1 \\1\\-1\\0\\1\end{bmatrix} , \begin{bmatrix}0\\0\\1\\-1\\1 \end{bmatrix}\)
위에서 독립인 edge는 \(x_1 \to x_4, x_1 \to x_2, x_2 \to x_3\) -> loop 가 없는(선 그엇을때 삼각형의 모양이 안 나오는)형태가 된다.
- 이를 Tree라고 한다.
-
#loops = #edges - (#nodes-1)
- 여기서 1은 rank
#nodes - #edges + #loops -1
- 이는 위처럼 오일러 공식으로 설명 가능
- Step
\(x\) = potential at nodes
\(e = Ax\) = potential difference
\(y = Ce\)
- \(y = CAx\)
\(A^Ty = 0\)
- \(A^TCAx = 0\)