어떻게 점과 선으로 그린 세상, 그래프

점은 대상이다

그래프는 점에서 시작한다. 점 하나가 대상 하나다. 역, 사람, 웹페이지처럼 무엇이든 점이 될 수 있다.
점에는 이름을 붙인다. 그래야 어느 점인지 알 수 있다.
아직 선은 없고, 점만 흩어져 있어요.

빈 자리를 누르면 점이 놓인다. 점 하나가 대상 하나예요. (점 = 노드)

점을 놓을수록 대상이 늘어난다. 하지만 점만 있으면 그냥 흩어진 알갱이일 뿐이다.
역이 따로따로 있기만 하면 노선도가 아닌 것과 같다. 점들이 서로 어떻게 이어지는지가 빠져 있다.
그 이음은 다음에서 그어요.

선은 관계다

이제 점들을 이어 보자. 두 점을 선으로 잇는다는 것은 '이 둘은 관계가 있다'는 뜻이다.
두 역 사이에 길이 있다, 두 사람이 친구다, 이 웹페이지가 저기로 링크한다. 선 하나가 관계 하나다.
점과 선이 모이면 그래프가 돼요.

점 하나를 누르고 다른 점을 누르면 선이 생긴다. 선 하나가 관계 하나예요. (선 = 엣지)

선을 그을수록 점들이 하나로 엮이고, 흩어진 점이 비로소 노선도가 된다.
점은 대상, 선은 관계. 이 둘만으로 세상의 수많은 것을 그릴 수 있다.
그 가운데 우리가 이미 아는 모양도 숨어 있어요.

트리는 특별한 그래프다

그래프에는 고리가 생길 수 있다. 점 A에서 출발해 선을 따라가다 다시 A로 돌아오면 그것이 고리다.
고리가 하나도 없는 그래프가 바로 트리다. 돌아오는 길 없이 가지처럼 뻗기만 하는 모양이다.
그러니 트리는 그래프의 한 종류예요.

고리를 만드는 선을 누르면 끊어진다. 고리가 사라지면 트리가 돼요. 트리 ⊂ 그래프.

고리 하나를 끊었더니 돌아오는 길이 사라졌다. 뒤엉켜 보이던 그래프가 깔끔한 트리가 된 것이다.
앞에서 본 폴더나 가계도가 바로 이런 트리였다.
트리는 그래프의 특별한 경우이고, 다시 말해 그래프가 더 큰 우산이에요.

그래프는 어디에나 있다

점과 선이라는 안경을 쓰면 세상이 다르게 보인다.
지하철은 역(점)과 노선(선)이고, 친구망은 사람(점)과 우정(선)이며, 웹은 페이지(점)와 링크(선)다.
전혀 달라 보이던 것들이 사실은 같은 그림이었다. 그래서 하나를 풀면 나머지도 함께 풀려요.

예시를 눌러 바꾼다. 지하철·친구망·웹, 모두 같은 점과 선이에요.

예시를 바꿔도 그림의 뼈대는 똑같다. 점이 대상, 선이 관계이고 이름표만 바뀔 뿐이다.
바로 이 점 때문에 그래프는 쓸모가 아주 많아요. 한 가지 도구로 세상의 수많은 문제를 그릴 수 있기 때문이다.

정리

한 줄로 모으면 이렇다. 점은 대상, 선은 관계, 점과 선으로 그린 그림이 그래프다. 고리가 없는 특별한 그래프가 트리다.
지하철도, 친구망도, 웹도 모두 점과 선으로 그릴 수 있다.
이제 점과 선이 놓였으니 남은 질문은 하나예요. 이 점들 사이를 어떻게 돌아다닐까?

핵심을 차례로 눌러 되짚는다. (점=대상 → 선=관계 → 그래프 → 트리는 고리 없는 그래프)

그래프를 그릴 줄 알게 됐으니 진짜 재미는 지금부터다.
한 점에서 출발해 선을 따라 모든 점을 둘러보는 법을 그래프 탐색이라고 하고, 가장 짧은 길을 찾는 법은 그 뒤에 이어진다.
다음 레슨에서는 점과 선 위를 어떻게 누비는지 따라가요.