[Linear algebra] 12. Graphs, networks, incidence matrices

Lecture

https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/resources/lecture-12-graphs-networks-incidence-matrices/

Lecture 12: Graphs, networks, incidence matrices | Linear Algebra | Mathematics | MIT OpenCourseWare

 

Note

• 그래프는 node가 column, edge가 row에 오도록 표현하여 matrix화할 수 있는데 다른 일반 matrix와 달리 규칙적인 구조를 갖고 있다. 예를 들면 위 예시와 같이 1개의 edge에는 2개의 node가 개입하기 때문에 row 단위로 정해진 개수의 non-zero element, 정해진 개수의 zero element가 있다.
• row dependency를 확인했을 때 dependent한 그룹이 발견된다면 이는 graph 상에서 loop를 의미하기도 한다.
• linear algebra는 graph 구조를 푸는 유용한 방법이다.
  
  

• 위 예시를 더 들여다보고 위 A matrix의 null space는 c [1, 1, 1, 1] 로 형성되는 1차원이다. 다른 말로 모든 node의 값이 같을 때이다.
• 이 값은 만약 node가 전류가 흐르는 시스템의 각 지점의 전압이라고 생각한다면 모든 위치의 전압이 같을 때 전류가 흐르지 않는 자연의 모양과 같다. 온도도, 물도 마찬가지로 다 대입이 가능하다. 
• 그래프로 표현하면 matrix로 표현할 수 있고, matrix 레벨에서 풀고 그 의미를 들여다 보면 자연 현상과 동일했다는 것이 주목할 만한 점이다. 단순히 숫자놀음이 아니라 왜 이러한 개념과 풀이가 필요하고 그 의미를 분석해볼 필요가 있는지 암시하는 부분이다.
  
  

• 같은 그래프에서 left null space를 푸는 것이 자연을 표현한 예시도 있다. 전류를 셈할 때 Kirchoff's current law를 사용하는데 이 법칙은 그래프 matrix의 left null space를 푸는 것과 같다. 
  
  

• 간단히 말해 loop 단위로 보았을 때 전류의 합이 0이 된다는 말인데 y를 각 edge에 흐르는 전류라고 보았을 때 left null space는 Kirchoff's curret law를 따르는 전류양의 관계를 정확히 표현한다. 
  
  

• dim(N(A.T)) 가 Kirchoff's CL에 의해 loop의 개수와 같다는 걸 알았고 그 이후에 그 값은 m-r과 같다는 것도 안다.
• 이를 기반으로 수식을 세워보면 num(nodes) - num(edges) + num(loop) = 1이라는 식을 세울 수 있는데 이는 Euler's formula와 동일하기도 하다!
• 사소하게는 pivot column만 뽑아내서 생각해보면 그래프에서 loop를 뺀 tree 구조를 찾아낼 수 있기도 하다.