유향 비순환 그래프
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
유향 비순환 그래프(DAG)는 사이클이 없는 방향 그래프이다. DAG는 정점과 변으로 구성되며, 변은 한 정점에서 다른 정점으로의 방향을 가진다. DAG는 도달 가능성 관계, 위상 정렬, 조합적 열거 등의 수학적 특성을 가지며, 도달 가능성 관계는 부분 순서로 표현될 수 있다. DAG의 추이 폐쇄와 추이 감소는 그래프의 에지 수를 줄여 시각화를 돕는다. 위상 정렬은 DAG의 정점을 순서대로 정렬하는 것으로, 모든 간선이 순서상 시작 정점에서 끝 정점으로 향하도록 한다. DAG의 개수는 조합적 열거를 통해 계산할 수 있으며, 멀티트리와 폴리트리와 같은 관련 그래프족이 존재한다.
DAG는 위상 정렬, 순환 그래프로부터의 구성, 추이적 폐포 및 축소, 클로저 문제, 경로 알고리즘 등 다양한 계산 문제와 관련된다. DAG는 스케줄링, 데이터 처리 네트워크, 인과 구조, 계보 및 버전 기록, 인용 그래프, 데이터 압축 등 다양한 분야에 응용된다. 예를 들어, 스케줄링 문제에서는 작업 간의 의존성을 표현하고, 데이터 처리 네트워크에서는 데이터 흐름을 모델링하며, 인과 관계를 나타내는 데 사용된다. 또한, 가계도, 버전 관리 시스템, 인용 그래프, 데이터 압축 등에서도 활용된다.
더 읽어볼만한 페이지
- 유향 비순환 그래프 - 하세 도형
하세 도형은 부분 순서 집합의 원소와 피복 관계를 점과 선으로 나타내어 순서 관계를 시각화하는 그래프 도구이며, 격자 이론, 조합론, 소프트웨어 공학 등에서 활용된다. - 유향 그래프 - 강한 연결 요소
강한 연결 요소는 유향 그래프에서 임의의 두 정점 간에 서로 도달 가능한 경로가 존재하는 부분 그래프를 의미하며, 깊이 우선 탐색 등 다양한 알고리즘으로 찾을 수 있고 그래프 이론과 알고리즘 설계에 중요한 개념이다. - 유향 그래프 - 위상정렬
위상 정렬은 방향 그래프의 정점들을 간선 방향에 따라 정렬하는 알고리즘으로, 작업 스케줄링, 의존성 분석 등에 활용되며 방향 비순환 그래프에서만 수행 가능하고, Kahn 알고리즘, 깊이 우선 탐색 등의 구현 방법이 존재하며 스케줄링 문제 해결에 중요한 선행 그래프 분석에 사용됩니다.
| 유향 비순환 그래프 | |
|---|---|
| 개요 | |
| 유형 | 방향 그래프 |
| 속성 | 순환이 없음 |
| 속성 | |
| 위상 정렬 | 가능 |
| 최장 경로 | 다항 시간 |
| 최단 경로 | 다항 시간 |
| 관련 구조 | |
| 종류 | 트리 |
| 다른 종류 | 방향 그래프, 비순환 그래프 |
2. 정의
그래프는 정점과 이들을 연결하는 변으로 구성된다. 방향 그래프의 경우, 각 변은 한 정점에서 다른 정점으로 향하는 방향을 가진다. 방향 그래프에서 경로는 변의 방향을 따라 순서대로 연결된 정점들의 열을 의미하며, 한 변의 끝 정점은 다음 변의 시작 정점과 같다. 만약 경로의 시작 정점과 끝 정점이 같다면, 이 경로는 사이클(cycle)을 형성한다.
유향 비순환 그래프(DAG)는 그래프 이론에서 다양한 수학적 특성을 지닌다. DAG의 정점들은 도달 가능성 관계를 통해 부분 순서를 형성하며, 이는 추이 폐포나 추이 축소와 같은 개념으로 분석될 수 있다. 또한, 모든 DAG는 정점들을 특정 순서로 배열하는 위상 정렬을 가지는데, 이는 DAG의 중요한 특징 중 하나이다. DAG의 개수를 세는 조합론적 열거 문제도 연구 대상이며, 멀티 트리, 폴리 트리, 아보리센스 등 관련된 특수한 형태의 그래프족도 존재한다.
유향 비순환 그래프(Directed Acyclic Graph, DAG)는 이러한 사이클이 존재하지 않는 방향 그래프를 말한다.[1][2][3]
방향 그래프의 어떤 정점 v가 다른 정점 u에서 시작하여 v에서 끝나는 경로가 존재할 때, 정점 v는 정점 u에서 도달 가능하다(reachable)고 한다. 특별한 경우로, 모든 정점은 변의 수가 0인 경로를 통해 자기 자신으로부터 도달 가능하다고 간주된다. 만약 어떤 정점이 하나 이상의 변으로 이루어진 경로(비자명 경로)를 통해 자기 자신에게 도달할 수 있다면, 그 경로는 필연적으로 사이클이 된다. 따라서 유향 비순환 그래프는 어떤 정점도 비자명 경로를 통해 자기 자신에게 도달할 수 없는 그래프로 정의할 수도 있다.[4]
3. 수학적 특성
3. 1. 도달 가능성 관계, 추이적 폐포, 추이적 축소
도달 가능성 관계는 유향 비순환 그래프(DAG)의 정점들에 대한 부분 순서 ''≤''로 형식화될 수 있다. 이 부분 순서에서 두 정점 ''u''와 ''v''는 DAG 내에 ''u''에서 ''v''로 가는 유향 경로가 존재할 경우, 즉 ''v''가 ''u''에서 도달 가능할 때, ''u'' ≤ ''v''로 정렬된다.[5][65] 모든 정점은 자기 자신으로부터 (간선 수가 0인 경로를 통해) 도달 가능하다고 간주된다 (''u'' ≤ ''u'').
서로 다른 DAG가 동일한 도달 가능성 관계와 부분 순서를 가질 수도 있다.[6][66] 예를 들어, 간선 ''a'' → ''b''와 ''b'' → ''c'' 두 개를 가진 DAG는 간선 ''a'' → ''b'', ''b'' → ''c'', ''a'' → ''c'' 세 개를 가진 DAG와 동일한 도달 가능성 관계를 가진다. 두 DAG 모두 정점들이 ''a'' ≤ ''b'' ≤ ''c'' 순서로 정렬되는 동일한 부분 순서를 생성한다.
DAG의 추이 폐포(transitive closure)는 해당 DAG와 동일한 도달 가능성 관계를 가지면서 가장 많은 간선을 포함하는 그래프이다. 즉, 원래 DAG에서 ''u'' ≤ ''v'' 인 모든 서로 다른 정점 쌍 (''u'', ''v'')에 대해 간선 ''u'' → ''v''를 가진다. 이는 도달 가능성 관계 ''≤''를 그래프 이론 용어로 직접 변환한 것으로 볼 수 있다. 이 방법은 모든 유한 부분 순서 집합 (''S'', ≤)에 적용될 수 있다. ''S''의 각 원소에 대한 정점과, ''u'' ≤ ''v'' 관계에 있는 모든 원소 쌍 (''u'', ''v'')에 대한 간선을 가지는 그래프는 자동으로 추이 폐포인 DAG가 되고, (''S'', ≤)를 도달 가능성 관계로 가진다. 따라서 모든 유한 부분 순서 집합은 DAG로 표현될 수 있다.
DAG의 추이 축소(transitive reduction)는 해당 DAG와 동일한 도달 가능성 관계를 가지면서 가장 적은 간선을 포함하는 그래프이다. 이는 DAG의 부분 그래프로서, 도달 가능성 관계 ''≤''의 커버링 관계(covering relation)에 있는 정점 쌍 (''u'', ''v'')에 대해서만 간선 ''u'' → ''v''를 가진다. 즉, ''u''에서 ''v''로 가는 더 긴 경로가 존재하는 간선 ''u'' → ''v''는 추이 축소에서 제거된다.
추이 폐포와 마찬가지로, 추이 축소는 주어진 DAG에 대해 유일하게 정의된다. 그러나 순환(cycle)을 포함하는 유향 그래프의 경우, 동일한 도달 가능성 관계를 가지는 최소 부분 그래프가 여러 개 존재할 수 있다.[7][67]
추이 축소는 부분 순서를 시각화하는 데 유용하다. 동일한 순서 관계를 나타내는 다른 그래프들보다 간선 수가 적어 더 간단한 그래프 그리기로 이어지기 때문이다. 부분 순서의 하세 다이어그램은 모든 간선의 방향이 간선의 시작 정점을 끝 정점보다 낮은 위치에 배치하여 표시되는 추이 축소의 그림이다.[8][68]
3. 2. 위상 정렬
유향 그래프의 위상 정렬은 정점들을 순서대로 나열하는 것으로, 모든 간선에 대해 시작 정점이 끝 정점보다 순서상 먼저 나타나도록 하는 방식이다. 위상 정렬을 가진 그래프는 순환(사이클)을 포함할 수 없다. 만약 순환이 존재한다면, 순환 내에서 가장 먼저 나타나는 정점으로 들어오는 간선은 시작 정점이 끝 정점보다 뒤에 위치하게 되어 위상 정렬의 정의에 어긋나기 때문이다. 따라서 위상 정렬을 가진 모든 그래프는 비순환적이다. 반대로, 모든 유향 비순환 그래프(DAG)는 적어도 하나의 위상 정렬을 가진다. 이 때문에 위상 정렬의 존재 유무는 유향 비순환 그래프를 정의하는 동등한 조건으로 사용될 수 있다. 즉, 위상 정렬을 가진 그래프가 곧 유향 비순환 그래프이다.[2]
일반적으로 위상 정렬은 유일하지 않다. 유향 비순환 그래프가 모든 정점을 포함하는 유향 경로를 가질 경우에만 유일한 위상 정렬을 가지며, 이때 정렬 순서는 정점들이 해당 경로에 나타나는 순서와 같다.[9]
유향 비순환 그래프의 위상 정렬 집합은 해당 그래프의 도달 가능성 관계에 대한 선형 확장 집합과 동일하다.[10] 따라서 동일한 부분 순서를 나타내는 두 그래프는 동일한 위상 정렬 집합을 가진다.
3. 3. 조합적 열거
유향 비순환 그래프(DAG)의 개수를 세는 문제는 로빈슨(Robinson)이 1973년에 연구했다.[11]
''n'' = 0, 1, 2, 3, …에 대해 ''n''개의 레이블이 지정된 정점을 가진 DAG의 수는 다음과 같다(DAG의 위상 정렬에서 이러한 숫자가 나타나는 순서에 대한 제한 없음).
:1, 1, 3, 25, 543, 29281, 3781503, … (OEIS A003024).
이러한 숫자는 다음의 점화식에 의해 계산될 수 있다.
:[11]
에릭 W. 와이슈타인은 추측했고,[12] 맥케이(McKay), 로일(Royle), 완레스(Wanless), 오지에(Oggier) 등은 2004년에 동일한 숫자가 모든 고유값이 양의 실수인 (0,1) 행렬의 개수와 같다는 것을 증명했다. 그 증명은 전단사적이다. 행렬 ''A''가 DAG의 인접 행렬일 필요충분조건은 ''A'' + ''I''가 모든 고유값이 양수인 (0,1) 행렬이라는 것이다. 여기서 ''I''는 항등 행렬을 나타낸다. DAG는 자기 루프를 가질 수 없으므로 인접 행렬의 대각선 원소는 모두 0이어야 한다. 따라서 ''I''를 더해도 모든 행렬 원소가 0 또는 1이라는 속성은 유지된다.[13]
3. 4. 관련 그래프족
'''멀티 트리'''(강력한 모호하지 않은 그래프 또는 맹그로브라고도 함)는 임의의 두 정점 사이에 최대 하나의 방향 경로만 존재하는 DAG이다. 이는 임의의 정점에서 도달할 수 있는 하위 그래프가 무방향 트리를 유도하는 DAG와 동등한 정의이다.[14]
'''폴리 트리'''(방향 트리라고도 함)는 무방향 트리의 각 간선에 방향을 지정하여 형성된 멀티 트리이다.[15]
'''아보리센스'''는 "루트"라고 불리는 특정 정점에서 시작하여, 무방향 트리의 간선들에 방향을 지정하여 형성된 폴리 트리이다. 이 구조에서는 루트에서 다른 모든 정점으로 가는 경로가 유일하게 존재한다.
4. 계산 문제
유향 비순환 그래프(DAG)는 그 구조적 특성으로 인해 다양한 계산 문제의 대상이 된다. 이 문제들은 컴퓨터 과학의 여러 분야에서 중요한 응용을 가진다.
DAG와 관련된 주요 계산 문제들은 다음과 같다.
- 위상 정렬 및 인식: DAG의 정점들을 선형 순서로 배열하는 문제와 주어진 그래프가 DAG인지 판별하는 문제이다. 이는 작업 스케줄링 등 다양한 분야에 활용된다.
- 순환 그래프로부터의 구성: 일반적인 유향 그래프나 무방향 그래프를 DAG로 변환하는 방법들을 다룬다. 여기에는 비순환 방향 설정, 피드백 정점 집합 또는 피드백 아크 집합 제거, 응축 등이 포함된다.
- 추이적 폐쇄 및 추이적 축소: DAG 내 정점 간의 도달 가능성 관계를 명확히 하거나 그래프 구조를 단순화하는 문제이다.
- 클로저 문제: 가중치가 부여된 DAG에서 특정 조건을 만족하는 정점 집합(클로저)의 최적 가중치를 찾는 문제로, 최대 흐름 문제와 관련하여 해결될 수 있다.
- 경로 알고리즘: DAG의 비순환적 특성을 이용하여 최단 경로나 최장 경로를 효율적으로 찾는 문제이다. 일반 그래프와 달리 DAG에서는 이 문제들을 선형 시간에 해결할 수 있다.
이러한 계산 문제들에 대한 구체적인 알고리즘과 복잡도는 각 하위 섹션에서 자세히 다룬다.
4. 1. 위상 정렬 및 인식
위상 정렬은 주어진 유향 비순환 그래프(DAG)의 위상 순서를 찾는 알고리즘 문제이다. 이 문제는 선형 시간에 해결할 수 있다.[16]위상 정렬을 위한 대표적인 알고리즘으로는 칸의 알고리즘과 깊이 우선 탐색(DFS) 기반 방법이 있다.
- 칸의 알고리즘: 이 알고리즘은 자신에게 들어오는 간선이 없는 정점들의 목록을 관리하면서 위상 순서를 직접 구성한다. 처음에는 들어오는 간선이 전혀 없는 정점들로 이 목록을 초기화한다. 그런 다음, 목록에서 정점을 하나씩 꺼내 부분적으로 구성된 위상 순서의 끝에 추가하고, 해당 정점에서 나가는 간선을 고려하여 이웃 정점들의 진입 차수를 갱신한다. 만약 이웃 정점의 진입 차수가 0이 되면, 그 정점도 목록에 추가한다. 모든 정점이 처리될 때까지 이 과정을 반복한다.[18]
- 깊이 우선 탐색(DFS) 기반 방법: 깊이 우선 탐색 그래프 순회를 수행한 후, 각 정점의 탐색이 끝나는 순서(후위 순서)를 기록하고 이 순서를 뒤집으면 위상 순서를 얻을 수 있다.[16]
또한, 주어진 유향 그래프가 DAG인지 여부 또한 선형 시간에 확인할 수 있다. 이는 위상 정렬 알고리즘을 활용하여 가능하다. 한 가지 방법은 위상 정렬을 시도하여 순서를 얻은 다음, 결과 순서가 유효한지(즉, 그래프의 모든 간선 `(u, v)`에 대해 `u`가 `v`보다 순서상 앞에 오는지) 각 간선에 대해 테스트하는 것이다.[17] 또는 칸의 알고리즘과 같은 일부 위상 정렬 알고리즘의 경우, 알고리즘이 오류 조건 없이 모든 정점을 성공적으로 정렬하는지 확인함으로써 DAG 여부를 판별할 수도 있다.[18]
4. 2. 순환 그래프로부터의 구성
임의의 무방향 그래프는 정점에 대한 전순서를 선택하고, 순서상 앞선 정점에서 뒤에 오는 정점으로 모든 간선(edge)의 방향을 정함으로써 DAG로 만들 수 있다. 이렇게 정해진 간선의 방향을 비순환 방향(acyclic orientation)이라고 한다. 서로 다른 전순서가 동일한 비순환 방향을 만들 수도 있으므로, ''n''개의 정점을 가진 그래프는 ''n''!개보다 적은 비순환 방향을 가질 수 있다. 비순환 방향의 수는 주어진 그래프의 색상 다항식 ''χ''에 대해 |''χ''(−1)|와 같다.[19]
임의의 유향 그래프는 모든 순환(cycle)에 포함된 정점 또는 간선의 집합인 피드백 정점 집합 또는 피드백 아크 집합을 제거하여 DAG로 만들 수 있다. 그러나 가장 작은 크기의 피드백 정점 집합이나 피드백 아크 집합을 찾는 것은 NP-난해 문제이다.[20] 또한, 임의의 유향 그래프는 각 강하게 연결된 요소를 하나의 초정점(supervertex)으로 축약하여 응축(condensation)이라고 불리는 DAG로 변환할 수도 있다.[21] 만약 그래프가 이미 비순환적이라면, 가장 작은 피드백 정점 집합과 피드백 아크 집합은 공집합이며, 응축 결과는 원래 그래프와 동일하다.
4. 3. 추이적 폐포 및 추이적 축소
도달 가능성 관계는 유향 비순환 그래프(DAG)의 정점들에 대한 부분 순서 ≤로 형식화될 수 있다. 이 부분 순서에서, 두 정점 ''u''와 ''v''는 DAG 내에 ''u''에서 ''v''로 향하는 방향성 경로가 존재할 경우, 그리고 오직 그 경우에만 ''u'' ≤ ''v''로 정렬된다. 즉, ''u''가 ''v''에 도달할 수 있을 때(또는 ''v''가 ''u''로부터 도달 가능할 때) 성립한다.[5] 하지만 서로 다른 DAG가 동일한 도달 가능성 관계와 부분 순서를 가질 수도 있다.[6] 예를 들어, 두 개의 간선 ''u'' → ''v''와 ''v'' → ''w''를 가진 DAG는 세 개의 간선 ''u'' → ''v'', ''v'' → ''w'', 그리고 ''u'' → ''w''를 가진 DAG와 동일한 도달 가능성 관계를 가진다. 두 DAG 모두 정점들이 ''u'' ≤ ''v'' ≤ ''w''로 정렬되는 동일한 부분 순서를 생성한다.
DAG의 추이적 폐쇄(transitive closure)는 해당 DAG와 동일한 도달 가능성 관계를 가지면서 가장 많은 간선을 포함하는 그래프이다. 이는 DAG의 도달 가능성 관계 ≤에 있는 모든 정점 쌍(''u'', ''v'')에 대해 간선 ''u'' → ''v''를 포함한다. 따라서 추이적 폐쇄는 도달 가능성 관계 ≤를 그래프 이론 용어로 직접 변환한 것으로 볼 수 있다. 모든 유한 부분 순서 집합 (''S'', ≤)에 대해, ''S''의 모든 원소를 정점으로 하고 ≤에 속하는 모든 원소 쌍을 간선으로 하는 그래프는 자동으로 추이적 폐쇄인 DAG가 되며, (''S'', ≤)를 도달 가능성 관계로 갖는다. 이런 방식으로 모든 유한 부분 순서 집합은 DAG로 표현될 수 있다.
DAG의 추이적 축소(transitive reduction)는 해당 DAG와 동일한 도달 가능성 관계를 가지면서 가장 적은 간선을 포함하는 그래프이다. 이는 DAG의 도달 가능성 관계 ≤의 커버링 관계(covering relation)에 있는 모든 정점 쌍(''u'', ''v'')에 대해 간선 ''u'' → ''v''를 포함한다. 추이적 축소는 원본 DAG의 부분 그래프이며, DAG 내에 ''u''에서 ''v''로 가는 더 긴 방향성 경로가 존재하는 간선 ''u'' → ''v''를 제거하여 만들어진다.
추이적 폐쇄와 마찬가지로 추이적 축소는 주어진 DAG에 대해 유일하게 정의된다. 반면, 순환이 있는 유향 그래프의 경우 동일한 도달 가능성 관계를 갖는 최소 부분 그래프가 여러 개 존재할 수 있다.[7] 추이적 축소는 부분 순서를 시각화하는 데 유용하다. 동일한 순서를 나타내는 다른 그래프들보다 간선 수가 적어 더 단순한 시각화가 가능하기 때문이다. 부분 순서의 하세 다이어그램은 추이적 축소의 간선 방향을 시작 정점이 끝 정점보다 아래에 위치하도록 그려서 표현한 것이다.[8]
주어진 DAG(유향 비순환 그래프)의 추이적 폐쇄는 ''n''개의 정점과 ''m''개의 간선이 있을 때, 각 정점으로부터의 도달 가능성을 검사하는 너비 우선 탐색(BFS) 또는 깊이 우선 탐색(DFS)을 이용하여 시간 복잡도 ''O''(''mn'') 안에 구성할 수 있다.[22] 또는, 행렬 곱셈 알고리즘을 이용하여 시간 복잡도 ''O''(''n''''ω'') (여기서 ''ω'' < 2.373은 행렬 곱셈 지수) 안에 해결할 수도 있다. 이는 밀집 그래프(dense graph)의 경우 ''O''(''mn'') 경계보다 이론적으로 더 빠르다.[23]
이러한 추이적 폐쇄 알고리즘들을 통해 길이가 1인 경로로만 연결된 정점 쌍과 길이가 2 이상인 경로가 하나 이상 존재하는 정점 쌍을 구별하는 것이 가능하다. 추이적 축소는 종점이 유일하게 길이가 1인 경로를 형성하는 간선들로 구성된다. 따라서 추이적 축소는 추이적 폐쇄와 동일한 점근적 시간 복잡도 내에서 구성될 수 있다.[24]
4. 4. 폐포 문제
클로저 문제는 정점에 가중치가 있는 유향 비순환 그래프(DAG)를 입력으로 받아, 클로저(어떤 정점 집합 ''C''로서, ''C''에 속한 정점에서 나가는 간선이 가리키는 정점 역시 ''C''에 속하는 집합)의 최소 또는 최대 가중치를 찾는 문제이다. 이 문제는 비순환성을 가정하지 않은 일반적인 유향 그래프에 대해서도 정의할 수 있지만, 그래프의 축약을 통해 동일한 문제로 귀결되므로 일반성이 더 커지는 것은 아니다. 폐포 문제는 최대 흐름 문제로 변환하여 다항 시간 안에 해결할 수 있다.[25]4. 5. 경로 알고리즘
위상 정렬 원리를 이용하면, 일반적인 그래프에서 사용하는 알고리즘 중 일부는 DAG(유향 비순환 그래프)에서 더 간단하게 적용될 수 있다. 예를 들어, DAG에서 특정 시작 정점부터 다른 모든 정점까지의 최단 경로나 최장 경로를 찾는 문제는 위상 정렬 순서대로 정점을 처리하여 선형 시간에 해결할 수 있다. 각 정점에 도달하는 경로의 길이는 해당 정점으로 들어오는 모든 간선을 확인하여 계산된 최소 또는 최대 길이로 정해진다.[26] 반면, 일반적인 그래프에서는 최단 경로를 찾기 위해 다익스트라 알고리즘이나 벨만-포드 알고리즘과 같이 상대적으로 더 복잡하고 느린 알고리즘이 필요하다.[27] 또한, 일반적인 그래프에서 최장 경로를 찾는 문제는 NP-hard로 알려져 있어 효율적인 해결 방법이 존재하지 않을 수 있다.[28]5. 응용
유향 비순환 그래프(DAG)는 다양한 분야에서 문제를 모델링하고 해결하는 데 유용하게 사용된다. 주요 응용 분야로는 작업 순서를 정하는 스케줄링, 데이터 처리 흐름을 나타내는 데이터 처리 네트워크, 사건 간의 인과 관계 분석, 가계도나 소프트웨어 버전 관리 시스템의 버전 기록과 같은 계층 구조 표현(계보 및 버전 기록), 그리고 학술 문헌 등의 인용 그래프 분석 등이 있다. 각 분야에서 DAG는 대상 시스템의 의존성, 순서, 흐름 등을 명확하게 표현하고 분석하는 데 중요한 도구로 활용된다.
5. 1. 스케줄링
부분 순서(partial order)를 유향 비순환 그래프(DAG)로 표현하는 방식은 순서 제약 조건이 있는 작업 시스템의 스케줄링 문제에 다양하게 응용된다.[29] 이러한 문제 중 중요한 유형은 특정 개체가 변경되었을 때 함께 업데이트되어야 하는 다른 개체들의 모음을 다룬다. 예를 들어, 스프레드시트에서 특정 셀이 변경되면 해당 셀에 의존하는 다른 셀들을 다시 계산해야 하고, 소스 코드가 변경되면 관련된 개체 파일을 다시 컴파일해야 한다.이러한 상황에서 의존성 그래프는 각 개체를 정점(vertex)으로 표현하고, 한 개체가 다른 개체보다 먼저 업데이트되어야 할 때 두 개체 사이에 간선(edge)을 연결하여 만든 그래프이다. 만약 이 그래프에 순환(cycle)이 존재한다면, 이를 순환 종속성이라고 부르며 일반적으로 허용되지 않는다. 순환이 있으면 관련된 작업들을 일관되게 스케줄링할 수 없기 때문이다. 순환 종속성이 없는 의존성 그래프는 DAG를 형성한다.[30]
예를 들어, 스프레드시트에서 한 셀의 값이 변경되면, 이 셀에 직접 또는 간접적으로 의존하는 다른 모든 셀의 값을 다시 계산해야 한다. 이때 스케줄링 대상 작업은 각 셀 값의 재계산이다. 한 셀의 수식이 다른 셀의 값을 참조할 때 종속성이 발생하며, 참조되는 값은 이를 사용하는 수식보다 먼저 계산되어야 한다. 의존성 그래프를 위상 정렬(topological sorting)하고 이 순서에 따라 셀 업데이트를 스케줄링하면, 각 셀을 한 번만 평가하여 전체 스프레드시트를 효율적으로 업데이트할 수 있다.[31] 비슷한 작업 순서 결정 문제는 프로그램 컴파일을 위한 make 파일 관리나 저수준 컴퓨터 프로그램 최적화를 위한 명령 스케줄링에서도 발생한다.[32]
스케줄링 제약 조건을 다루는 또 다른 DAG 기반 방법론은 프로그램 평가 및 검토 기술(PERT)이다. 이는 대규모 인적 프로젝트 관리를 위해 개발된 초기 DAG 응용 사례 중 하나이다. PERT에서 DAG의 정점은 수행해야 할 개별 작업이 아니라 프로젝트의 주요 마일스톤을 나타낸다. 실제 작업이나 활동은 해당 작업의 시작과 완료를 나타내는 두 마일스톤을 연결하는 DAG의 간선으로 표현된다. 각 간선에는 작업을 완료하는 데 필요한 예상 시간이 표시된다. 이 DAG에서 가장 긴 경로는 프로젝트의 임계 경로(critical path)를 나타내며, 프로젝트 전체 소요 시간을 결정하는 경로이다. 각 마일스톤의 일정은 해당 정점까지의 최장 경로 길이를 계산하여 결정할 수 있다.[33]
5. 2. 데이터 처리 네트워크
유향 비순환 그래프(DAG)는 처리 요소들의 네트워크를 나타내는 데 사용될 수 있다. 이러한 표현 방식에서 데이터는 처리 요소로 들어오는 에지를 통해 입력되고, 나가는 에지를 통해 출력된다.예를 들어, 전자 회로 설계에서 정적인 조합 논리 회로 블록은 논리 게이트들의 비순환 시스템으로 표현될 수 있다. 이 시스템은 입력에 대한 함수를 계산하며, 함수의 입력과 출력은 개별 비트로 표현된다. 일반적으로 이러한 블록의 출력은 레지스터나 상태 요소에 의해 저장되지 않는 한 다시 입력으로 사용될 수 없으며, 이는 비순환적 속성을 유지하는 데 도움이 된다.[34]
데이터 흐름 프로그래밍 언어는 데이터 스트림에 대한 연산 시스템과 연산들의 출력과 입력 간의 연결을 설명한다. 이러한 언어들은 동일한 비순환적으로 연결된 연산 모음이 많은 데이터 항목에 반복적으로 적용되는 데이터 처리 작업을 설명하는 데 유용하다. 각 연산은 다른 입력 집합을 사용할 수 있게 되는 즉시 병렬 프로세스에 의해 수행될 수 있어 병렬 알고리즘으로 실행될 수 있다.[35]
컴파일러에서는 순차적인 코드(루프나 조건 분기 없는 일련의 명령문) 내에서 수행되는 각 산술 연산의 입력과 출력을 설명하기 위해 DAG를 사용할 수 있다. 이 표현 방식은 컴파일러가 공통 부분식 제거를 효율적으로 수행하도록 돕는다.[36] 더 높은 수준의 코드 구성에서는 비순환 의존성 원리가 적용되는데, 이는 대규모 소프트웨어 시스템의 모듈이나 구성 요소 간의 의존성이 유향 비순환 그래프를 형성해야 한다는 원칙이다.[37]
피드포워드 신경망 역시 유향 비순환 그래프의 한 예시이다.
5. 3. 인과 구조
정점이 특정 시간에 발생하는 사건을 나타내고, 간선이 항상 시간상 앞선 정점에서 뒤의 정점을 가리키는 그래프는 필연적으로 방향성을 가지며 비순환적이다. 이는 그래프의 경로를 따라갈 때 정점과 연관된 시간이 항상 증가하기 때문에, 경로상의 한 정점에서 다시 그 정점으로 돌아올 수 없어 순환(cycle)이 발생하지 않기 때문이다. 이는 사건이 미래에만 영향을 미치고 과거에는 영향을 미치지 않으므로 인과 루프가 존재하지 않는다는 우리의 자연스러운 직관과 일치한다. 양자 중력에 대한 인과 집합 접근 방식에서 나타나는 그래프가 이러한 유형의 예시이며, 이 경우 그래프는 추이적으로 완전하다. 소프트웨어 버전 기록이나 문헌 인용 그래프 등도 시간 순서를 따르는 방향성 비순환 그래프(DAG)의 예시이다. 버전 기록에서는 각 버전이 특정 시간과 연결되고, 인용 그래프에서는 문서가 특정 시점에 게시되며 이전 문서만 참조할 수 있다.사건들이 특정 물리적 시간과 직접적인 관련이 없는 경우에도, 사건 간의 순수한 인과 관계를 나타내기 위해 방향성 비순환 그래프를 사용하기도 한다.[38] 대표적인 예로 베이즈 네트워크가 있는데, 이는 확률적 사건들의 시스템을 방향성 비순환 그래프의 정점으로 나타낸다. 여기서 특정 사건의 발생 가능성은 DAG 상에서 그 사건의 선행 사건(predecessor)들의 발생 가능성으로부터 계산될 수 있다.[39] 이러한 맥락에서 DAG의 모럴 그래프는 동일한 정점의 모든 부모(parent) 노드 사이에 무방향 간선을 추가하고(이를 "결합(marrying)"이라고도 한다), 모든 방향성 간선을 무방향 간선으로 대체하여 생성된 무방향 그래프이다.[40]
영향력 다이어그램 역시 유사한 인과 구조를 가진 그래프 유형이다. 이 다이어그램의 정점은 내려야 할 결정이나 아직 알 수 없는 정보를 나타내며, 간선은 한 정점에서 다른 정점으로 미치는 인과적 영향을 나타낸다.[41] 예를 들어, 역학 분야에서는 이러한 다이어그램을 사용하여 다양한 개입(intervention) 전략에 따른 예상 결과 값을 추정하는 데 활용한다.[42][43]
반대로, 방향성 비순환 그래프로 표현되는 모든 응용 문제는 그 자체로 인과 구조를 가진다고 해석할 수 있다. 이는 그래프에 명시적인 시간 순서가 존재하거나, 그래프 구조 자체에서 파생될 수 있는 순서가 있기 때문이다. 모든 방향성 비순환 그래프는 위상 정렬이 가능하므로 이러한 해석이 가능하다. 즉, 모든 간선이 정렬된 순서상 동일한 방향(앞선 정점에서 뒤따르는 정점)을 가리키도록 정점들을 배열하는 방법이 적어도 하나 존재한다는 의미이다.
5. 4. 계보 및 버전 기록
가계도는 각 가족 구성원을 정점으로 하고, 각 부모-자식 관계를 간선으로 하는 유향 비순환 그래프로 볼 수 있다.[44] 하지만 이름과 달리 반드시 트리 구조는 아닌데, 이는 친족 간 결혼으로 인해 자녀가 어머니와 아버지 양쪽에서 공통 조상을 가질 수 있기 때문이다. 이러한 현상을 족보 붕괴라고 한다.[45] 물론 모계 혈통(어머니-딸 관계)이나 부계 혈통(아버지-아들 관계)만을 따지면 각각은 트리가 된다. 어떤 사람도 자신의 조상이 될 수는 없으므로, 가계도는 항상 비순환적이다.[46]
Git과 같은 분산 버전 관리 시스템의 버전 기록 역시 유향 비순환 그래프 구조를 가진다. 여기서는 각 개정판(revision)이 정점이 되고, 한 개정판에서 다음 개정판으로 넘어가는 관계가 간선이 된다. 여러 버전의 변경 사항을 하나로 합치는 병합(merge) 작업이 가능하기 때문에, 버전 기록은 일반적으로 트리가 아니다.[47]
계산 기하학 분야의 여러 무작위화된 알고리즘에서는 "기록 DAG"라는 것을 유지 관리하는데, 이는 알고리즘이 진행됨에 따라 기하학적 구조가 어떻게 변해왔는지 그 버전 기록을 나타낸다. 예를 들어, 델로네 삼각분할을 만드는 무작위 증분 알고리즘의 경우를 보자. 점이 하나씩 추가될 때마다 기존의 삼각형 하나가 세 개의 더 작은 삼각형으로 쪼개지거나, 인접한 두 삼각형 쌍이 다른 두 삼각형 쌍으로 바뀌는 "플립(flip)" 연산을 통해 삼각분할이 수정된다. 이 알고리즘의 기록 DAG는 과정 중에 생성된 모든 삼각형을 정점으로 가지며, 어떤 삼각형이 다른 두 개 또는 세 개의 삼각형으로 대체될 때마다 해당 삼각형들 사이에 간선을 연결한다. 이러한 구조는 점 위치 찾기(point location query) 같은 문제를 효율적으로 해결하는 데 도움을 준다. 예를 들어, 어떤 쿼리 점 ''q''가 델로네 삼각분할 내의 어느 삼각형에 속하는지 찾으려면, 기록 DAG에서 시작하여 각 단계마다 ''q''를 포함하는 다음 단계의 삼각형으로 이동하는 경로를 따라가면 된다. 이 경로의 끝에서 도달한 최종 삼각형이 바로 ''q''를 포함하는 델로네 삼각형이 된다.[48]
5. 5. 인용 그래프
인용 그래프에서 정점은 단일 출판 날짜를 가진 문서를 나타내고, 간선은 한 문서의 참고 문헌에서 다른, 반드시 더 이전의 문서로 향하는 인용 관계를 보여준다. 대표적인 예는 학술 논문 간의 인용 관계로, 1965년 데릭 J. 드 솔라 프라이스는 "과학 논문의 네트워크"라는 논문[49]에서 이를 지적하며 인용 네트워크의 첫 번째 모델인 프라이스 모델을 제시했다.[50] 이 경우, 특정 논문이 인용된 횟수, 즉 인용 횟수는 인용 네트워크에서 해당 정점으로 들어오는 간선의 수(진입 차수)와 같으며, 이는 인용 분석에서 중요한 지표로 활용된다.학술 논문 외에도 법원 판결 역시 인용 그래프의 예시가 될 수 있다. 판사는 특정 사건에 대한 결론을 내릴 때, 이전 판례들을 인용하여 자신의 주장을 뒷받침한다. 또한, 특허 분야에서도 현재 특허와 관련된 이전 기술, 즉 선행 기술에 해당하는 이전 특허들을 참조해야 하므로 인용 그래프 구조가 나타난다.
인용 네트워크는 방향성을 가지며 순환하지 않는 그래프(DAG, Directed Acyclic Graph)의 특성을 지니고 있어, 일반적인 그래프 분석 방법 외에도 DAG의 고유한 속성을 활용한 분석 기법을 적용할 수 있다. 예를 들어, 추이 감소(Transitive Reduction) 기법은 다양한 분야의 인용 분포를 분석하여, 각기 다른 맥락에서 인용 네트워크가 어떻게 형성되는지에 대한 통찰력을 제공하고 그 메커니즘의 차이를 밝히는 데 도움을 준다.[51] 또 다른 기법인 주 경로 분석(Main Path Analysis)은 인용 연결 고리를 추적하여 특정 인용 그래프 내에서 가장 중요하고 영향력 있는 인용 흐름을 찾아내는 데 사용된다.
프라이스 모델은 실제 인용 네트워크를 완벽하게 설명하기에는 다소 단순한 모델이지만, 그 구조가 간단하여 네트워크의 여러 속성을 수학적으로 분석할 수 있다는 장점이 있다. 이 모델의 분석 결과 중 상당수는 무방향성 그래프 모델인 바라바시-알버트 모델을 통해 얻어진 결과를 활용하여 도출되기도 한다. 하지만 프라이스 모델은 방향성 비순환 그래프를 생성하므로, DAG 고유의 속성을 분석적으로 계산하고자 할 때 유용한 도구가 된다. 예를 들어, 프라이스 모델에 따르면 네트워크에 n번째로 추가된 노드에서 가장 처음 생성된 노드까지 이어지는 가장 긴 경로의 길이는 대략 에 비례하여 증가하는 것으로 나타난다.[52]
참조
[1]
서적
Graphs: Theory and Algorithms
John Wiley and Son
[2]
서적
Digraphs: Theory, Algorithms and Applications
Springer-Verlag
[3]
서적
Graph theory: an algorithmic approach
Academic Press
[4]
서적
Simulation Techniques for Discrete Event Systems
https://books.google[...]
Cambridge University Press
[5]
서적
The Design and Analysis of Algorithms
https://books.google[...]
Springer
[6]
서적
Loop Transformations for Restructuring Compilers: The Foundations
https://books.google[...]
Springer
[7]
서적
Digraphs: Theory, Algorithms and Applications
https://books.google[...]
Springer
[8]
서적
Graphs, Networks and Algorithms
https://books.google[...]
Springer
[9]
서적
Algorithms
https://books.google[...]
Addison-Wesley
[10]
서적
A Short Course in Discrete Mathematics
https://books.google[...]
Courier Dover Publications
[11]
서적
New Directions in the Theory of Graphs
Academic Press
[12]
웹사이트
Weisstein's Conjecture
WeissteinsConjecture
[13]
간행물
Acyclic digraphs and eigenvalues of (0,1)-matrices
http://www.cs.uwater[...]
[14]
간행물
Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)
[15]
간행물
Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987
http://ftp.cs.ucla.e[...]
[16]
서적
Introduction to Algorithms
[17]
서적
The Algorithm Design Manual
https://books.google[...]
Springer
[18]
문서
Jungnickel
2012
[19]
간행물
Acyclic orientations of graphs
http://math.mit.edu/[...]
[20]
서적
Computers and Intractability: A Guide to the Theory of NP-Completeness
W. H. Freeman and Company
[21]
서적
Structural Models: An Introduction to the Theory of Directed Graphs
John Wiley & Sons
[22]
문서
Skiena
2009
[23]
문서
Skiena
2009
[24]
문서
Bang-Jensen
2008
[25]
간행물
Maximal closure of a graph and applications to combinatorial problems
[26]
문서
Cormen et al.
2001
[27]
문서
Cormen et al.
2001
[28]
문서
Cormen et al.
2001
[29]
문서
Skiena
2009
[30]
간행물
23rd Australian Software Engineering Conference
IEEE
[31]
서적
Handbook of Graph Theory
https://books.google[...]
CRC Press
[32]
서적
The Compiler Design Handbook: Optimizations and Machine Code Generation
https://books.google[...]
CRC Press
[33]
서적
What Every Engineer Should Know About Decision Making Under Uncertainty
https://books.google[...]
CRC Press
[34]
서적
Timing
https://books.google[...]
Springer
[35]
간행물
Programming Symposium
[36]
서적
Advanced Backend Optimization
https://books.google[...]
John Wiley & Sons
[37]
서적
Large-Scale Software Architecture: A Practical Guide using UML
https://books.google[...]
John Wiley & Sons
[38]
서적
Causal Learning
https://books.google[...]
Oxford University Press
[39]
서적
Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks
https://books.google[...]
Society for Industrial and Applied Mathematics
[40]
서적
Probabilistic Networks and Expert Systems
Springer
[41]
서적
The Technology Management Handbook
https://books.google[...]
CRC Press
[42]
서적
Encyclopedia of Epidemiology, Volume 1
https://books.google[...]
SAGE
[43]
논문
Causal diagrams for empirical research
https://escholarship[...]
[44]
논문
Haplotypes versus genotypes on pedigrees
2011-04
[45]
간행물
IEEE Symposium on Information Visualization (INFOVIS 2005)
[46]
간행물
Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01)
Society for Industrial and Applied Mathematics
[47]
서적
Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems
https://books.google[...]
Springer
[48]
서적
Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures
https://books.google[...]
American Mathematical Society
[49]
논문
Networks of Scientific Papers
http://garfield.libr[...]
1965-07-30
[50]
논문
A general theory of bibliometric and other cumulative advantage processes
1976
[51]
논문
Transitive reduction of citation networks
[52]
논문
The Longest Path in the Price Model
2020
[53]
간행물
Combinatorial Pattern Matching
Springer
[54]
서적
Applied Combinatorics on Words
https://books.google[...]
Cambridge University Press
[55]
논문
Representation of switching circuits by binary-decision programs
[56]
논문
Binary decision diagrams
[57]
간행물
Proc. 24th ACM/IEEE Design Automation Conference (DAC '87)
ACM
[58]
서적
Graph theory: an algorithmic approach
Academic Press
[59]
서적
Graphs: Theory and Algorithms
John Wiley and Son
[60]
서적
Digraphs: Theory, Algorithms and Applications
Springer-Verlag
[61]
서적
Graphs: Theory and Algorithms
John Wiley and Son
[62]
서적
Digraphs: Theory, Algorithms and Applications
Springer-Verlag
[63]
서적
Graph theory: an algorithmic approach
Academic Press
[64]
서적
Simulation Techniques for Discrete Event Systems
https://books.google[...]
Cambridge University Press
[65]
서적
The Design and Analysis of Algorithms
https://books.google[...]
Springer
[66]
서적
Loop Transformations for Restructuring Compilers: The Foundations
https://books.google[...]
Springer
[67]
서적
Digraphs: Theory, Algorithms and Applications
https://books.google[...]
Springer
[68]
서적
Graphs, Networks and Algorithms
https://books.google[...]
Springer
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com