by
Dec 03. 2023
[수다:數茶, 차 마시며 보는 수학 이야기. 04]
끈끈한 거미줄_그래프 이야기(1)
초등학교에 입학하고 부터 고등학교를 졸업할 때 까지, 선생님들과 주변 어른들은 우리에게 "수학을 열심히 배워둬야 한다." "수학을 잘 해야 다른 과목들도 잘 할 수 있다." 라며 수학의 중요성을 강조하셨다. 성인이 되어 공부의 자취들을 돌아보니 수학 공부를 통해 논리적인 사고도 기를 수 있었고, 전반적인 학업역량에 큰 밑거름이 되었다 생각한다.
하지만 사회는 논리만으로 돌아가는 것 같진 않다. 우리는 살다보면 정말 복잡한 문제를 마주한다. 공부를 열심히 하는 중에도 또래들과 잘 어울리라는 말은, 커서는 새로운 인간관계 그리고 취직하게 되면 마주할 직장 상사와의 관계로 뻗어나간다. 우리를 끊임없이 따라다니는 문제, 바로 인간관계는 사회생활을 하면서 피할 수 없는 문제이다.
누군가는 다른 누군가와 연결되어 있고, 그 역시도 다른 누군가와 연결이 되어있다. 또, 연결은 사람마다 가지각색이다. 마치 알록달록 거미줄 같다.
이렇게 아름다운 거미줄이지만 우리에게 얽힌 줄은 아름답지만은 않은 것 같다. 인간관계에 있어 각자의 고충이 있기 마련이다. 가끔은 이런 엉킨 거미줄을 풀고 싶을 때가 있지 않은가? 이런 복잡한 거미줄을 명료하게 정리해줬으면 좋겠다 생각이 든다.
사람들의 세계에서와 마찬가지로 수학의 세계에서도 복잡한 관계를 풀어나가는 시도가 있다. 우리가 생각하는 인간관계와 비슷하게, 관계를 가진 대상을 수학적으로 분석하여 여러 결과를 도출하는데, 이것이 바로 그래프 이론이라는 학문이다.
우선 복잡한 생각은 잠시 멈춰두자. 이름만 짚어 보자면 그래프 이론이라는 이름에서 '그래프'를 다루는 이론임을 짐작할 수 있다. 그렇다면 '그래프'란 무엇인가?
그래프(graph)란, 각기 떨어져 있는 점들(node, 노드)과 이 점들을 이어주는 선들(edge, 엣지)로 이루어진 연결 그림을 일컫는다. 단 연결 그림을 그릴 때 몇가지 조건이 있는데,
1) 점은 각기 떨어진 대상들이며, 오로지 선들만이 이 떨어진 점을 이어준다.
2) 두 점은 오직 하나의 선으로만 연결되어야 한다.
3) 자기 자신과는 연결되지 않는다.
(단, 위 조건들은 쉽게 그래프를 설명하기 위해 가져온 것이며, 조건을 지우더라도 약한 의미에선 여전히 그래프이니 너무 조건에 매몰되진 말자.)
직접 그래프를 관찰하기 위해 5개의 점을 한데 그려두자. 각각 1번 점, 2번 점, ... 5번 점이라 이름을 붙이고 이들 중 원하는 쌍만 선들로 이어주자.
작가는 (1번, 3번), (1번, 5번), (2번, 3번), (2번, 5번), (4번, 5번) 쌍을 선으로 이어주었다. 이렇게 점들을 이어주면 하나의 그래프가 완성이 된다. 5개의 점들과 5개의 선들로 이루어진 이 그림은 무언가 빈 공간이 많아 보인다. 유심히 보면 (1번, 2번)은 연결이 안되어있다. (3번, 5번)도 마찬가지이다. 그래프를 그려뒀지만 이렇게 완전히 연결이 안된 그래프를 '불완전그래프'라고 한다.
이렇게 아직은 불완전한 그래프지만 마저 이어보면 5개의 선들을 더 그릴 수 있고,
