다중 그래프

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

1. 개요
2. 정의
- 2.1. 무향 다중 그래프
  - 2.1.1. 변에 고유한 정체성이 없는 경우
  - 2.1.2. 변에 고유한 정체성이 있는 경우
- 2.2. 유향 다중 그래프
  - 2.2.1. 변에 고유한 정체성이 없는 경우
  - 2.2.2. 변에 고유한 정체성이 있는 경우 (화살집)
3. 관련 개념
4. 라벨링
- 4.1. 정의 1
- 4.2. 정의 2
참조

1. 개요

다중 그래프는 그래프 이론에서 꼭짓점과 변으로 구성된 그래프의 일반화된 개념이다. 변은 여러 개가 존재할 수 있으며, 자기 자신으로 연결되는 고리(루프)를 허용한다. 다중 그래프는 무향, 유향, 혼합 다중 그래프로 분류되며, 변의 방향성 유무에 따라 정의가 달라진다. 또한, 다중 그래프는 변에 고유한 정체성이 있는지 여부에 따라 정의가 구분된다. 라벨링 개념을 지원하며, 라벨이 지정된 다중 그래프는 정점과 호에 라벨이 부여된 그래프로 정의된다.

더 읽어볼만한 페이지

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

다중 그래프

2. 정의

다중 그래프 $G=(V,E,\partial)$ 는 다음과 같은 순서쌍이다.

$V$ 는 '''꼭짓점'''(vertex^영어)의 집합이다.
$E$ 는 '''변'''(edge^영어)의 집합이다.
$\partial\colon E\to S^2(V)$ 는 함수이다. 여기서 $S^2(V)=\{\{u,v\}\colon u,v\in V\}$ 이다. 만약 $\partial e=\{u,v\}$ 라면, $u$ 와 $v$ 를 $e$ 의 '''끝점'''(endpoint^영어)이라고 한다. 양 끝점이 같은 변은 '''고리'''(loop|루프^영어)라고 한다.

일부 저자는 다중 그래프에서 루프를 허용한다.^[2] 다른 저자는 이러한 그래프를 '''의사 그래프'''라고 부르며, 루프가 없는 경우에만 다중 그래프라는 용어를 사용한다.^[3]

2. 1. 무향 다중 그래프

무향 다중 그래프는 변에 방향성이 없는 다중 그래프이다. 무향 다중 그래프는 변에 고유한 정체성이 없는 경우와 있는 경우로 나누어 정의할 수 있으며, 자세한 내용은 하위 섹션을 참고할 수 있다.

꼭짓점

v\in V(G)

의 '''차수'''(degree^영어)

\deg v

는 다음과 같이 정의된다.

:

\deg v=\left|\left\{e\in E(G)\colon v\in\operatorname{end}(G)\land|\operatorname{end}(G)|=2\right\}\right|+2\left|\left\{e\in E(G)\colon\{v\}=\operatorname{end}(G)\right\}\right|

즉, 고리는 차수에서 두 배로 센다.

다중 그래프의 경우 그래프에 대한 대부분의 용어들이 적용되지만, 다른 경우도 있다. 예를 들어, 다중 그래프에서 변을 축약(contraction^영어)시키면, 중복되는 변들을 하나로 합치지 않으며, 고리 또한 남겨둔다.

2. 1. 1. 변에 고유한 정체성이 없는 경우

다중 그래프는 다음과 같이 정의된다.

'''V'''는 집합이며, '''정점''' 또는 '''노드'''라고 불린다.
'''E'''는 정점의 순서가 없는 쌍의 멀티셋이며, '''변''' 또는 '''선'''이라고 불린다.

2. 1. 2. 변에 고유한 정체성이 있는 경우

다중 그래프

G=(V,E,\partial)

는 다음과 같은 순서쌍이다.

$V$ 는 집합이다. 이를 '''꼭짓점의 집합'''이라고 하며, 그 원소를 '''꼭짓점'''(vertex^영어)이라고 한다.
$E$ 는 집합이다. 이를 '''변의 집합'''이라고 하며, 그 원소를 '''변'''(edge^영어)이라고 한다.
$\partial\colon E\to S^2(V)$ 는 함수이다. 여기서 $S^2(V)=\{\{u,v\}\colon u,v\in V\}$ 이다. 만약 $\partial e=\{u,v\}$ 라면, $u$ 와 $v$ 를 $e$ 의 '''끝점'''(endpoint^영어)이라고 한다. 양 끝점이 같은 변을 '''고리'''(loop|루프^영어)라고 한다. 다중 그래프 $G$ 의 꼭짓점의 집합은 $V(G)$ , 변의 집합은 $E(G)$ 로 쓴다.

다중 그래프는 ''G'' := (''V'', ''E'', ''r'')로 구성된 순서쌍으로 정의할 수도 있다.

''V''는 ''정점'' 또는 ''노드''의 집합이다.
''E''는 ''변'' 또는 ''선''의 집합이다.
''r'' : ''E'' → {(''x'',''y'') : ''x'', ''y'' ∈ ''V''}, 각 변에 정점 쌍을 할당한다.

일부 저자는 다중 그래프가 루프를 가질 수 있도록 허용하는데, 즉 정점을 자기 자신에 연결하는 변을 허용한다.^[2] 반면, 다른 저자는 이러한 그래프를 '''의사 그래프'''라고 부르며, 루프가 없는 경우에만 다중 그래프라는 용어를 사용한다.^[3]

2. 2. 유향 다중 그래프

변에 방향성이 있는 다중 그래프는 순서쌍 (V, A) 또는 (V, A, s, t)로 표현될 수 있다. 여기서 V는 꼭짓점 집합, A는 유향 변(호, 화살표) 집합, s는 각 변의 시작 꼭짓점을 나타내는 함수, t는 각 변의 끝 꼭짓점을 나타내는 함수이다.

다중 유향 그래프는 동일한 출발 노드와 도착 노드를 가진 다중 호(여러 개의 변)를 가질 수 있다는 점에서 유향 그래프와 다르다.

2. 2. 1. 변에 고유한 정체성이 없는 경우

다중 그래프는 유향 그래프의 일종으로, 동일한 출발 노드와 도착 노드를 가진 다중 호(여러 개의 변)를 가질 수 있다. 다중 유향 그래프는 꼭짓점 집합과 꼭짓점 순서쌍의 멀티셋(중복을 허용하는 집합)으로 정의된다.

2. 2. 2. 변에 고유한 정체성이 있는 경우 (화살집)

다중 그래프 화살통 ''G''는 다음과 같은 4-튜플 순서쌍으로 정의된다.

: ''G'' := (''V'', ''A'', ''s'', ''t'')

''V''는 ''꼭짓점'' 또는 ''노드''의 집합이다.
''A''는 ''변'' 또는 ''선''의 집합이다.
$s : A \rightarrow V$ : 각 변에 그 시작 노드를 할당한다.
$t : A \rightarrow V$ : 각 변에 그 목표 노드를 할당한다.

이 개념은 항공사가 제공하는 가능한 항공편 연결을 모델링하는 데 사용될 수 있다. 이 경우 다중 그래프는 도시들을 연결하는 방향이 있는 평행 변 쌍을 가진 유향 그래프가 되어, 해당 위치들 ''로''와 ''에서'' 모두 비행하는 것이 가능하다는 것을 보여준다.

범주론에서 작은 범주는 연관적인 합성 법칙과 각 꼭짓점에서 합성의 좌항 및 우항 항등원으로 작용하는 구별되는 자체 루프를 갖춘 다중 그래프(자체 식별성을 가진 변)로 정의될 수 있다. 이러한 이유로 범주론에서 용어 ''그래프''는 표준적으로 "다중 그래프"를 의미하며, 범주의 기본 다중 그래프는 '''기본 유향 그래프'''라고 한다.

3. 관련 개념

그래프는 고리가 없고, 두 꼭짓점 사이에 최대 하나의 변이 존재하는 다중 그래프이다.

화살집(quiver|퀴버^영어)은 변이 방향을 갖춘 다중 그래프이다. 즉, 유향 그래프와 다중 그래프의 공통적인 일반화이다.

4. 라벨링

다중 그래프와 다중 유향 그래프는 그래프 라벨링 개념을 지원하지만, 이 경우 용어에 통일성은 없다. 라벨이 지정된 다중 유향 그래프는 라벨이 지정된 꼭짓점과 호(화살표)를 가진다.

4. 1. 정의 1

라벨이 지정된 다중 방향 그래프는 ''라벨이 지정된'' 호(화살표)를 가진 라벨이 지정된 그래프이다.

형식적으로, 라벨이 지정된 다중 방향 그래프 G는 ''라벨이 지정된'' 정점과 호를 가진 다중 그래프이며, 8-튜플(tuple)

G=(\Sigma_V, \Sigma_A, V, A, s, t, \ell_V, \ell_A)

로 표현된다. 여기서:

$V$ 는 정점의 집합이고, $A$ 는 호의 집합이다.
$\Sigma_V$ 와 $\Sigma_A$ 는 사용 가능한 정점 및 호 라벨의 유한 알파벳이다.
$s\colon A\rightarrow\ V$ 와 $t\colon A\rightarrow\ V$ 는 호의 ''시작'' 정점과 ''대상'' 정점을 나타내는 두 개의 맵(map)이다.
$\ell_V\colon V\rightarrow\Sigma_V$ 와 $\ell_A\colon A\rightarrow\Sigma_A$ 는 정점과 호의 라벨링을 설명하는 두 개의 맵이다.

4. 2. 정의 2

라벨이 지정된 다중 방향 그래프는 여러 개의 ''라벨이 지정된'' 호, 즉 동일한 끝 정점과 동일한 호 라벨을 가진 호를 가진 라벨이 지정된 그래프이다. (이 라벨이 지정된 그래프의 개념은 그래프 라벨링 문서에서 제공된 개념과 다르다.)

참조

_[1] 서적 1997
_[2] 서적 2012
_[3] 서적 2002
_[4] 서적 2010
_[5] 서적 2002
_[6] 서적 2012

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

문의하기 : help@durumis.com