시작

오늘은 CS지식의 기초인 그래프 이론에대해 알아볼 것이다. 보통 우리가 아는 그래프는 엑셀이나, 한글과 같은 곳에서 보이는

이런 그래프를 많이 떠오를텐데, 지금 이 CS에서 말하는 그래프는 정점(Vertex)와 간선(Edge)으로 이루어진 것을 이야기 한다.

정점과 간선

한번 예시를 들어보자면, 정점(Vertex)는 어떤 사람이나, 물건이 될 수 있으며 간선(Edge)는 어떤 사람이나, 물건 까지의 길이라고 생각하면 된다. 그렇다면 "꽃병"과 "사람"은 정점(Vertex)라고 할 수 있으며, "꽃병"과 "사람"사이의 길은 간선(Edge)라고 할 수 있다.

indegree와 outdegree

우선 이 것들을 설명하기 전에 용어를 아는게 아닌 어떤 얘시 사용 되는지를 알아야된다. 그러면 어떻게 사용되는 예시를 알아보도록 하자.

사용 예시

만약 A위치에서 B위치로 간다고 가정해보자. 그걸 그래프로 표현한다면 이렇게 표현이 될 것이다.

다시 길을 찾아보니 한가지 방법이 더 있는 것! 그리고 B에서 A로 가는길은 한가지가 없다. 그러면 그림으로 표현해보자.

그러면 이런식으로 그림이 나오는데. 이렇게 된다면 A의 outdegree는 2개 indegree는 1개라는 것과 B의 outdegree는 1개 indegree는 2개 라는 것을 알 수 있다. 그렇다면 indegree와 outdegree의 표현 방법을 알 수 있는데. indegree는 정점에 들어오는 간선의 개수고 outdegree는 정점에서 나가는 간선의 개수라는 것을 알 수 있다.

가중치

그래프 이론에는 가중치라는 것이 존재한다. 가중치는 그래프의 정점에서 정점까지 가기까지의 비용이라 생각하면 쉽다. 그렇다면 한번 예시를들어보자면, A에서 B까지의 가는 방법이 2가지가 있는데, 버스를 이용하는 방법과 택시를 이용하는 방법이 있다. 버스를 이용하면 3000원 이라는 비용을 지불해야되고, 택시를 이용하면 1만원이라는 비용을 내야된다. 이 것을 가중치라고 부른다.