graph(1) - 그래프와 트리

들어가기에 앞서

제가 포스팅을 할 때, 이야기 형식으로 기술을 합니다. 혹자는 내용만 정리하면 되는데 너무 글머리가 길다고 질문할 수 있습니다. 하지만 이는, 혹시라도 존재할 지 모르는 누군가가 제가 쓴 글을 처음부터 읽는다면 최대한 흡입력이 있도록 하기 위해서입니다.

아무튼 반갑습니다. 첫 포스팅입니다. 첫 주제를 graph 이론으로 선정하였습니다. 컴퓨터 과학에서 빠질 수 없는 주제이자, 어떤 상황을 특정 점(node, vertex)로 생각하여 문제를 해결할 수 있는 이론이기 때문입니다.

graph

그래프라는 단어를 들어봤을 때, 이런 막대그래프를 생각하신 분들도 있으실 것이고

어떤 좌표계에서 정의역의 값들과 함숫값의 쌍의 집합을 시각화한 형태라고 생각하신 분들도 있으실 겁니다.

하지만, 컴퓨터 과학에서 graph는 어떤 정점(node, vertex .. 이후 글에서는 이를 혼합하여 사용할 것입니다)과 그들을 잇는간선(edge)로 이루어진 자료구조를 일컫습니다.

현실에서, 서울 -> 부산까지 가는 시간이 2시간, 부산 -> 서울까지 가는 시간이 3시간인 교통편을 그래프로 생각해보겠습니다.

서울과 부산을 노드로 치환할 수 있습니다. 서울 -> 부산까지 가는 시간이 2시간으로 주어졌습니다. 이는 서울 -> 부산에 해당하는 간선에 2시간이라는 가중치(weight)가 주어졌다고 할 수 있습니다. 부산 -> 서울은 반대로, 3시간이라는 가중치가 주어졌다고 볼 수 있습니다.

지금은 정점이 2개밖에 없는 경우지만, 정점이 여러개가 있는 경우를 살펴보겠습니다.

4개의 정점이 있습니다. 부산, 서울, 일본, 섬 이렇게 4개가 존재합니다. 부산 -> 서울은 2시간, 서울 -> 부산은 3시간, 서울<->일본은 1시간, 일본->부산은 2시간, 섬은 고립된 존재라고 볼 수 있습니다. 그래프에서 연결된 부분을 컴포넌트(component)라고 부릅니다. 위 그래프에선, (서울,부산,일본)과 (섬) 2개의 컴포넌트로 이루어진 그래프라고 볼 수 있습니다. 또한 위 그래프들은, 간선에 방향이 표기되어 있습니다. 이러한 그래프를 방향 그래프(directed graph) 라고 합니다. 비방향 그래프(non-directed graph)는 방향이 없는 그래프입니다.

섬은 고립되어 있습니다. 따라서, 위 그래프의 모든 정점들은 연결되어 있지 않습니다. 위와 같은 그래프를 비연결 그래프(non-connected graph)라고 부릅니다. 이를 컴포넌트 이론과 연결지어 본다면, 컴포넌트가 하나면 연결 그래프고, 둘 이상이면 비연결 그래프라고 생각할 수 있습니다. 그래프의 모든 정점들 사이 경로가 있다면, 연결 그래프(connected graph)라고 부를 수 있습니다.

tree

tree는 graph의 종류입니다. tree의 정의는 cycle이 없는 연결 그래프라고 할 수 있습니다. 즉 하나의 컴포넌트로 이루어진 그래프입니다. cycle은 순환이라는 의미입니다. 어떤 정점을 기준으로 graph 내부를 탐험한 후, 시작 정점으로 돌아온다면 이는 cycle이 있다고 할 수 있습니다. 반대로, 시작 정점을 기준으로 탐험했을 때, 시작 정점으로 돌아올 수 없다면 이는 cycle이 없다고 판단할 수 있습니다.

하나의 컴포넌트로 이루어진 graph는 tree의 후보군이 될 수 있습니다. 될 수도, 안 될 수도 있습니다. 일단 연결 그래프라는 하나의 조건은 충족시켰기 때문입니다.

위 그래프는 cycle이 있는 graph의 간단한 예시입니다.

이산수학 그래프 이론

이산수학(discrete math)에서도, 그래프 이론을 배웁니다. 알고리즘을 위한 이산수학 그래프 이론을 간단하게 살펴보겠습니다.

두 정점을 잇는 간선이 있을 때, 두 정점을 이웃, 인접(adjacent) 정점이라고 부릅니다. 또한, 각 정점에 대해, 간선이 몇 개 달려있는지 나타내는 척도를 차수(degree)라고 부릅니다. 간단하게 팔이 몇 개 달려있는가를 나타낸다고 볼 수 있습니다. 간선의 수가 n개 있다고 하면, 그래프의 모든 정점의 차수의 합은 2n개가 있습니다. 왜냐하면 하나의 간선에, 두 개의 정점이 달려있기 때문입니다.

방향 그래프에서, 하나의 정점을 기준으로, 들어오는 간선의 수를 진입 차수(indegree), 나가는 간선의 수를 진출 차수(outdrgree)라고 합니다.

아래 그래프에서, 1번 정점에 대한, 진입 차수는 3, 진출 차수는 2입니다. 또한, 진입 차수와 진출 차수를 더한 값이 차수라고 볼 수 있습니다.

완전 그래프와 정규 그래프와 이분 그래프

완전 그래프(complete graph)는 정점의 수가 n개인 그래프에서, 모든 정점의 차수가 n-1인 그래프를 의미합니다. 즉, 하나의 정점에서, 자신을 제외한 모든 정점까지의 간선이 존재하는 그래프입니다.

정규 그래프(regular graph)는 모든 노드의 차수가 같은 그래프입니다. 즉, 정규 그래프 내부 완전 그래프가 존재한다고 할 수 있습니다.

어떠한 그래프의 정점에 단 두 가지의 색을 칠한다고 가정해보겠습니다. 이 때, 이웃한 정점들의 색이 같지 않게 칠할 수 있다면, 이러한 그래프를 이분 그래프(biprate graph)라고 부릅니다.

마무리하며

간단하게 그래프의 이해 및 종류에 대해 알아보았습니다. 다음 포스팅에서는 컴퓨터에서 어떻게 그래프를 구현하고, 탐험하는지에 대해 이론 및 실제 문제를 통해 알아보도록 하겠습니다.