경로 (그래프 이론)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

그래프 이론에서, '''경로'''는 그래프 내에서 꼭짓점들을 잇는 일련의 변들을 의미한다. 경로는 유한 또는 무한 시퀀스로, 유한 경로는 시작점과 종점을 가지며, 무한 경로는 무한히 이어진다. 경로는 같은 꼭짓점을 중복해서 거치지 않으며, 꼭짓점을 중복하는 경우는 트레일, 변까지 중복되는 경우는 워크라고 한다. 또한 유향 그래프에서는 변의 방향을 고려한 유향 경로가 존재하며, 경로의 길이, 가중치 등을 정의할 수 있다. 경로와 관련된 문제로는 최단/최장 경로 문제, k-경로 분할 문제 등이 있으며, 이들은 다양한 알고리즘을 통해 해결될 수 있다.

더 읽어볼만한 페이지

그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.

경로 (그래프 이론)
그래프 이론
종류	이산수학
경로
그래프 이론	그래프의 꼭짓점들을 연결하는 간선들의 순열
관련 주제	오일러 경로 해밀턴 경로 최단 경로 문제 최장 경로 문제 경로 (그래프) 그래프 거리 지오데식 (그래프 이론) 트리비얼 경로

2. 정의

경로는 그래프에서 정점과 변이 번갈아 나타나는 열로, 다음 조건을 만족한다.

유한 경로와 무한 경로가 있다.
경로에서는 같은 꼭짓점을 중복해서 지날 수 없다.
꼭짓점을 중복하지만 변이 중복되지 않는 경우를 '''트레일'''(trail^영어), 변도 중복될 수 있는 경우를 '''보행'''(步行, walk^영어)이라고 한다.

유향 그래프에도 경로가 있으며, 항상 이전 정점에서 다음 정점으로 간선이 향한다. 유향 그래프에서는 '''유향 경로'''(directed path), '''유향 사이클'''(directed cycle)과 같은 용어를 사용한다.

정점이 여러 번 나타나지 않는 경로를 '''단순 경로'''(simple path)라고 하며, 시작점과 끝점을 제외한 정점이 여러 번 나타나지 않는 닫힌 경로를 '''단순 사이클'''(simple cycle)이라고 한다. 최근에는 '단순'이라는 표현을 생략하고 닫힌 경로는 단순 사이클, 경로는 단순 경로를 의미하는 경우가 많지만, 항상 그런 것은 아니다.

경로 상에서 인접하지 않은 정점 사이에 간선이 존재하지 않는 경로를 유도 경로(induced path)라고 한다. 그래프의 모든 정점을 포함하는 단순 닫힌 경로는 해밀턴 사이클이다.

공통 내부 정점을 갖지 않는 두 경로는 서로 '''독립''' 또는 '''내부 정점이 서로소(점소)'''라고 한다. 공통 내부 간선을 갖지 않는 두 경로는 서로 '''변소'''라고 한다.

경로를 구성하는 간선의 수를 경로의 '''길이'''라고 하며, 여러 번 나타나는 간선은 여러 번 계산한다. 정점이 하나뿐인 경우도 경로이며, 이 경우 길이는 0이다.

가중 그래프는 각 간선에 값(가중치)이 대응되는 그래프이다. '''경로의 가중치'''는 경로에 속하는 간선의 가중치의 총합이며, 가중치 대신 비용(cost) 또는 길이라는 표현을 쓰기도 한다.

2. 1. 유한 경로

그래프

G

에서 길이

n\in\mathbb N

인 '''유한 경로'''는 다음 성질을 만족시키는 점렬

v_0,v_1,\dots,v_n

이다.

모든 $i,j=0,\dots,n$ 에 대하여, $v_i=v_j$ 라면 $i=j$ 이다.
모든 $i=0,\dots,n-1$ 에 대하여, $v_i$ 와 $v_{i+1}$ 을 연결하는 변이 존재한다. ( $v_iv_{i+1}\in E(G)$ )

경로는 같은 꼭짓점을 중복해서 거칠 수 없다.

2. 2. 무한 경로

그래프

G

의 '''무한 경로'''는 다음 성질을 만족시키는

V(G)

속의 무한 점렬

v_0, v_1, \dots

이다.

모든 $i, j = 0, \dots$ 에 대하여, $v_i = v_j$ 라면 $i = j$ 이다.
모든 $i = 0, \dots$ 에 대하여, $v_i$ 와 $v_{i+1}$ 을 연결하는 변이 존재한다.

2. 3. 워크, 트레일, 경로

그래프에서 '''워크''', '''트레일''', '''경로'''는 다음과 같이 정의된다.

'''워크'''(walk)는 정점과 변이 번갈아 나타나는 열이다. 변의 중복은 허용되지만, 정점의 중복은 허용될 수도 있고 허용되지 않을 수도 있다.
'''닫힌 워크'''(closed walk)는 시작 정점과 끝 정점이 같은 워크이다.
'''열린 워크'''(open walk)는 시작 정점과 끝 정점이 다른 워크이다.
'''트레일'''(trail)은 변이 중복되지 않는 워크이다. 정점은 중복될 수 있다.
'''경로'''(path)는 모든 정점(따라서 모든 변)이 서로 다른 트레일이다.^[1]

예를 들어, 다음과 같은 그래프에서,

HAB와 HDG는 경로이다.
BDEFDC는 꼭짓점 D가 반복되므로 경로가 아니지만 트레일이다.
BDEFDB는 변 BD가 반복되므로 트레일이 아니지만 워크이다.

일부 저자는 모든 정점이 서로 다른 경로를 '''단순 경로'''(simple path)라고 부르며, 경로라는 용어를 사용할 때는 정점의 중복을 허용하기도 한다.^[2]

가중 그래프에서는 워크, 트레일, 경로의 ''가중치''를 거쳐간 변들의 가중치의 합으로 정의한다. 가중치 대신 ''비용'' 또는 ''길이''라는 단어를 사용하기도 한다.

2. 4. 유향 경로

'''유향 워크'''(Directed walk)는 유향 그래프에서 정점의 시퀀스를 연결하는, 동일한 방향으로 향하는 변의 유한 또는 무한 시퀀스이다.

:를 유향 그래프라고 하자. 유한 유향 워크는 정점 시퀀스 가 존재하여 for 인 변의 시퀀스 이다. 은 유향 워크의 ''정점 시퀀스''이다. 유향 워크는 ''v''₁ = ''v''_''n''이면 ''닫힌'' 것이고, 그렇지 않으면 ''열린'' 것이다. 무한 유향 워크는 여기서 설명된 것과 동일한 유형의 변 시퀀스이지만 첫 번째 또는 마지막 정점이 없고, 반무한 유향 워크(또는 반직선)는 첫 번째 정점은 있지만 마지막 정점은 없다.

'''유향 트레일'''(Directed trail)은 모든 변이 서로 다른 유향 워크이다.
'''유향 경로'''(Directed path) 또는 '''단순 유향 경로'''(Simple directed path)는 모든 정점이 서로 다른 유향 트레일이다.

만약 이 정점 시퀀스 를 갖는 유한 유향 워크이면, ''w''는 ''v''₁ ''에서'' ''v''_''n''''까지의 걷기''라고 한다. 유향 경로 또는 유향 단순 경로의 경우도 마찬가지이다. 두 개의 ''구별되는'' 정점 사이에 유한 유향 워크가 있다면, 그들 사이에는 유한 유향 경로와 유한 유향 단순 경로도 있다.

가중 유향 그래프는 유향 그래프의 모든 변에 값을 ('가중치') 연결한다. 가중 유향 그래프에서 ''유향 워크'' (또는 유향 경로 또는 유향 단순 경로)의 ''가중치''는 통과한 변의 가중치의 합이다. 가끔 가중치 대신 ''비용'' 또는 ''길이''라는 단어가 사용된다.

3. 종류

그래프는 각 정점 쌍을 포함하는 경로가 있는 경우 연결되어 있다고 한다. 유향 그래프는 각 정점 쌍을 포함하는 반대 방향의 유향 경로가 있는 경우 강하게 연결되어 있다고 한다. 두 경로는 내부 정점이나 변을 공유하지 않는 경우 ''정점 독립적'' (또는 ''내부적으로 분리'' 또는 ''내부적으로 정점 분리'')이라고 한다. 마찬가지로, 두 경로는 변을 공유하지 않는 경우 ''변 독립적'' (또는 ''변 분리'')이라고 한다. 두 개의 내부적으로 분리된 경로는 변 분리적이지만, 그 반대는 반드시 참이 아니다. 그래프에서 두 정점 사이의 거리는, 만약 존재한다면, 두 정점 사이의 최단 경로의 길이이며, 그렇지 않은 경우 거리는 무한대이다. 연결 그래프의 지름은 그래프의 정점 쌍 간의 가장 큰 거리이다.

3. 1. 단순 경로와 사이클

정점이 여러 번 나타나지 않는 경로를 '''단순 경로'''(en: simple path)라고 부르며, 시점/종점을 제외한 정점이 여러 번 나타나지 않는 닫힌 경로를 '''단순 사이클'''(en: simple cycle)이라고 부른다. 최근에는 "simple"(단순)은 처음부터 함의되어 있는 경우가 많아, 닫힌 경로라고 하면 단순 사이클을 의미하고, 경로라고 하면 단순 경로를 의미한다.

하지만 항상 그런 의미로 사용되는 것은 아니다. 서적에 따라서는 정점이 반복되는 경로를 '''워크'''(en: walk)라고 부르며, 여기서 말하는 단순 경로를 '''경로'''(path)라고 부른다. 워크에서 간선의 반복을 제거한 것을 '''트레일'''(trail)이라고 한다. 트레일은 정점의 반복을 허용하지만, 간선은 반복할 수 없다.

3. 2. 유도 경로

경로 상에서 인접하지 않은 정점 사이에 간선이 존재하지 않는 경로를 유도 경로라고 한다.

3. 3. 해밀턴 경로

그래프의 모든 정점을 반복 없이 포함하는 경로는 해밀턴 경로라고 한다.

4. 성질

그래프에서 경로와 관련된 성질은 다음과 같다.

연결성: 그래프의 각 정점 쌍을 잇는 경로가 존재하면 연결되어 있다고 한다. 유향 그래프에서는 각 정점 쌍을 잇는 반대 방향의 유향 경로가 존재하면 강하게 연결되어 있다고 한다.

정점/변 독립: 두 경로가 내부 정점이나 변을 공유하지 않으면 '정점 독립적'(또는 '내부적으로 분리')이라고 한다. 두 경로가 변을 공유하지 않으면 '변 독립적'(또는 '변 분리')이라고 한다. 내부적으로 분리된 두 경로는 변 분리적이지만, 그 반대는 항상 참이 아니다. 공통 내부 정점을 갖지 않는 두 경로는 서로 "독립" 또는 "내부 정점이 서로소(점소)"라고 한다. 또한 공통 내부 간선을 갖지 않는 두 경로는 서로 "변소"라고 한다.

거리: 그래프에서 두 정점 사이의 거리는 두 정점 사이의 최단 경로의 길이이며, 경로가 없으면 거리는 무한대이다.^[1] 연결 그래프의 지름은 그래프의 모든 정점 쌍 사이의 거리 중 가장 큰 값이다.^[1]

4. 1. 연결성

그래프는 각 정점 쌍을 포함하는 경로가 있으면 연결되어 있다고 한다. 유향 그래프는 각 정점 쌍을 포함하는 반대 방향의 유향 경로가 있으면 강하게 연결되어 있다고 한다.

4. 2. 정점/변 독립

두 경로는 내부 정점이나 변을 공유하지 않는 경우 '''정점 독립적''' (또는 '''내부적으로 분리''' 또는 '''내부적으로 정점 분리''')이라고 한다. 마찬가지로, 두 경로는 변을 공유하지 않는 경우 '''변 독립적''' (또는 '''변 분리''')이라고 한다. 두 개의 내부적으로 분리된 경로는 변 분리적이지만, 그 반대는 반드시 참이 아니다. 공통 내부 정점을 갖지 않는 두 경로는 서로 "'''독립'''", 또는 "내부 정점이 서로소(점소)"라고 한다. 또한, 공통 내부 간선을 갖지 않는 두 경로는 서로 "'''변소'''"라고 한다.

4. 3. 거리

그래프에서 두 정점 사이의 거리는 두 정점 사이의 최단 경로의 길이이며, 만약 존재하지 않는 경우 거리는 무한대이다.^[1] 연결 그래프의 지름은 그래프의 정점 쌍 간의 가장 큰 거리이다.^[1]

5. 알고리즘

그래프에서 최단 및 최장 경로를 찾는 여러 알고리즘이 존재하며, P≠NP를 가정하면 최단 경로를 찾는 것이 최장 경로를 찾는 것보다 계산적으로 훨씬 쉽다.

데이크스트라 알고리즘은 음이 아닌 가중치를 가진 그래프에서, 벨만-포드 알고리즘은 음의 가중치를 가진 그래프에서 최단 경로를 찾을 수 있다. 플로이드-워셜 알고리즘은 모든 정점 쌍 사이의 최단 경로를 찾는 데 사용된다.

5. 1. 최단 경로 문제

그래프에서 두 정점 사이의 최단 경로를 찾는 문제이다. 한국 내 내비게이션 시스템, 대중교통 경로 안내 등에 활용된다.

데이크스트라 알고리즘: 음이 아닌 가중치를 가진 그래프에서 최단 경로를 찾는 알고리즘이다.^[1]
벨만-포드 알고리즘: 음의 가중치를 가진 그래프에서 최단 경로를 찾는 알고리즘이다.^[1]
플로이드-워셜 알고리즘: 모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘이다.^[1]

5. 2. 최장 경로 문제

최장 경로 문제는 그래프에서 주어진 두 정점 사이의 가장 긴 경로를 찾는 문제이다. P≠NP를 가정하면, 최장 경로를 찾는 것은 최단 경로 문제보다 계산적으로 더 어렵다. 최단 경로 문제와는 달리, 최장 경로 문제는 다항 시간 내에 해결하는 효율적인 알고리즘이 알려져 있지 않다.

데이크스트라 알고리즘은 음이 아닌 가중치를 가진 방향 그래프 및 무방향 그래프에서 출발 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 데 사용될 수 있다. 벨만-포드 알고리즘은 음의 가중치를 가진 방향 그래프에도 적용할 수 있다. 플로이드-워셜 알고리즘은 가중치가 있는 방향 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 데 사용될 수 있다.

5. 3. K-경로 분할 문제

'''k-경로 분할''' 문제는 주어진 그래프를 길이가 최대 ''k''인 정점 분리 경로들의 가장 작은 집합으로 분할하는 문제이다.^[1]

6. 예시

다음은 그래프에서 경로, 트레일, 워크의 예시이다.

HAB와 HDG는 경로이다.
BDEFDC는 꼭짓점 D가 반복되므로 경로가 아니지만 트레일이다.
BDEFDB는 변 BD가 반복되므로 트레일이 아니지만 워크이다.

참조

_[1] 논문 An improved approximation algorithm for the minimum 3-path partition problem https://doi.org/10.1[...] 2019-07-01
_[2] 서적 Graph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991 https://books.google[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com