https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/
그래프는 노드와 엣지들의 집합이다.
Graph={nodes, edges}
예시로 다음과 같은 directed 그래프가 있다고 해보자.
위 그래프는 4개의 노드와 5개의 엣지를 갖는다.
그리고 이를 Incidence Matrix(근접 행렬)로 표현하면 다음과 같다. (row는 edge를 의미하고, column은 node를 의미한다. -1에서 출발하여 1로 도달한다는 의미이다.)
A=⎣⎢⎢⎢⎢⎢⎡−10−1−101−10000110−100011⎦⎥⎥⎥⎥⎥⎤
여기서 edge1, edge2, edge3만 있다고 가정해보자.
⎣⎢⎡−10−11−10011000⎦⎥⎤
위 행렬만 보고 해당 그래프가 loop를 만들 수 있는지 판단할 수 있을까?
정답은 yes이다. 왜냐하면 row1+row2=row3로 dependent이기 때문에 이는 loop를 만들 수 있다.
그러면 계속해서 N(A)를 찾아보자.
Ax=0=⎣⎢⎢⎢⎢⎢⎡−10−1−101−10000110−100011⎦⎥⎥⎥⎥⎥⎤⎣⎢⎢⎢⎡x1x2x3x4⎦⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎢⎡−x1+x2−x2+x3−x1+x3−x1+x4−x3+x4⎦⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎢⎡00000⎦⎥⎥⎥⎥⎥⎤
그리고 이를 만족하는 벡터 x 예시를 하나 들어보자.
x=⎣⎢⎢⎢⎡1111⎦⎥⎥⎥⎤
위 벡터 x는 null space의 벡터로 볼 수 있다. 그래서 정리하면,
N(A)=c⎣⎢⎢⎢⎡1111⎦⎥⎥⎥⎤
basis of N(A)=⎣⎢⎢⎢⎡1111⎦⎥⎥⎥⎤
위와 같이 나올 것이다.
따라서 N(A)의 차원은 dim(N(A))=1이라는 것을 알 수 있다.
그리고 A의 랭크는 Rank(A)=n−dim(N(A))=4−1=3이라는 것을 알 수 있다.
그렇다면 dim(N(AT))는 어떨까?
지난번 강의에서 배웠던 공식대로 한다면 dim(N(AT))=m−r=5−3=2가 나올 것이다.
ATy=⎣⎢⎢⎢⎡−11000−110−1010−100100−11⎦⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎡y1y2y3y4y5⎦⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎡−y1−y3−y4y1−y2y2+y3−y5y4+y5⎦⎥⎥⎥⎤=⎣⎢⎢⎢⎡0000⎦⎥⎥⎥⎤
그리고 위 행렬을 아까의 그래프와 비교해서 보자.
- row1=[−y1−y3−y4]는 1번 노드에 대해서 balance가 잡힌 엣지 벡터라는 것을 보여준다.
- row2=[y1−y2]는 2번 노드에 대해서 balance가 잡힌 엣지 벡터라는 것을 보여준다.
- row3=[y2+y3−y5]는 3번 노드에 대해서 balance가 잡힌 엣지 벡터라는 것을 보여준다.
- row4=[y4+y5]는 4번 노드에 대해서 balance가 잡힌 엣지 벡터라는 것을 보여준다.
그렇다면 N(AT)의 basis를 구해보자. 우리는 Elimination을 적용해서 basis를 구하는 방법을 배웠다.
하지만 그래프만 보고도 N(AT)의 basis를 직관적으로 구할 수 있다.
위 그래프에서 최소 크기로 loop를 이루는 벡터 y를 구해보자.
⎣⎢⎢⎢⎢⎢⎡11−100⎦⎥⎥⎥⎥⎥⎤,⎣⎢⎢⎢⎢⎢⎡001−11⎦⎥⎥⎥⎥⎥⎤
그리고 위 벡터들이 N(AT)의 basis가 된다.
basis for N(AT)=⎣⎢⎢⎢⎢⎢⎡11−100⎦⎥⎥⎥⎥⎥⎤,⎣⎢⎢⎢⎢⎢⎡001−11⎦⎥⎥⎥⎥⎥⎤
그리고 위 그래프에서 가장 큰 loop 1->2->3->4->1은 다음과 같이 basis의 조합으로 표현이 가능하다.
big loop (1->2->3->4->1)=⎣⎢⎢⎢⎢⎢⎡110−11⎦⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎢⎡11−100⎦⎥⎥⎥⎥⎥⎤+⎣⎢⎢⎢⎢⎢⎡001−11⎦⎥⎥⎥⎥⎥⎤
즉, 그래프에서 작은 loop들의 조합으로 큰 loop를 구성할 수 있다.
그리고 별개의 내용으로, 만약 loop가 존재하지 않는 그래프라면 이는 "Tree"라고 부른다.
그러면 이제 dim(N(AT))가 루프의 개수를 의미하는 것을 알았다.
그리고 다음과 같은 점들도 알 수가 있다.
dim(N(AT))=m−r
#loops=#edges−(#nodes−1)
위에서 왜 "r=#nodes−1"이 나오냐면, 연결된(directed) 그래프에서는 최소 하나의 노드가 연결되어 있기 때문에, 해당 노드는 다른 노드들의 연결로 표현이 가능하여 전체 노드 수에서 1을 빼줘야 하기에 "r=#nodes−1"이 나온다.
그리고 여기서 Euler's Law도 증명된다는 것을 알 수 있다.
#nodes−#edges+#loops=1
강의에서 potential difference(전위차), Ohm's Law(옴의 규칙), Euler's Law(오일러 공식) 등을 얘기하고 있는데, 사실 제대로 이해가 가지 않았다. 그래서 그냥 그래프 기준으로된 연산들에만 집중했다.
해당 내용에 대해서는 https://bizzengine.tistory.com/158 를 참조하였다.
