그래프 이론 기본 개념: 용어 경로 행렬 표현 기준 잡기

핵심 정의와 기호

G=(V,E)는 정점 집합 V와 간선 집합 E로 이루어진 그래프입니다. 먼저 자기 고리와 같은 두 정점 사이의 중복 간선이 없는 단순 무방향 그래프를 기본으로 합니다. 무방향 간선 {A,B}는 순서를 구분하지 않고 방향 간선 (A,B)는 A→B를 뜻합니다.

용어	이 글의 기준
차수 deg(v)	무방향 단순 그래프에서 v에 닿는 간선 수
보행 walk	간선을 따라 이동하며 정점·간선 반복 허용
경로 path	정점을 반복하지 않는 보행
사이클 cycle	시작·끝만 같고 나머지 정점은 반복하지 않는 닫힌 보행
연결	모든 두 정점 사이에 경로가 있음
가중치	간선에 붙인 비용·거리 등 수치

단순 무방향 사이클은 길이가 최소 3입니다. 방향 그래프에서는 들어오는 차수와 나가는 차수를 구분합니다. 자기 고리를 허용하는 무방향 그래프에서는 고리가 차수에 2를 더하므로 기본 범위와 구별합니다.

가장 작은 예제

V={A,B,C}, E={{A,B},{B,C}}이면 A−B−C는 경로입니다. A와 C는 직접 이웃이 아니지만 경로가 있으므로 그래프는 연결되어 있습니다. 차수는 A:1,B:2,C:1입니다.

정점 순서를 A,B,C로 고정한 인접 행렬입니다.

출발/도착	A	B	C
A	0	1	0
B	1	0	1
C	0	1	0

무방향이어서 행렬은 대각선을 기준으로 대칭입니다. 인접 리스트로는 A:[B], B:[A,C], C:[B]이며 같은 연결을 다른 방식으로 저장한 것입니다.

헷갈리는 반례

정점 4개·간선 3개라고 항상 트리는 아닙니다. A,B,C 사이 삼각형과 고립 정점 D를 두면 간선은 3개지만 연결되지 않고 사이클도 있습니다. 트리는 연결되고 사이클이 없는 무방향 그래프입니다. 기본 범위의 정점 3개·간선 2개 그래프는 모두 트리이므로 그것을 반례로 쓰면 안 됩니다.

손으로 풀어보기

A→B와 B→C만 있는 팔로우 관계라면 인접 행렬은 [[0,1,0],[0,0,1],[0,0,0]]입니다. A에서 C로 갈 수 있지만 C에서 A로는 갈 수 없습니다. 친구 관계처럼 양방향으로 모델링하면 위 대칭 행렬이 됩니다. 방향을 지운 것이 같은 질문에 답하는 모델인지 먼저 확인합니다.

선택: JavaScript로 검산하기

코드 직접 실행

본문 예제를 선택하고 실제 계산 결과를 확인합니다.

예제 크게 보기 (새 탭)

손풀이 뒤 선택해서 실행하는 짧은 전체 코드입니다. 브라우저 Console 또는 Node.js가 준비된 환경의 check.mjs에서 실행할 수 있으며 수학 학습에 설치는 필수가 아닙니다.

const vertices = ['A', 'B', 'C'];
const matrix = [
  [0, 1, 0],
  [1, 0, 1],
  [0, 1, 0],
];
console.log(vertices, matrix);

기대 결과: 정점 순서 [‘A’,’B’,’C’]와 위 무방향 인접 행렬이 출력됩니다.

원문 예제는 이미 작성한 행렬을 출력해 비교하는 용도이며 경로 탐색 알고리즘을 실행한 것은 아닙니다.

자주 발생하는 오해와 교정

직접 간선이 없다는 사실과 경로가 없다는 사실은 다릅니다. 간선 수만 세어 트리라고 판정하지 말고 연결성과 사이클을 확인합니다. 방향을 제거하면 도달 가능성이 달라질 수 있습니다.

직접 풀어볼 문제와 해설

쉬운 개념

무방향 그래프의 간선 {A,B}는 A와 B 양쪽에 한 번씩 닿습니다. 따라서 모든 정점 차수의 합은 간선 수의 두 배입니다.

단계별 예제

1. V={A,B,C,D}, E={AB,BC,CD,DA}인 사각형을 그립니다.
2. 각 정점의 차수는 2이므로 차수 합은 8입니다.
3. 간선은 4개라 2|E|=8로 일치합니다.

직접 풀 문제

이 그래프에 대각선 AC를 하나 추가하면 각 정점의 차수와 차수 합은 어떻게 되나요? 그래프는 연결되어 있나요?

정답·해설 보기

1. A와 C의 차수는 3, B와 D의 차수는 2가 됩니다.
2. 차수 합은 3+2+3+2=10이고 간선 5개에 대해 2|E|=10입니다.
3. 사각형의 경로들이 남아 있으므로 연결되어 있습니다.

다음 학습

11회차에서 간선 전체 방문·정점 전체 방문·최소 비용을 서로 구분합니다. 다음 글 읽기

학습 완료 체크리스트

• 정의의 적용 범위와 기호를 말로 설명할 수 있습니다.
• 위 손풀이를 답을 가린 상태에서 다시 계산합니다.
• 반례가 어떤 조건을 어기는지 설명합니다.

알고리즘 수학 노트

누적 이전 체크포인트: discrete-step-09-matrix. 아래는 이번 회차의 완성 예시입니다. 자신의 다른 예제 하나를 덧붙여도 좋습니다.

사용자를 정점으로, 친구·팔로우를 각각 무방향·방향 간선으로 모델링합니다. 정점 순서를 먼저 고정한 뒤 표의 (i,j)에 연결 여부를 넣습니다. 경로 A−B−C와 직접 간선 AC의 차이, 차수 (1,2,1), 연결·사이클 반례를 기록합니다. 다음 회차는 무엇을 방문하고 무엇을 최소화하는지 구분합니다.

완료 체크포인트

discrete-step-10-graph

다음 학습

평면 그래프와 다익스트라: 오일러 해밀턴 경로 이해하기에서 다음 개념을 이어갑니다.