그래프 이론 기초 — 정점, 간선과 핵심 개념

그래프 이론은 **그래프(graph)**를 연구하는 분야로, 그래프는 **정점(vertices)**과 **간선(edges)**으로 이루어진 구조입니다. 정점은 하나의 대상이고, 간선은 두 대상 사이의 관계를 나타냅니다.

그래프 이론의 기초를 찾고 있다면, 먼저 이 생각에서 시작하면 됩니다. 그래프는 연결 관계를 깔끔하게 모델링하는 방법입니다. 소셜 네트워크의 사람들, 도로로 이어진 도시들, 서로 링크된 웹페이지들은 모두 그래프로 나타낼 수 있습니다.

수학에서 그래프란 무엇인가

**무방향 그래프(undirected graph)**에서는 간선이 두 정점이 연결되어 있음을 뜻하며, 그 연결에는 방향이 없습니다. $A$가 $B$와 연결되어 있으면, $B$도 $A$와 연결되어 있습니다.

**방향 그래프(directed graph)**에서는 간선에 방향이 있으므로 $A \to B$와 $B \to A$는 서로 다른 의미입니다. 초보자용 예제에서는 보통 **단순 무방향 그래프(simple undirected graph)**를 사용하는데, 이는 루프가 없고 같은 두 정점 사이에 중복된 간선도 없다는 뜻입니다.

이 조건이 중요한 이유는 많은 정의가 먼저 단순 무방향 그래프를 기준으로 소개되기 때문입니다. 그래프의 종류가 바뀌면 용어의 의미도 달라질 수 있습니다.

먼저 알아야 할 그래프 이론 기본 용어

정점과 간선

정점은 추적하려는 대상입니다. 간선은 추적하려는 연결 관계입니다.

그래프가 도시와 도로를 모델링한다면, 도시는 정점이고 도로는 간선입니다.

차수

무방향 그래프에서 정점의 **차수(degree)**는 그 정점에 닿아 있는 간선의 개수입니다.

어떤 도시가 다른 세 도시와 도로로 연결되어 있다면, 그 도시의 차수는 $3$입니다.

경로

**경로(path)**는 연속한 각 정점 쌍이 간선으로 연결된 정점들의 나열입니다.

한 정점에서 다른 정점까지 경로가 있다면, 간선을 따라 한쪽에서 다른 쪽으로 이동할 수 있습니다.

사이클

**사이클(cycle)**은 시작점과 끝점이 같은 경로입니다. 보통의 기본 정의에서는 그 외의 다른 정점은 반복되지 않습니다.

사이클이 있다는 것은 그래프 안에 닫힌 고리가 있다는 뜻입니다.

연결 그래프와 연결 성분

무방향 그래프가 **연결되어 있다(connected)**는 것은 모든 정점이 어떤 경로를 통해 다른 모든 정점에 도달할 수 있다는 뜻입니다.

이 조건이 성립하지 않으면 그래프는 **연결 성분(connected components)**으로 나뉩니다. 각 성분은 그래프의 연결된 한 조각입니다.

예제로 보기: 작은 그래프 하나

정점이 $A$, $B$, $C$, $D$, $E$이고, 간선이 다음과 같다고 합시다.

$$AB,\ AC,\ BC,\ CD$$

그러면 $A$, $B$, $C$ 위에는 삼각형이 하나 생기고, $C$에서 $D$로 가는 간선이 하나 더 있으며, $E$는 고립된 정점이 됩니다.

이제 핵심 개념들을 쉽게 확인할 수 있습니다.

각 정점의 차수는 다음과 같습니다.

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

$A$에서 $D$로 가는 경로가 있습니다.

$$A-C-D$$

사이클도 하나 있습니다.

$$A-B-C-A$$

이 그래프는 연결 그래프가 아닙니다. 왜냐하면 $E$는 다른 정점들로부터 도달할 수 없기 때문입니다. 따라서 이 그래프에는 두 개의 연결 성분이 있습니다. 하나는 $A,B,C,D$를 포함하고, 다른 하나는 $E$만 포함합니다.

이 한 가지 예만으로도 차수, 경로, 사이클, 고립 정점, 연결 성분이 어떻게 함께 나타나는지 볼 수 있습니다.

빠른 확인: 차수의 합

유한한 무방향 그래프에서는 항상

$$\sum \deg(v) = 2|E|$$

가 성립합니다.

그 이유는 모든 간선이 정확히 두 끝점을 가지므로, 각 간선이 두 정점의 차수에 각각 $1$씩 더해지기 때문입니다.

위 예제에서 차수의 합은

$$2+2+3+1+0=8$$

이고 간선의 수는 $4$이므로,

$$2|E| = 2 \cdot 4 = 8$$

이 됩니다.

이 식은 손으로 차수를 셀 때 유용한 점검 방법입니다. 숫자가 맞지 않으면 어딘가 잘못된 것입니다.

그래프 이론에서 자주 하는 실수

정점과 간선을 헷갈리기

정점은 대상이고, 간선은 그 대상들 사이의 관계입니다.

그래프의 종류를 잊어버리기

단순 무방향 그래프에서 참인 명제라도 방향 그래프나 루프를 허용하는 그래프에서는 바뀌어야 할 수 있습니다.

경로를 사이클처럼 생각하기

경로는 시작한 곳으로 다시 돌아올 필요가 없습니다. 사이클은 반드시 돌아와야 합니다.

고립 정점을 무시하기

차수가 $0$인 정점도 여전히 그래프의 일부입니다. 이런 정점은 그래프가 연결되어 있는지 여부를 바꿀 수 있습니다.

그래프 이론 기초는 어디에 쓰일까

이 개념들은 컴퓨터 네트워크, 경로 계획, 스케줄링, 추천 시스템, 소셜 네트워크에서 등장합니다. 맥락은 달라져도 같은 질문이 반복됩니다. 무엇이 연결되어 있는가, 어디까지 도달할 수 있는가, 그리고 고리는 어디에 있는가?

그래서 그래프 이론은 이산수학과 컴퓨터 과학에서 모두 초반에 배우는 주제가 됩니다.

비슷한 그래프를 직접 해보기

정점 $P$, $Q$, $R$, $S$ 네 개를 그려 보세요. 그리고 간선 $PQ$, $QR$, $RS$, $SP$를 추가하세요.

그다음 세 가지 질문에 답해 보세요. 각 정점의 차수는 얼마인가, 그래프는 연결되어 있는가, 그리고 이 그래프에는 사이클이 있는가?