이 글에서 정리하는 내용
저는 그래프 이론 9강에서 처음 헷갈리기 쉬운 용어, 워크·트레일·경로의 차이, 완전 그래프·이분 그래프·정규 그래프의 판별 기준, 그리고 발생 행렬·인접 행렬·인접 리스트 표현 방법까지 한 흐름으로 정리하겠습니다. 이 글을 끝까지 읽으면 그래프 그림을 보고 핵심 개념을 스스로 판별하고, 같은 그래프를 여러 방식으로 바꾸어 표현하는 연습까지 할 수 있습니다.
그래프를 시작할 때 먼저 알아야 할 기본 용어
저는 그래프를 처음 배울 때 가장 먼저 그래프가 무엇인지부터 짧고 정확하게 잡는 편이 이해가 빨랐습니다. 그래프는 꼭지점과 변으로 이루어진 구조입니다. 꼭지점은 대상이고, 변은 그 대상 사이의 연결입니다. 이 기본 틀만 머릿속에 들어오면 이후에 나오는 인접, 발생, 차수, 부분 그래프 같은 용어도 자연스럽게 연결됩니다.
가장 먼저 보는 기본 표기
G = (V, E)
V = {A, B, C, D}
E = {AB, AC, BC, CD}
|V| = 4
|E| = 4이 표기는 그래프를 가장 기본적으로 적는 방식입니다. G는 그래프 전체를 뜻하고, V는 꼭지점 집합, E는 변 집합을 뜻합니다. 그래서 G = (V, E)는 그래프가 꼭지점과 변으로 이루어졌다는 뜻입니다.
예를 들어 V에 A, B, C, D 네 개의 꼭지점이 있고, E에 AB, AC, BC, CD 네 개의 변이 있으면 이 그래프는 꼭지점 4개와 변 4개를 가진 구조가 됩니다. 시험에서는 |V|와 |E|가 각각 무엇을 세는지 정확히 구분하는 문제가 자주 나옵니다.
기호 읽는 방법도 함께 익히기
V : 꼭지점 집합
E : 변 집합
G = (V, E) : 그래프 G는 꼭지점 집합 V와 변 집합 E로 이루어진다
|V| : 꼭지점의 개수
|E| : 변의 개수
K_n : 꼭지점이 n개인 완전 그래프
deg(v) : 꼭지점 v의 차수그래프 단원에서는 기호가 갑자기 많아져서 개념보다 기호 읽기에서 막히는 경우가 많습니다. 저는 V를 꼭지점, E를 변, |V|를 꼭지점 개수처럼 읽는 습관을 먼저 들이는 것이 훨씬 효율적이라고 봅니다.
특히 Kₙ은 완전 그래프를 뜻하고, deg(v)는 꼭지점 v에 연결된 변의 수인 차수를 뜻합니다. 루프가 있을 때는 차수 계산에서 2로 세는 점도 같이 기억해 두면 좋습니다.
인접, 발생, 루프, 병렬 변, 고립 정점
A --- B
| \
| \
C C
A와 B는 인접하다
변 AB는 A와 B에 발생한다
A에서 A로 이어지는 변은 루프다
같은 두 꼭지점을 잇는 변이 여러 개면 병렬 변이다
어떤 변과도 연결되지 않은 꼭지점은 고립 정점이다인접은 꼭지점끼리 연결되어 있다는 뜻이고, 발생은 변이 어떤 꼭지점에 닿아 있다는 뜻입니다. 두 말이 비슷해 보여도 기준이 다릅니다. 인접은 꼭지점과 꼭지점의 관계이고, 발생은 변과 꼭지점의 관계입니다.
또한 같은 꼭지점 하나를 다시 잇는 변은 루프, 같은 두 꼭지점을 잇는 변이 둘 이상이면 병렬 변입니다. 아무 변도 닿지 않은 꼭지점은 고립 정점입니다. 저는 이 다섯 용어를 한 묶음으로 외우는 편이 훨씬 정리가 잘 되었습니다.
워크, 트레일, 경로를 어떻게 구분할까
이 부분은 그래프 단원에서 가장 자주 섞이는 구간입니다. 이름은 비슷하지만 금지되는 대상이 다릅니다. 저는 이 차이를 “무엇을 반복해도 되는가”로 구분하면 빠르게 정리된다고 느꼈습니다.
같은 예시로 한 번에 비교하기
예시 그래프
A --- B --- D
\ /
\ /
C
워크 예시 : A - B - C - B - D
트레일 예시 : A - B - C - D
경로 예시 : A - C - B - D워크는 가장 넓은 개념입니다. 꼭지점과 변을 따라 이동하기만 하면 되므로 꼭지점이나 변의 반복이 허용될 수 있습니다. 그래서 A – B – C – B – D처럼 중간에 B를 다시 지나가도 워크가 될 수 있습니다.
트레일은 변을 반복하지 않는 워크입니다. 즉, 지나간 변을 다시 쓰면 안 됩니다. 경로는 꼭지점을 반복하지 않는 형태로 이해하면 됩니다. 그래서 경로는 트레일보다 더 엄격한 개념이라고 정리하면 헷갈림이 줄어듭니다.
워크, 트레일, 경로를 시험에서 구분하는 기준
워크 : 반복 허용 가능
트레일 : 같은 변 반복 금지
경로 : 같은 꼭지점 반복 금지시험에서 이 셋을 구분할 때는 길게 생각할 필요가 없습니다. 먼저 같은 변을 두 번 썼는지 보고, 아니라면 같은 꼭지점을 다시 지났는지를 보면 됩니다. 이 순서로 확인하면 대부분의 문제가 정리됩니다.
저는 워크를 가장 큰 상자, 트레일을 그 안의 더 좁은 상자, 경로를 가장 엄격한 상자로 이해했습니다. 이 구조로 기억하면 세 정의를 따로 외우지 않아도 됩니다.
연결 그래프와 연결 성분
연결 그래프 예시
A --- B --- C --- D
연결되지 않은 예시
A --- B C --- D
연결 성분 : 서로 도달 가능한 꼭지점끼리 묶인 덩어리두 꼭지점 사이에 경로가 있으면 서로 연결되어 있다고 말합니다. 그래프 전체가 하나의 덩어리처럼 이어져 있으면 연결 그래프입니다. 반대로 서로 닿을 수 없는 부분이 나뉘어 있으면 여러 연결 성분으로 분리되어 있다고 봅니다.
이 개념은 이후 탐색 알고리즘을 배울 때도 매우 중요합니다. 그래프가 한 번에 전부 이어져 있는지, 아니면 몇 개의 부분으로 나뉘는지를 파악하는 기준이 되기 때문입니다.
그래프의 종류를 판별하는 기준
그래프 종류 문제는 이름을 외우는 것보다 판별 기준을 눈에 익히는 것이 훨씬 중요합니다. 저는 완전 그래프, 이분 그래프, 정규 그래프를 각각 “전부 연결”, “두 편으로 분리”, “차수 동일”이라는 짧은 말로 잡아 두는 편이 기억에 남았습니다.
완전 그래프, 이분 그래프, 정규 그래프 비교
완전 그래프
모든 꼭지점이 다른 모든 꼭지점과 연결됨
예: K_4
이분 그래프
꼭지점을 두 집합으로 나눌 수 있고
같은 집합 내부에는 변이 없음
정규 그래프
모든 꼭지점의 차수가 같음
예: 모든 꼭지점의 차수가 2이면 2-정규 그래프완전 그래프는 말 그대로 빠짐없이 연결된 그래프입니다. 꼭지점이 n개이면 Kₙ으로 적습니다. 예를 들어 K₄는 4개의 꼭지점이 서로 모두 연결된 형태입니다.
이분 그래프는 꼭지점을 두 그룹으로 나눌 수 있고, 변은 반드시 서로 다른 그룹 사이에만 놓입니다. 같은 그룹 안에서 변이 하나라도 생기면 이분 그래프가 아닙니다. 정규 그래프는 모든 꼭지점의 차수가 같은 그래프입니다. 즉, 연결 개수가 모두 같아야 합니다.
| 종류 | 판별 기준 |
|---|---|
| 완전 그래프 | 모든 꼭지점 쌍이 서로 연결됨 |
| 이분·정규 그래프 | 두 집합 분리 가능 / 모든 꼭지점 차수 동일 |
단순 그래프와 부분 그래프도 함께 정리하기
단순 그래프
루프가 없다
병렬 변이 없다
부분 그래프
원래 그래프의 꼭지점과 변 일부만 골라 만든 그래프
신장 부분 그래프
꼭지점은 모두 유지하고 변만 일부 선택한 그래프단순 그래프는 시험에서 기본 조건처럼 자주 등장합니다. 루프도 없고 병렬 변도 없는 무향 그래프라는 점을 바로 떠올릴 수 있어야 합니다. 완전 그래프나 인접 행렬 성질을 설명할 때도 단순 그래프라는 조건이 자주 붙습니다.
부분 그래프는 원래 그래프에서 일부만 떼어낸 구조이고, 신장 부분 그래프는 꼭지점은 그대로 두고 변만 일부 남긴 경우입니다. 저는 이 둘을 비교할 때 “꼭지점까지 줄었는가, 꼭지점은 유지되는가”를 기준으로 구분합니다.
그래프를 행렬과 리스트로 표현하는 방법
그래프를 그림으로만 이해하면 문제를 풀 때는 괜찮지만, 자료구조나 알고리즘으로 넘어갈 때 표현 방식이 중요해집니다. 이 단원에서는 발생 행렬, 인접 행렬, 인접 리스트를 꼭 구분해서 볼 필요가 있습니다. 셋 다 그래프를 표현하지만 무엇과 무엇의 관계를 적는지가 다릅니다.
발생 행렬은 정점과 변의 관계를 적는다
그래프
V = {A, B, C}
E = {e1 = AB, e2 = AC, e3 = BC}
발생 행렬
e1 e2 e3
A 1 1 0
B 1 0 1
C 0 1 1발생 행렬은 행에 꼭지점, 열에 변을 놓습니다. 그리고 어떤 꼭지점이 어떤 변에 닿아 있으면 1, 아니면 0으로 적습니다. 그래서 발생 행렬은 정점과 변 사이의 관계를 기록하는 표라고 이해하면 됩니다.
꼭지점 개수가 |V|개이고 변 개수가 |E|개이면 발생 행렬의 크기는 |V| × |E|가 됩니다. 이 차원 자체가 인접 행렬과 다르므로, 크기부터 구분하면 실수가 줄어듭니다.
인접 행렬은 정점과 정점의 관계를 적는다
같은 그래프의 인접 행렬
A B C
A 0 1 1
B 1 0 1
C 1 1 0인접 행렬은 행과 열 모두 꼭지점으로 두고, 서로 연결되어 있으면 1, 아니면 0을 적습니다. 무향 단순 그래프에서는 대칭 행렬이 되며, 자기 자신과의 연결이 없으므로 대각 원소는 0이 됩니다.
즉, 발생 행렬은 정점-변 관계, 인접 행렬은 정점-정점 관계입니다. 저는 이 차이를 “열에 무엇을 쓰는가”로 기억하면 빠르게 구분된다고 느꼈습니다.
인접 리스트는 각 꼭지점 옆에 이웃을 적는다
인접 리스트
A : B, C
B : A, C
C : A, B인접 리스트는 각 꼭지점에 연결된 꼭지점들을 순서대로 적는 방식입니다. 표처럼 한눈에 보기 좋기보다는 실제로 저장하고 순회할 때 효율적인 형태로 자주 등장합니다.
같은 그래프라도 그림, 발생 행렬, 인접 행렬, 인접 리스트로 모두 바꿔 적을 수 있어야 합니다. 그래프 단원은 정의를 외우는 데서 끝나는 것이 아니라, 한 표현을 다른 표현으로 옮기는 연습이 핵심입니다.
정리
저는 그래프 이론 9강을 공부할 때 용어를 따로따로 외우기보다 하나의 예시 그래프를 계속 바꿔 보며 정리하는 방식이 가장 효과적이었습니다. 그래프는 꼭지점과 변으로 이루어지고, 인접과 발생은 관계의 기준이 다르며, 루프·병렬 변·고립 정점은 그래프의 특수한 상태를 설명하는 용어입니다.
또한 워크는 가장 넓은 이동 개념이고, 트레일은 변을 반복하지 않으며, 경로는 꼭지점을 반복하지 않습니다. 완전 그래프는 전부 연결된 그래프, 이분 그래프는 두 집합으로 나뉘는 그래프, 정규 그래프는 모든 꼭지점의 차수가 같은 그래프입니다. 마지막으로 발생 행렬은 정점과 변의 관계, 인접 행렬은 정점과 정점의 관계, 인접 리스트는 각 꼭지점의 이웃 목록을 적는 방식이라는 점만 정확히 잡아도 이 단원 전체가 훨씬 정돈됩니다.
많이 받는 질문
Q. 워크와 경로는 정확히 무엇이 다른가요?
워크는 이동 자체가 가능한 순서라면 폭넓게 허용되는 개념입니다. 반면 경로는 같은 꼭지점을 다시 지나가지 않는 더 엄격한 형태입니다. 그래서 시험에서는 먼저 반복된 꼭지점이 있는지 확인하면 경로 여부를 빠르게 판별할 수 있습니다.
Q. 발생 행렬과 인접 행렬이 자꾸 헷갈립니다.
열에 무엇이 오는지 먼저 보시면 됩니다. 발생 행렬은 행이 꼭지점, 열이 변입니다. 인접 행렬은 행과 열이 모두 꼭지점입니다. 즉, 발생 행렬은 정점-변 관계, 인접 행렬은 정점-정점 관계를 기록합니다.
Q. 이분 그래프는 그림만 보고 어떻게 판별하나요?
꼭지점을 두 그룹으로 나눠 보고, 같은 그룹 안에서 연결되는 변이 없는지 확인하시면 됩니다. 모든 변이 서로 다른 두 그룹 사이에만 있으면 이분 그래프입니다. 직접 두 색으로 칠해 본다고 생각하면 판별이 훨씬 쉬워집니다.