Graph and Adjacency Matrix 기초

여러 항목간의 1:1 대결 결과를 바탕으로 전체 순위를 산정하는 방법을 공부하다가 Graph와 Adjacency Matrix라는 개념을 처음 접하게 되었다.

간단하게 정리를 해보자면…

그림처럼 A->B, B->C 이런 Graph인 G1이 있다고 하자. 이를 Adjacency matrix A1으로 변환할 수 있다.

이렇게 만들어진 Adjacency matrix는 재미있는 성질을 가지게 되는데, 바로 n제곱을 하게 되면 n단계를 거쳐 해당 vertex로 올 수 있는 경우의 수를 나타내준다는 점이다.

그림의 윗부분을 보면 A가 B를 이겼고, B가 C를 이겼다면, A가 C를 간접적으로 이겼다고 볼 수 있다는 것을 나타낸다. 즉 Adjacency matrix의 제곱은 한다리 거쳐서 얻은 승수를 나타내준다. 같은 방식으로 세제곱을 하면 두다리거쳐서 얻은 승수를 나타내게 될텐데, 이 그래프에서는 3단계 승수가 없으므로 zero matrix가 된다.

그림 아랫부분을 A와 B가 서로 알고, B와 C가 서로 아는 사이를 나타내는 그래프라고 가정한다면, adjacency matrix의 제곱은 한다리 거쳐서 아는 경우의 수를 나타내는 matrix가 되겠다. 지금 그림에서는 각 vertex에 대한 self-loop이 없기 때문에 main diagonal 값이 모두 0인 matrix가 만들어지지만, 만약 self-loop을 넣어 모두 1로 잡고 (나는 나 자신을 안다) 제곱을 계속 해나가다보면 어느 순간에 matrix에 0 값이 사라지게 된다. 이런 식으로 small world network 관련 계산을 할 수 있겠다.

재미있네! 후훗~