2주차 개념 #1. 그래프이론의 기초(Graph, Vertex, Edge, Weight)

2주차 개념 #1. 그래프이론의 기초(Graph, Vertex, Edge, Weight)

자 오늘은 그래프 이론에 대해서 배워보도록 할텐데,

사실 그래프 이론이다라고 했을 때 정말 많은 개념들이 있어요. 뭐 오일로경로, SCC, 단절점 등 정말 어려운 개념들도 많고 또 넓은 범위를 다루는 개념이지만 오늘은 기초 중에 기초를 배워보도록 할게요.

자 첫번째 정점과 간선입니다.

정점(vertex)은 노드 라고도 불리구요. 그래프를 형성하는 기본단위 입니다.

정점은 분할할 수 없는 객체이자 "점"으로 표현되는 위치, 사람, 물건 등이 될 수 있습니다. 그러니까 '저' 라는 사람, 또 제가 가지고 있는 물건, 저의 위치가 정점으로 놓일 수 있다는 거예요.

 

반면, 간선(Edge)은 이러한 정점을 잇는 선을 의미합니다.

관계, 경로 등이 될 수 있어요. 예를 들어서 어떠한 위치나 사람으로부터 무언가를 통해 간다고 했을 때 '어떠한 위치나 사람'은 정점이 되고요. '무언가를 통해 간다'는 간선이 된다라는 거예요.

예를 들어서 제가 어떠한 위치에서 어디로 간다고 해볼게요.

자 그러면 이 위치는 제가 지금 온양관광호텔에 있거든요. 그리고 제가 남성역을 간다고 해볼게요. 이때 이러한 위치들은 정점이 될 수 있는 거예요. 자 그러면 이 정점과 정점을 잇는 선은 경로가 되겠죠? 이런 것들이 간선이 된다는 거예요.

그리고 정점과 간선의 관계는 위치, 그리고 경로도 될 수 있지만 사실은 사람과 사람 간의 관계도 될 수 있어요.

 

실제로 큰돌이가 옥순이를 짝사랑했습니다.

저의 슬픈 기억이지만 자 이러한 것도 정점과 간선이 된다라는 거에요. 그러니까 저라는 사람, 그리고 옥순이라는 사람은 뭐가 돼요? 정점이 돼요.

그리고 저라는 마음은 어떻게 돼요? 제가 이 사람을 좋아한다는 감정은 하나의 간선이 된다라는 거예요.

 

자 그리고 여기서 더 나아가서 지금까지 정점과 간선을 배웠는데,

나로부터 여기까지. 그러니까 뭐뭐부터 뭐뭐까지 라는 이 선밖에 없으면 뭐다? 단방향 간선이다라고 하는 거예요.

반면에,

근데 만약에 이 옥순이도 저를 사랑한다면 두 개의 간선이 있는 거죠. 서로 오고 가고 할 수 있죠. 얘를 양방향 간선이다. 라고 해요.

이번에는 편도와 왕복으로 예시를 들게요. 예를 들어서 그럴 리 없겠지만 남성역에서는 온양관광호텔을 가지 못하고, 온양관광호텔에서만 남성역을 갈 수 있는 경우, 하나의 간선만 있기 때문에 이거를 단방향 간선 이라고 합니다.

반면, 왕복은 네이버 지도에서 출발지와 목적지와 바꾸면 갈 수 있는 길이 나와요. 이렇게 왕복이 있는 거를 양방향 간선 이라고 하는 거예요.

 

자 그럼 이제 indegree와 outdegree에 대해서 얘기해볼게요.

참고로 저희가 그래프 관련 문제를 풀거나, 그래프 관련 어떤 설명을 듣다보면 u와 v로 설정해 놓은 걸 되게 많이 보실 거에요.

그러니까 그래프를 표현할 때 어떤 식이나 이런 걸 보면 u와 v를 많이 볼 텐데, u는 그 이런 그래프 이론에서 보통은 from 이라는 의미로 많이 써요. 그리고 v는 to 라는 의미를 가지고 있어요.

지금 저는 u에서 v로 가는 단방향 간선 하나를 그렸어요. 그런데 u에서 v로 가는 경로가 한 4가지가 있다고 할게요.

그런데 이거를 어떻게 표현하냐? 라는 거는

'u의 outdegree가 4개구나' 라고 하는 거예요. 그러니까 정점과 정점을 잇는 간선이 무조건 하나가 아니라는 거예요.

아까 본 네이버 지도를 예시로 들면,

지금 온양관광호텔과 남성역을 예시로 했을 때 온양관광호텔에서 남성역까지 가는 경로는 6개인 반면, 남성역에서 온양관광호텔까지 가는 경로는 7개인 것을 볼 수 있습니다.

이걸 어떻게 표현하냐? 이 u라는 정점에서 봤을 때 indegree는 7개 라는 거예요.

다시, 이 정점으로부터 나가는 간선들은 outdegree 라고 부르고요. 들어오는 간선은 indegree 라고 합니다.

다시 볼게요. u와 v 라는 정점이 있어요. u에서만 가면 단방향 간선이고, v에서도 가면 양방향 간선이죠.

u라는 정점에서 봤을 때, indegree는 2개죠. 반면, 자 u라는 정점에서 나가는 간선, outdegree는 4개예요.

 

이제 v를 예로 들게요.

v의 관점에서도 생각할 줄 알아야 되죠. v라는 정점에서 indegree는 몇 개예요? 4개죠. outdegree는 2개입니다.

자, 이렇게 해서 indegree, outdegree 까지 알아봤고요. 그리고 이렇게 지금 저희가 정점이나 간선을 설명을 했잖아요.

이런 정점과 간선으로 이루어진 집합들, 이런 거를 그래프다. 라고 해요.

이 세 개의 정점은 두 개의 간선으로 연결이 되었죠?

그런데 이렇게 그렸을 때, 위의 것과 아래 것은 연결되어 있지는 않죠. 그래서 이러한 집합들을 그래프 라고 하는 거에요.

다시 말해서, 정점과 간선의 집합을 그래프 라고 하는 거에요.

---

자 그리고 이번에는 가중치를 배워보도록 할텐데,

가중치는 정점과 정점 사이에 드는 비용을 뜻해요.

앞선 예시에 있던 온양관광호텔에서 제가 남성역으로 간다고 했죠. 그래서 온양관광호텔과 남성역이 정점이다 라고 했구요. 그리고 온양관광호텔과 남성역 사이에 있는 선을 간선이다라고 했어요.

온양호텔에서 남성역으로 갈 때, 이 간선에 드는 비용을 가중치라고 해요.

제가 온양관광호텔에서 남성역으로 간다고 했을 때,

드는 비용은요, 시간이 될 수가 있고요. 칸이 될 수가 있고요. 비용이 될 수가 있어요.

이걸 보면 택시비는 98,530원 통행료는 3,500원 연료비는 13,667원 그리고 시간은 1시간 36분, 이게 가중치라고요.

우리가 시간은 돈이라고 하잖아요. 시간, 뭐 그리고 비용, 돈. 그런 거를 가중치라고 해요.

 

알고리즘 문제를 풀다 보면 이게 어떤 형식으로 나오게 되냐면,

예를 들어서, 어떠한 정점에서 어떠한 정점으로 간다라고 했을 때, 이렇게 주어질 때가 있어요.

제가 어떤 칸 위에 있어요. 그리고 제가 여기까지 이동을 해야 돼요.

자, 그럼 몇 칸이 걸려요? 1칸, 2칸, 3칸이 걸리죠. 3칸, 이게 가중치라고요.

그러니까 문제에서는 뭐 비용으로 어떤 돈이 됐다, 어떤 시간이 됐다, 뭐 3분, 3시간 이렇게 표현할 수도 있지만 이렇게 3칸으로 표현될 수도 있다라는 거예요.

 

자, 이렇게 해서 그래프 이론의 기초에 대해서 얘기를 해봤습니다.