연결성·경로·순환

세 가지 질문을 구분하기

0에서 2로 갈 수 있는가, 최소 몇 개 간선이 필요한가, 정확히 두 개 간선을 지나는 보행은 몇 개인가는 서로 다른 문제입니다. 보행은 인접 간선을 잇는 정점열이며 정점이나 간선을 반복할 수 있습니다. 이 단원에서 단순 경로는 정점을 반복하지 않는 보행입니다. 자기 자신까지 길이 0인 경로도 허용합니다.

실습은 세 정점의 가중치 없는 방향 그래프입니다. 간선 마스크 표기는 앞 단원과 같습니다. 주황 간선은 선택한 출발점 s에서 도착점 t까지 찾은 한 최단 경로이며, 가능한 모든 경로를 강조하지는 않습니다.

너비 우선 탐색과 최단 거리

너비 우선 탐색은 출발점을 거리 0으로 놓고, 한 간선으로 갈 수 있는 정점을 먼저 방문한 뒤 거리 2,3,… 순서로 확장합니다. 이미 방문한 정점은 다시 큐에 넣지 않습니다. 처음 정점 v를 발견한 깊이가 최단 거리입니다. 더 짧은 경로가 있었다면 그 이전 깊이에서 발견되었어야 하기 때문입니다.

0→1→2에서 s=0,t=2의 경로는 (0,1,2), 거리는 2입니다. 반대 방향은 도달할 수 없습니다. 도달 불가를 거리 0과 구분하여 —로 표시합니다. s=t이면 간선을 하나도 지나지 않는 경로 (s)가 있으므로 거리는 항상 0입니다.

음수·양수 가중치가 들어가면 간선 수가 작은 경로와 비용이 작은 경로가 다를 수 있습니다. 이 BFS 증명을 가중 최단 경로 알고리즘의 증명으로 사용하지 마세요.

행렬 곱은 보행을 센다

인접행렬의 규약을 Aᵤᵥ=1 iff u→v로 정합니다. 그러면

는 s→v→t인 두 단계 보행을 셉니다. 각 중간 정점 v의 기여를 합하기 때문입니다. 같은 논리와 귀납법으로 (Aᵏ)ₛₜ는 길이 k 보행의 수입니다. A⁰=I는 길이 0 보행을 나타냅니다.

반복 정점을 허용하므로 행렬 거듭제곱은 일반적으로 단순 경로의 수를 세지 않습니다. 예를 들어 0↔1에서는 (A²)₀₀=1이지만 이 보행은 0을 다시 방문합니다. 최단 경로 문제와 고정 길이 보행 수 문제를 분리해야 합니다.

도달성의 논리적 합성

숫자 덧셈·곱셈 대신 OR·AND를 쓰면 행렬 곱은 보행 개수가 아니라 존재 여부를 계산합니다. 표는 자기 자신을 포함한 도달성 관계를 보여 줍니다. 중간 정점 k를 허용할 때

로 갱신합니다. 정점들을 차례대로 중간 정점에 허용하면 유한 그래프의 추이 폐포를 얻습니다. 숫자 개수와 Boolean 존재 판정은 같은 행렬 기호처럼 보이지만 대수가 다릅니다.

약연결성과 강연결성

방향을 지웠을 때 연결이면 약연결입니다. 모든 정점쌍이 서로 도달하면 강연결입니다. 일반 그래프는 서로 도달하는 정점들을 강연결 성분으로 묶을 수 있습니다. 상호 도달 관계는 반사·대칭·추이적이므로 동치류를 만듭니다.

사슬 0→1→2는 약연결이지만 강연결 성분은 세 개입니다. 2→0을 더하면 세 정점이 하나의 강연결 성분이 됩니다. 성분들을 정점 하나씩으로 압축한 그래프는 DAG입니다. 압축 그래프에 순환이 있었다면 해당 성분들은 원래 서로 도달하여 이미 하나의 성분이어야 하기 때문입니다.

AI 시스템에서의 해석

의존성 검사, 지식 그래프의 도달성, 메시지 전달의 k-hop 범위에서 이 구분을 사용합니다. k층 메시지 전달이 정확히 k길이의 모든 단순 경로를 독립적으로 처리한다는 뜻은 아닙니다. 반복·정규화·방향성·self-loop 유무를 명시해야 합니다.

그림의 길이는 비용이 아니고 정점 번호는 좌표가 아닙니다. 실습의 최단 경로는 가중치 없는 방향 간선 개수 기준입니다.

확인 문제와 답

1. 마스크 5의 (A²)₀₀은? 1이며 0→1→0입니다.
2. 빈 그래프에서 d(0,0),d(0,2)는? 0과 도달 불가입니다.
3. 강연결 성분을 압축하면 순환이 남나요? 방향 순환이 없는 DAG가 됩니다.

추가 읽기: MIT Mathematics for Computer Science. 경로와 행렬 곱은 여기 명시한 방향 규약을 따릅니다.