유향 그래프

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

1. 개요
2. 정의
- 2.1. 용어
3. 종류
- 3.1. 부분 클래스
4. 내차수와 외차수
5. 연결성
6. 활용
7. 관련 문제
참조

1. 개요

유향 그래프는 정점(노드)과 정점 사이의 방향성을 가진 간선(호, 화살표)으로 구성된 그래프이다. 유향 그래프는 순서쌍 G = (V, A)로 정의되며, V는 정점의 집합, A는 정점의 순서쌍 집합으로, 각 순서쌍은 유향 간선을 나타낸다. 유향 그래프는 무향 그래프와 달리 간선의 방향성이 존재하며, 머리와 꼬리를 갖는다. 유향 그래프는 가중치, 루프, 다중 호의 허용 여부에 따라 다양한 종류로 분류되며, 내차수와 외차수 개념을 통해 정점의 연결 상태를 분석할 수 있다. 유향 그래프는 약한 연결, 강한 연결과 같은 연결성을 가질 수 있으며, 먹이 그물, 게임 트리 등 다양한 분야에 활용된다.

더 읽어볼만한 페이지

유향 그래프 - 강한 연결 요소
강한 연결 요소는 유향 그래프에서 임의의 두 정점 간에 서로 도달 가능한 경로가 존재하는 부분 그래프를 의미하며, 깊이 우선 탐색 등 다양한 알고리즘으로 찾을 수 있고 그래프 이론과 알고리즘 설계에 중요한 개념이다.
유향 그래프 - 위상정렬
위상 정렬은 방향 그래프의 정점들을 간선 방향에 따라 정렬하는 알고리즘으로, 작업 스케줄링, 의존성 분석 등에 활용되며 방향 비순환 그래프에서만 수행 가능하고, Kahn 알고리즘, 깊이 우선 탐색 등의 구현 방법이 존재하며 스케줄링 문제 해결에 중요한 선행 그래프 분석에 사용됩니다.
그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.

유향 그래프

2. 정의

'''유향 그래프'''(영어: directed graph)는 꼭짓점과 방향이 있는 변으로 구성된 그래프이다.

유향 그래프 $\Gamma=(V,E)$ 는 집합 $V$ 와 $V$ 의 순서쌍들의 집합 $E\subset V\times V$ 의 순서쌍이다. $e=(u,v)$ 라면 $e$ 를 $u$ 에서 $v$ 로 가는 변이라고 하며, 꼭짓점 $v$ 는 변 $e$ 의 머리(head|헤드^영어), 꼭짓점 $u$ 는 변 $e$ 의 꼬리(tail|테일^영어)라고 한다.^[1]

일부 저자는 유향 그래프가 동일한 출발점과 도착점을 가진 여러 개의 화살표를 갖는 것을 허용하는데, 이러한 개체는 '''유향 멀티그래프'''라고 불린다. 반면에, 어떤 저자는 유향 그래프가 루프를 가질 수 없도록 정의하기도 한다.^[2] 루프가 없는 유향 그래프는 '''단순 유향 그래프'''라고 하며, 루프가 있는 유향 그래프는 ''루프-디그래프''라고 한다.

2. 1. 용어

유향 그래프는 head|헤드^영어와 tail|테일^영어이라는 용어를 사용한다. 유향 그래프의 정의는 다음과 같다.^[1]

''V''는 집합으로, 그 원소들을 ''정점'', ''노드'', 또는 ''점''이라고 부른다.
''A''는 정점의 순서쌍 집합으로, ''호'', ''유향 간선''(때로는 단순히 ''간선''이라고 부르며, 해당 집합은 ''A'' 대신 ''E''로 표기), ''화살표'', 또는 ''유향 선''이라고 부른다.

이는 일반 또는 무향 그래프와는 다르며, 후자는 정점의 비순서쌍을 기반으로 정의되며, 일반적으로 ''간선'', ''링크'' 또는 ''선''이라고 부른다. 호 (x, y)는 x에서 y로 향하는 것으로 간주되며, y는 호의 머리, x는 꼬리라고 불린다. y는 x의 직접적인 후계자라고 하며, x는 y의 직접적인 선임자라고 한다. 경로가 x에서 y로 이어진다면, y는 x의 후계자라고 하며 x에서 도달 가능하다고 하고, x는 y의 선임자라고 한다. 호 (y, x)는 (x, y)의 역 호라고 불린다.

어떤 저자들은 다중 호를 가질 수 있도록 허용하는데, 이러한 경우 '''유향 멀티그래프'''라고 부른다.

루프가 없는 유향 그래프는 '''단순 유향 그래프'''라고 할 수 있으며, 루프가 있는 유향 그래프는 ''루프-디그래프''라고 할 수 있다.^[2]

3. 종류

유향 그래프의 종류는 다음과 같다.

대칭 유향 그래프: 모든 간선이 양방향으로 나타나는 유향 그래프이다. 즉, 모든 화살표에 대해 해당 역 화살표도 존재한다.^[2]
단순 유향 그래프: 루프(정점을 자체에 연결하는 화살표)가 없고, 동일한 시작 및 대상 노드를 가진 여러 개의 화살표가 없는 유향 그래프이다. 여러 개의 화살표가 있는 경우는 유향 멀티그래프라고 한다.^[2]
완전 유향 그래프: 각 정점 쌍이 대칭적인 유향 아크 쌍으로 연결된 단순 유향 그래프이다.
반완전 멀티파티트 유향 그래프: 정점 집합이 여러 집합으로 분할되어, 서로 다른 집합의 모든 정점 ''x''와 ''y''에 대해 ''x''와 ''y'' 사이에 아크가 있는 단순 유향 그래프이다. ''x''와 ''y'' 사이에는 하나의 아크가 있거나 반대 방향으로 두 개의 아크가 있을 수 있다.^[3]
반완전 유향 그래프: 각 정점 쌍 사이에 아크가 있는 단순 유향 그래프이다.
준전이 유향 그래프: ''x''에서 ''y''로, ''y''에서 ''z''로의 아크가 있는 모든 정점 ''x'', ''y'', ''z''에 대해 ''x''와 ''z'' 사이에도 아크가 있는 단순 유향 그래프이다. ''x''와 ''z'' 사이에는 하나의 아크만 있거나 반대 방향으로 두 개의 아크가 있을 수 있다.^[5]
지향 그래프: 반대 방향의 유향 간선 쌍이 없는 유향 그래프이다. 유향 그래프는 2-유향 사이클이 없는 경우에만 지향 그래프이다.^[6]
토너먼트: 무향 완전 그래프의 각 간선에 방향을 부여하여 얻은 지향 그래프이다. 토너먼트는 반완전 유향 그래프이다.^[4]
유향 그래프는 유향 사이클이 없으면 비순환이다. 이러한 유향 그래프는 유향 비순환 그래프(DAG)라고 부른다.^[7]
멀티트리는 동일한 시작 정점에서 동일한 끝 정점으로 가는 서로 다른 유향 경로가 없는 DAG이다.
지향 트리(폴리트리)는 트리의 간선에 방향을 지정하여 형성된 DAG이다.
루트 트리는 기본 무향 트리의 모든 간선이 루트에서 멀어지거나 루트를 향하도록 방향이 지정된 지향 트리이다.

3. 1. 부분 클래스

'''대칭 유향 그래프'''는 모든 간선이 양방향으로 두 번 나타나는 유향 그래프이다. 즉, 유향 그래프에 속하는 모든 화살표에 대해 해당 역 화살표도 속한다.^[2]
'''단순 유향 그래프'''는 루프(정점을 직접 자체에 연결하는 화살표)가 없고, 동일한 시작 및 대상 노드를 가진 여러 개의 화살표가 없는 유향 그래프이다. 여러 개의 화살표가 있는 경우 유향 멀티그래프라고 한다.^[2]
'''완전 유향 그래프'''는 각 정점 쌍이 대칭적인 유향 아크 쌍으로 연결된 단순 유향 그래프이다.
'''반완전 멀티파티트 유향 그래프'''는 정점 집합이 집합으로 분할되어 서로 다른 집합의 모든 정점 ''x''와 ''y''의 쌍에 대해 ''x''와 ''y'' 사이에 아크가 있는 단순 유향 그래프이다. ''x''와 ''y'' 사이에 하나의 아크가 있거나 반대 방향으로 두 개의 아크가 있을 수 있다.^[3]
'''반완전 유향 그래프'''는 각 정점 쌍 사이에 아크가 있는 단순 유향 그래프이다. 모든 반완전 유향 그래프는 각 정점이 분할의 집합을 구성하는 자명한 방식으로 반완전 멀티파티트 유향 그래프이다.^[4]
'''준전이 유향 그래프'''는 ''x''에서 ''y''로, ''y''에서 ''z''로의 아크가 있는 별개의 모든 정점 ''x'', ''y'', ''z''의 삼중항에 대해 ''x''와 ''z'' 사이에 아크가 있는 단순 유향 그래프이다. ''x''와 ''z'' 사이에 하나의 아크만 있거나 반대 방향으로 두 개의 아크가 있을 수 있다.^[5]
'''지향 그래프'''는 반대 방향의 유향 간선 쌍이 없는 유향 그래프이다. 유향 그래프는 2-유향 사이클이 없는 경우에만 지향 그래프이다.^[6]
'''토너먼트'''는 무향 완전 그래프의 각 간선에 대한 방향을 선택하여 얻은 지향 그래프이다. 토너먼트는 반완전 유향 그래프이다.^[4]
유향 그래프는 유향 사이클이 없으면 '''비순환'''이다. 이러한 유향 그래프의 일반적인 이름은 '''유향 비순환 그래프'''(DAG)이다.^[7]
''멀티트리''는 동일한 시작 정점에서 동일한 끝 정점으로 가는 서로 다른 유향 경로가 없는 DAG이다.
''지향 트리'' 또는 ''폴리트리''는 트리의 간선(연결된, 비순환 무향 그래프)의 방향을 지정하여 형성된 DAG이다.
''루트 트리''는 기본 무향 트리의 모든 간선이 루트에서 멀어지거나 루트를 향하도록 지향된 지향 트리이다.

4. 내차수와 외차수

정점의 경우 정점에 인접한 머리 끝부분의 수를 정점의 내차수(indegree)라고 하며 정점에 인접한 꼬리의 끝부분의 수를 외차수(outdegree)라고 부른다.

꼭짓점에 인접한 머리 끝 부분의 수를 해당 꼭짓점의 ''진입 차수''라고 하며, 꼬리 끝 부분의 수는 해당 꼭짓점의 ''진출 차수''라고 한다(트리에서는 ''분기 계수''라고 함).

''G'' = (''V'', ''E'')이고 ''v'' ∈ ''V''라고 하자. ''v''의 진입 차수는 deg⁻(''v'')로 표시하고, 진출 차수는 deg⁺(''v'')로 표시한다.

deg⁻(''v'') = 0인 꼭짓점은 각 꼭짓점의 나가는 호의 시작점이므로 ''소스''라고 한다. 마찬가지로, deg⁺(''v'') = 0인 꼭짓점은 들어오는 각 호의 끝점이므로 ''싱크''라고 한다.

''차수 합 공식''에 따르면, 유향 그래프의 경우,

:

\sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |E|.

모든 꼭짓점 ''v'' ∈ ''V''에 대해, deg⁺(''v'') = deg⁻(''v'')이면, 해당 그래프를 ''균형 유향 그래프''라고 한다.^[8]

5. 연결성

유향 그래프는 모든 유향 간선을 무향 간선으로 대체하여 얻은 무향 "기저 그래프"가 연결 그래프이면 "약하게 연결"(또는 단순히 "연결"이라고 한다)^[9]된다.

유향 그래프는 모든 정점 쌍(x, y)에 대해 ''x''에서 ''y''로(그리고 ''y''에서 ''x''로) 유향 경로가 존재하면 "강하게 연결" 또는 "강력하다"고 한다. "강력 연결 요소"는 최대 강력 연결 부분 그래프이다.

연결된 루트 그래프("흐름 그래프")는 특별한 "루트 정점"에서 모든 정점으로 유향 경로가 존재하는 그래프이다.

6. 활용

먹이그물^[10]과 게임 트리 등을 유향 그래프로 나타낼 수 있다.
'''가중 유향 그래프''' ('''유향 네트워크'''라고도 함)는 화살표에 ''가중치''가 할당된 유향 그래프이다.^[2]
'''흐름 네트워크'''는 ''소스''와 ''싱크''라는 두 노드가 구분되는 가중 유향 그래프이다.
'''근원 유향 그래프''' ('''흐름 그래프'''라고도 함)는 꼭짓점이 근원으로 구분된 유향 그래프이다.
* ''제어 흐름 그래프''는 컴퓨터 과학에서 프로그램 실행 중 거쳐갈 수 있는 모든 경로를 나타내는 데 사용되는 근원 유향 그래프이다.
'''신호 흐름 그래프'''는 노드가 시스템 변수를 나타내고, 분기 (가장자리, 호 또는 화살표)가 노드 쌍 간의 기능적 연결을 나타내는 유향 그래프이다.
'''흐름 그래프'''는 일련의 선형 대수 또는 미분 방정식과 관련된 유향 그래프이다.
'''상태 다이어그램'''은 유한 상태 기계를 나타내는 유향 멀티 그래프이다.
'''가환 다이어그램'''은 범주론에서 사용되는 유향 그래프로, 꼭짓점은 (수학적) 객체를 나타내고 화살표는 사상을 나타낸다. 동일한 시작점과 끝점을 가진 모든 유향 경로는 합성을 통해 동일한 결과를 갖는다.
리 군 이론에서 '''quiver''' ''Q''는 functor category FinVct_''K''^''F''(''Q'')의 객체, 즉 functor로 정의된 ''representation'' ''V''의 domain 역할을 하며, 따라서 형상을 특징짓는 유향 그래프이다. 여기서 ''F''(''Q'')는 ''Q''의 경로로 구성된 ''Q''의 free category이고 FinVct_''K''는 field ''K'' 위의 유한 차원 벡터 공간의 범주이다. quiver의 표현은 그 꼭짓점에 벡터 공간을, 그 가장자리 (따라서 경로)에는 그들 사이의 선형 변환과 호환되게 레이블을 붙이고, 자연 변환을 통해 변환한다.

7. 관련 문제

유향 그래프의 차수열은 진입 차수와 진출 차수의 쌍으로 구성된 목록이다. 위의 예시의 경우 차수열은 ((2, 0), (2, 2), (0, 2), (1, 1))이다. 차수열은 유향 그래프의 불변량으로, 동형 유향 그래프는 동일한 차수열을 가진다. 그러나 차수열은 일반적으로 유향 그래프를 고유하게 식별하지 못하며, 경우에 따라 비동형 유향 그래프가 동일한 차수열을 가질 수 있다.

유향 그래프 실현 문제는 주어진 양의 정수 쌍의 수열을 차수열로 갖는 유향 그래프를 찾는 문제이다. (꼬리에 오는 0 쌍은 유향 그래프에 적절한 수의 고립된 정점을 추가하여 자명하게 실현될 수 있으므로 무시할 수 있다.) 어떤 유향 그래프의 차수열인 수열, 즉 유향 그래프 실현 문제에 대한 해가 있는 수열을 유향 그래프 수열 또는 유향 그래프 시퀀스라고 한다. 이 문제는 클레이트만-왕 알고리즘 또는 풀커슨-첸-앤스티 정리로 해결할 수 있다.

참조

_[1] 서적
_[2] 서적 Introductory Graph Theory https://books.google[...] Courier Corporation 2020-10-02
_[3] 서적
_[4] 서적
_[5] 서적
_[6] 서적
_[7] 서적
_[8] 간행물 Discrete Mathematics and Graph Theory PHI Learning Pvt. Ltd.
_[9] 서적
_[10] 웹사이트 https://terms.naver.[...]

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

문의하기 : help@durumis.com