경로 (그래프 이론)

그래프 이론에서 경로(經路, 영어: path)는 보통 그래프 안의 보행 가운데 꼭짓점을 반복하지 않는 것이다. 즉, 한 꼭짓점에서 다른 꼭짓점으로 변들을 따라 이동하되 같은 꼭짓점을 두 번 이상 지나지 않는 열이다. 유향 그래프에서 각 변의 방향을 따라가는 경로는 유향 경로라고 한다. 경로는 연결성, 거리, 순환, 나무, 해밀턴 경로 등의 개념을 정의하는 그래프 이론의 기본 대상이다.

정의

그래프에서 보행, 자취, 경로, 순환, 회로의 예(왼쪽 위에서부터 오른쪽 아래 방향). 화살표는 보행이 거치는 꼭짓점의 순서를 의미한다.

경로의 정의는 보통 보행과 자취의 개념과 함께 서술한다. 엄밀히는 변의 열과 꼭짓점의 열을 함께 적는 것이 가장 일반적이지만, 단순 그래프에서는 각 단계의 변이 양 끝점으로 결정되므로 꼭짓점의 열만 적어도 충분하다.

보행, 자취, 경로

그래프 $G$의 유한 보행(영어: walk)은

$v_{0},e_{1},v_{1},e_{2},\dots ,e_{n},v_{n}$

과 같은 유한열로서, 각 $i=1,\dots ,n$에 대하여 변 $e_{i}$의 양 끝점이 $v_{i-1}$와 $v_{i}$인 것을 말한다. 단순 그래프에서는 보통

$v_{0},v_{1},\dots ,v_{n}$

처럼 꼭짓점열만 적는다. 이때 보행의 길이는 포함된 변의 수인 $n$이다.

유한 보행에서 모든 변이 서로 다르면 이를 자취(영어: trail)라고 한다. 또한 모든 꼭짓점이 서로 다르면 이를 경로라고 한다. 즉, 경로는 꼭짓점을 반복하지 않는 자취이다. 단순 그래프에서는 꼭짓점이 반복되지 않으면 변도 자동으로 반복되지 않으므로, 경로는 꼭짓점열

$v_{0},v_{1},\dots ,v_{n}$

으로 정의해도 무방하다.

길이가 0인 경로는 꼭짓점 하나만으로 이루어진다. 길이가 1인 경로는 서로 인접한 두 꼭짓점과 그 사이의 변으로 이루어진다. 경로

$v_{0},v_{1},\dots ,v_{n}$

에서 $v_{0}$와 $v_{n}$을 그 경로의 끝점이라고 하고, 나머지 꼭짓점들

$v_{1},\dots ,v_{n-1}$

을 내부 꼭짓점이라고 한다.

특히 $v_{0}=u$, $v_{n}=v$이면, 이 경로를 꼭짓점 $u$에서 $v$로 가는 경로 또는 $u$와 $v$를 연결하는 경로라고 한다.

문헌에 따라서는 현재 이 문서에서 말하는 경로를 단순 경로(영어: simple path)라고 부르고, “경로”라는 말을 보다 느슨하게 쓰는 경우도 있다. 그러나 그래프 이론의 입문 문헌에서는 보통 꼭짓점을 반복하지 않는 열을 경로라고 한다.

유향 경로

유향 그래프 $G$의 유한 유향 보행은

$v_{0},e_{1},v_{1},e_{2},\dots ,e_{n},v_{n}$

과 같은 유한열로서, 각 $i=1,\dots ,n$에 대하여

$e_{i}=(v_{i-1},v_{i})$

인 것을 말한다. 즉, 각 변은 항상 이전 꼭짓점에서 다음 꼭짓점으로 향해야 한다. 단순한 경우에는 마찬가지로

$v_{0},v_{1},\dots ,v_{n}$

과 같은 꼭짓점열만 적는다.

유향 보행에서 모든 변이 서로 다르면 유향 자취이라고 하고, 모든 꼭짓점이 서로 다르면 유향 경로(영어: directed path)라고 한다. 따라서 유향 경로는 꼭짓점을 반복하지 않으면서, 각 변의 방향을 거슬러 가지 않는 경로이다.

무한 경로

그래프 $G$의 무한 경로는

$v_{0},v_{1},v_{2},\dots$

와 같은 무한 꼭짓점열로서, 모든 꼭짓점이 서로 다르고, 모든 $i\geq 0$에 대하여 $v_{i}$와 $v_{i+1}$가 인접한 것을 말한다. 유향 그래프의 경우에는 각 $(v_{i},v_{i+1})$가 유향 변이어야 한다.

문헌에 따라서는 양쪽으로 무한히 뻗는

$\dots ,v_{-1},v_{0},v_{1},\dots$

와 같은 열도 무한 경로로 다룬다. 다만 그래프 이론의 기초적인 논의에서는 보통 유한 경로를 중심으로 다루며, 필요할 때 무한 경로를 별도로 언급한다.

관련 개념

거리와 연결성

그래프의 두 꼭짓점 $u$와 $v$ 사이의 거리 $d(u,v)$는 $u$와 $v$를 연결하는 경로들 가운데 길이가 가장 짧은 것의 길이이다. 만약 두 꼭짓점을 연결하는 경로가 없다면, 문맥에 따라 거리를 무한대로 정의하거나 아예 정의하지 않기도 한다.

그래프의 임의의 두 꼭짓점 사이에 항상 경로가 존재하면 이를 연결 그래프라고 한다. 따라서 경로의 존재 여부는 그래프가 연결되어 있는지를 판단하는 가장 기본적인 기준이다.

유향 그래프에서는 임의의 두 꼭짓점 $u$, $v$에 대하여 $u$에서 $v$로 가는 유향 경로와 $v$에서 $u$로 가는 유향 경로가 모두 존재하면, 그 유향 그래프를 강하게 연결되었다(영어: strongly connected)고 한다.

연결 그래프의 지름(영어: diameter)은 그래프의 두 꼭짓점 사이의 거리들 가운데 최댓값이다. 따라서 지름은 그래프가 전체적으로 얼마나 “멀리 퍼져 있는가”를 나타내는 수치이다.

유도 경로와 해밀턴 경로

주어진 그래프 $G$의 유도 부분 그래프인 경로를 유도 경로(영어: induced path)라고 한다. 동치적으로 말하면, 경로의 서로 이웃하지 않은 두 꼭짓점 사이에 원래 그래프 $G$에서 추가적인 변이 없어야 한다. 유도 경로는 경로 자체가 그래프 안에서 “불필요한 지름길 없이” 들어 있는 경우라고 볼 수 있다.

그래프의 모든 꼭짓점을 정확히 한 번씩 지나는 경로를 해밀턴 경로(영어: Hamiltonian path)라고 한다. 해밀턴 경로가 존재하는지 여부는 그래프 이론의 대표적인 문제 가운데 하나이며, 그래프 전체를 하나의 긴 경로로 덮을 수 있는지를 묻는 문제로 이해할 수 있다.

한편 모든 변을 정확히 한 번씩 지나는 것은 경로가 아니라 오일러 경로의 개념과 관련되며, 이는 경로와는 다른 조건이다. 현재 문서의 경로는 꼭짓점의 반복 여부를 기준으로 정의된다는 점에서 오일러 경로와 구별된다.

서로소 경로

두 경로가 내부 꼭짓점을 공유하지 않으면 이를 내부 꼭짓점이 서로소인 경로 또는 꼭짓점-서로소 경로라고 한다. 또한 두 경로가 공통된 변을 갖지 않으면 변-서로소 경로라고 한다.

이러한 개념은 그래프의 연결성이 얼마나 강한지를 정량적으로 표현할 때 중요하다. 예를 들어 어떤 두 꼭짓점 사이에 서로소인 경로가 여러 개 존재한다는 것은, 일부 꼭짓점이나 변이 제거되어도 두 꼭짓점이 계속 연결될 가능성이 높다는 뜻이다. 이와 관련하여 멩거의 정리가 중요한 역할을 한다.

경로 탐색 문제

그래프 이론과 알고리즘에서는 두 꼭짓점 사이의 경로를 찾는 문제를 자주 다룬다. 특히 어떤 기준에서 가장 짧은 경로 또는 가장 긴 경로를 구하는 문제는 중심적인 주제이다.

최단 경로

두 꼭짓점 사이의 최단 경로는 길이가 가장 짧은 경로를 찾는 문제이다. 변에 가중치가 없는 그래프에서는 경로의 길이를 변의 수로 재며, 이 경우 최단 경로의 길이는 두 꼭짓점 사이의 거리와 같다.

가중 그래프에서는 각 변에 가중치가 주어지며, 경로의 가중치는 그 경로가 지나는 모든 변의 가중치의 합으로 정의한다. 이 경우 최단 경로는 변의 수가 아니라 전체 가중치의 합이 최소가 되는 경로를 말한다.

가중치가 없는 그래프에서는 너비 우선 탐색을 이용하여 최단 경로를 찾을 수 있다. 변의 가중치가 모두 0 이상인 경우에는 데이크스트라 알고리즘이 대표적인 방법이며, 음의 가중치가 허용되는 경우에는 벨만-포드 알고리즘을 사용할 수 있다. 모든 꼭짓점 쌍 사이의 최단 경로를 한꺼번에 구하는 문제에는 플로이드-워셜 알고리즘이 널리 쓰인다.

최장 경로

두 꼭짓점 사이의 최장 경로는 가능한 경로들 가운데 길이가 가장 긴 경로를 찾는 문제이다. 여기서 경로는 꼭짓점을 반복할 수 없으므로, 무한히 같은 순환을 도는 식으로 길이를 늘릴 수는 없다.

그러나 일반 그래프에서 최장 경로 문제는 최단 경로 문제보다 계산적으로 훨씬 어렵다. 실제로 최장 경로 문제는 NP-난해한 문제로 알려져 있다. 따라서 최단 경로처럼 일반적인 효율적 알고리즘이 알려져 있지는 않다.

다만 그래프가 유향 비순환 그래프인 경우에는 위상 정렬과 동적 계획법을 이용하여 최장 경로를 효율적으로 구할 수 있다. 이 때문에 최장 경로 문제는 그래프의 종류에 따라 난이도가 크게 달라진다.

같이 보기

• 경로 그래프
• 순환 (그래프 이론)
• 해밀턴 경로
• 오일러 경로
• 최단 경로 문제
• 경로 (위상수학)