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

점은 대상이에요

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

빈 자리를 눌러 점을 놓아봐요. 점 하나가 대상 하나예요. (점 = 노드)

점을 놓을수록
대상이 늘어났어요.
하지만 점만 있으면
그냥 흩어진 알갱이예요.
역이 따로따로 있으면
노선도가 아니듯이요.
점들이 서로
어떻게 이어지는지가 빠졌어요.
그 이음을 다음에서 그어봐요.

선은 관계예요

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

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

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

트리는 특별한 그래프예요

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

고리를 만드는 선을 눌러 끊어봐요. 고리가 사라지면 트리가 돼요. 트리 ⊂ 그래프.

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

그래프는 어디에나 있어요

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

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

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

정리해볼까요

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

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

그래프를 그릴 줄 알게 됐으니
진짜 재미는 이제부터예요.
한 점에서 출발해
선을 따라 모든 점을 둘러보는 법,
가장 가까운 점을 찾는 법.
그걸 그래프 탐색이라고 불러요.
다음 강에서, 점과 선 위를
어떻게 누비는지 함께 따라가봐요.