학부 1학년 1학기, 당시 선형대수학이랑 확률 통계를 한 학기동안 다 나가는 괴랄한 수업을 진행하시던 교수님이 여름방학 동안 보라고 추천해주신 영화가 하나 있다. 바로 맷 데이먼 주연의 굿 윌 헌팅. MIT에서 청소부로 일 하는 천재 윌이 삶에 대해서 깨닫는 대충 그런 영화다. 두 세번정도 돌려본 영화이기도 하다.
각설하고 영화의 초반부에 램보 교수는 학기를 마무리하는 문제로 칠판에 이상한 수학 문제를 휘갈겨 놓는다. 정확한 기억이 나진 않지만 해당 문제를 풀면 유명한 연구실에서 연구할 수 있는 기회가 주어지는 뭐 그런 어려운 문제라고 소개한다.
영화에서는 푸리에 이론이랑 관련있다고 했는데, 최근에 다시 영화를 보면서 보니 이거 푸리에 이론이랑 상관이 없어보인다. 그래프 이론이랑 관련된 문제인 것 같다. 이번 학기 대학원 코스웤으로 그래프 관련 수업을 들은 덕분에 찾을 수 있었던 재밌는 옥에 티가 아닌가 싶다. 잠깐 시간을 내서 해당 문제를 풀어봤다.
이제 MIT 명문 연구실에 들어가기 위한 문제를 풀어보도록 하자!
G is the graph (그림)
1) Find the adjacency matrix A
그래프 G의 adjacency matrix A를 찾으란다. 우선 adjacency matrix가 뭔지 알아야 한다. 그래프는 두 가지 요소가 있다. 첫번째는 노드(node or vertex), 두번째는 엣지(edge or link)이다. 간단하게 이야기하면 노드는 점이고, 엣지는 그 점들을 연결하는 선을 의미한다. 노드와 엣지는 좌표처럼 어딘가에 고정되어 있는 것이 아니기 때문에 완전 다르게 생긴 것 같은 두 그래프도 사실은 똑같은 그래프일 수 있다.
이렇게 그래프라는 놈이 자유도가 높다보니, 뭐 수학적으로 이 녀석을 잘 표현할만한 방법이 필요한데, 그게 바로 adjacency matrix다. 그래프에서 중요한 것은 노드 사이에 연결이 있느냐 없느냐, 있으면 어느정도 있느냐 하는 것이니, 그것만 잘 표현할 수 있으면 된다. 그런데 이 놈들은 노드에 순서 조차 없으므로 같은 그래프를 가지고도 다른 adjacency matrix를 얻을 수 있다 (귀찮긴 하지만 자유도가 높은 만큼 대부분의 자료를 그래프로 표현할 수 있다는 강점을 가진다).
N개의 노드가 있는 방향성이 없는 그래프가 있다면, 그 그래프의 adjacency matrix는 N by N 형태를 가진다. 1번 노드와 2번 노드가 연결되어 있다면 행렬의 1행 2열과 2행 1열에는 존재하는 엣지의 수가 값으로 존재한다. 방향성이 있는 경우에는 출발하는 노드의 열, 도착하는 노드의 행에 대해서 값을 적어준다. 방향성을 열->행 방향으로 하느냐 행->열 방향으로 하느냐는 쓰는 사람 마음인데 나는 배우기를 열->행으로 배웠으니 그렇게 써둘련다.
앞의 그래프를 adjacency matrix로 그려놓고 보니 실제로 동일한 그래프 임을 알 수 있다. 오른쪽 그래프의 노드 번호를 좀 신경써서 매겨야 하긴 했지만 말이다. 아무튼 무슨 개념인지 대충 이해했으리라 믿는다. Adjacency matrix는 그래프를 노드간의 연결성을 기반으로 표현하는 가장 기본적인 표현법이다 정도만 이해하면 된다.
문제로 돌아와서 그래프를 보면 1은 (2, 4), 2는(1, 3_1, 3_2, 4) 3은 (2_1, 2_2), 4는 (1, 2)와 연결되어 있으니 오른쪽 처럼 생긴 행렬로 표현할 수 있게 된다. 2와 3사이에는 엣지가 2개니 1이 아니라 2라는 것만 주의하면 되겠다.
c.f.) 참고로 지금처럼 방향성이 없는 그래프에서 어떤 노드에서 출발해서 다시 자기자신으로 다시 들어오는 엣지는 1이 아니라 2를 적어준다. 나갈 수 있는 길이 2개라서 그렇다고...
벌써 1번을 풀어버렸다. MIT의 저명한 연구실 들어가는 것 생각보다 쉬울지도 모르겠다.(물론 아니다)
2) Find the matrix giving the number of 3-step walks
3-step walks의 수를 알려주는 matrix를 구하라고 한다. 여기서 알아야 하는 개념은 walk와 step이다. 익숙한 단어이긴 하다. 쉽게 이야기하면 어떤 노드에서 다른 노드로 옮겨가는 것을 이야기 한다. 1번 노드에서 2번 노드로 넘어가면 1-step walk (1->2)인 것. 생각해보면 1-step walk를 하나하나 다 세어보면 (1->2), (1->4), (2->1), (2->3_1), (2->3_2), (2->4), (3->2_1), (3->2_2), (4->1), (4->2) 뭐 이렇게 10개가 될게다. 잘 생각해보면 연결만 되어 있으면 양 방향으로 왔다리 갔다리가 되니까 1-step walk의 수는 edge 개수의 2배가 된다.
그런데 2-step부터는 문제가 조금 달라진다. (3*# edge)로 구하면 되나? 라는 행복한 상상을 할 수 있지만 이런 상황을 생각해보자. 2->3->4 ? 이건 안된다. 3에서 4로는 갈 수 없으니까 말이다. 심지어 walk는 같은 노드에 한 번 더 들려도 괜찮다. 1->2->1이 된다는 것. 그럼 1로 가는 경우는 1에서 갈 수 있는게 2개니까 경우의 수 열심히 때리면 되는거 아니냐? 라고 할 수 있지만 100-step walk는...? 어떻게 구할거냐...? 대부분의 대학 전공서적의 문제들은 새끼 문제들이 서로 유기적으로 연결되어 있다는 사실을 생각해보자. 일반적으로 뒤에서 안 쓸 내용을 앞에서 구하라고 안한다. 즉 아까 이야기한 adjacency matrix를 잘 활용하면 walk를 셀 수 있다.
A*A를 하는 상황이다. 행렬곱을 모르는 이들을 위해서(사실 이걸 모르면 이 글을 읽고 있지도 않겠지만...) 행렬곱에 대해서 간단히 설명하자면, 수식상 앞에 있는 행렬의 행(가로) 성분을 뒤에 오는 행렬의 열(세로) 성분과 각각 곱해서 다 더하면 된다. 가령 1행 (0, 1, 0, 1)과 1열(0, 1, 0, 1)을 곱하면 0*0+1*1+0*0+1*1 = 2 이고 이제 최종 행렬의 1행 1열에 2가 들어가는 것이다.
이걸 adjacency matrix의 측면에서 생각해보자. Adjacency matrix 성분의 값이 0이 아니라는 것은 연결이 되어 있다는 뜻이고 이는 곧 walk를 만들 수 있다는 것이다. 2행과 3열을 곱하는 상황을 생각해보자. (1,0,2,1)⋅(0,2,0,0)이므로 결과적으로 0이다. Adjacency matrix의 행 혹은 열의 값이 의미하는 것은 넘어갈 수 있는 길의 개수다. 즉, (1,0,2,1)은 2번 노드에서 1, 2, 3, 4번 노드로 넘어갈 수 있는 길이 각각 1, 0, 2, 1개라는 뜻이다. 그렇다면 (0,2,0,0)은 1,2,3,4번 노드에서 3번 노드로 넘어올 수 있는(사실 방향성이 없는 상황이라 동일한 개념이지만, 편의를 위해 이렇게 씁니다) 길의 개수가 각각 0, 2, 0, 0개라는 뜻이다. 자 그럼 각각의 성분을 곱하면 뭐냐? 2번에서 3번으로 2-step에 걸쳐 넘어가는 각각의 경우의 수를 의미하는거다. 1*0(2->1->3 경우의 수), 0*2(2->2->3 경우의 수), 2*0(2->3->3 경우의 수), 1*0(2->4->3 경우의 수)인거다. 이해가 됐으면 한다... 즉 A^2의 각 성분은 2-step walk를 수행해서 해당 열->행 혹은 행->열로 갈 수 있는 경우의 수가 되는 것이다. 앞서 말한 1번으로 오는 경우, 2번으로 오는 경우, 이런게 단순한 행렬곱으로 표현이 되는 것이다. 영화의 문제에서는 3-step walk의 수를 알 수 있는 matrix를 구하라고 했다. 이건 곧 A*A*A=A^3 인 것!
계산을 하면 위와 같다. n-step walk가 A^n 이라는 것을 처음부터 생각해내는 것은 수학적인 직관이 풍부한 사람이 아니라면 쉬운 일은 아니겠다만 그래프 이론을 다루는 많은 전공서에서는 해당 공식을 walk의 개념을 설명하며 알려주므로 사실 MIT를 다니는 학생들에게는 구몬 2번 정도의 문제가 아니였을까 싶다. 한 걸음 더 MIT의 명문 연구실에 다가가고 있다. 3번 4번은 나중에 또 짬날 때 풀어서 정리하겠다. 이번 글을 마무리하기에 앞서 이런 walk 개념을 어따 써먹냐고 할 수 있다. 본인도 중⋅고등학생 때 '수학 이거 공부해서 어디다 써먹나'하는 생각을 많이 했었기에 이런게 도움이 될까 싶어 적어본다.
walk는 결국 노드 간의 연결성을 기반으로 graph를 travel하는 경우의 수이다. 본인의 기억이 맞다면 경우의 수는 확률과 통계 따위의 과목에서 확률을 정의하기 위해서 배웠다. 어떤 그래프로 모델링된 자료가 있을 때 이 자료를 확률적으로 분석하기에 참 좋은 도구가 될 수 있다는 것이다. 대표적인 적용 예시로 전염병이 전파되는 것을 walk를 기반으로 시뮬레이션 할 수 있다. 사람 한 명, 한 명을 노드로 정의하고 각 노드에는 감염 여부를 판단할 수 있는 변수가 하나씩 저장되어 있다고 하자, 감염을 시킬 수 있을만한 밀접 접촉이 있었던 사람들을 끼리 엣지로 연결한다고 생각해보자. 어떤 확진자 한 명이 있다고 생각하고 그 사람이 밀접 접촉해서 전달할 수 있는 사람은 1-step 노드에 있는 사람들이 된다. 이제 이 사람들의 감염 가능 여부를 False->True로 바꿔준다. 이제 그 사람과 edge를 가지는 사람은 모두 감염 가능 여부가 True가 됐을거다. 이제 walk를 한 번 더 돌리자. 또 다시 감염 가능 여부가 True인 사람과 만나는 사람들의 감염 가능 여부를 True로 바꿔준다. 이걸 몇번 반복하다 보면 감염의 여지가 있는 사람들을 알 수 있게 된다.
그런데 또 실제 세계에서는 small world라는 성질이 있다. 뭐 전세계에 있는 사람 중 아무나 한 명을 잡아서 그 사람한테 편지를 보낸다고 할 때 '6~8다리 건너면 그 사람한테 전달할 수 있다' 뭐 그런 얘기 (그 유명한 무야호 밈이 탄생한 무한도전 김상덕씨 찾기 에피소드도 비슷한 맥락) 들어본 적이 있을 것 같다 (얻어 가는 교훈은 세상은 x나 좁으니 말과 행동을 조심하자는 것). 그러니 walk를 계속 돌리다 보면 막판엔 대부분의 사람들이 감염될 수 있게 되는 상황이 온다. 반면 실제 세계에서는 방역 지침 같은 것들도 있고 마스크나 사회적 거리두기 등이 코로나-19 전염에 영향을 준다. 그래서 이러한 영향들을 가중치로 모델링 해서 사용하거나 확률을 도입하여 실제 세계와 유사한 시뮬레이션을 구현하고는 한다. 위의 그림은 지나가다 본 비슷한 연구인데 state transition을 도입해서 시뮬레이션을 모델링 했던 것으로 기억함. 궁금하시면 읽어보시라. 이외에도 초기 구글 검색 엔진의 page rank 알고리즘에 적용된 random walk, teleport 등이 결국 walk의 개념에 기반을 두고 있다는 것.
본인은 사실 딱히 수학을 잘 못하는 편이지만 선형대수, 미적분, 확률, 최적화 이론 범벅인 그래프 이론 게시물을 작성하고 있는 이유는 1) 간지남, 2) 멋있음 이다. 암튼 한 학기동안 나름 재미있게 공부했던 것 같아. '굿윌헌팅으로 그래프 이론 찍먹하기!' 시리즈로 본인처럼 흥미를 느끼는 사람이 있었으면 한다는 원대한 바람이 있다..~ 뭐 그냥 그렇다고...~
'호에에엥?' 카테고리의 다른 글
| 극장판 짱구는 못말려 13기: 부리부리 3분 대작전 감상 (1) - 현실과 시뮬라크르, 메타버스? (2) | 2023.01.09 |
|---|
