그래프 (그래프 이론)

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

1. 개요

그래프 이론은 객체 간의 관계를 나타내는 수학적 구조인 그래프를 연구하는 학문이다. 그래프는 정점과 간선으로 구성되며, 간선의 방향 유무, 가중치 부여, 자기 루프 및 다중 간선 허용 여부에 따라 무향, 유향, 가중, 단순, 다중 그래프 등으로 분류된다.

그래프는 위상수학적, 논리학적, 범주론적 성질을 가지며, 다양한 종류의 그래프(정규, 완전, 유한, 연결, 이분, 경로, 평면, 사이클, 트리 등)가 존재한다. 그래프는 분리 합집합, 데카르트 곱, 텐서 곱 등의 연산을 통해 새로운 그래프를 생성하며, 변 수축, 선 그래프, 쌍대 그래프 등의 단항 연산을 통해 그래프를 변환할 수 있다.

그래프 이론은 소셜 네트워크 분석, 추천 시스템, 지식 그래프 등 다양한 분야에 응용되며, 정보과학, 인공지능, 자연어 처리 등에서 핵심적인 역할을 수행한다. 또한, 하이퍼그래프, 단순 복합체, 매트로이드 등으로 일반화되어 더 넓은 범위의 문제를 다룬다.

더 읽어볼만한 페이지

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

그래프 (그래프 이론)
개요
분야	수학, 전산학
연구 분야	그래프 이론 네트워크 이론 조합 최적화 알고리즘
종류
방향 그래프	정점과 방향 간선으로 구성됨
무방향 그래프	정점과 무방향 간선으로 구성됨
가중 그래프	간선에 가중치가 부여된 그래프
연결 그래프	모든 정점 쌍 사이에 경로가 존재하는 그래프
완전 그래프	모든 정점 쌍이 간선으로 연결된 그래프
이분 그래프	정점을 두 그룹으로 나눌 수 있으며, 각 그룹 내 정점끼리는 연결되지 않는 그래프
평면 그래프	평면상에서 간선의 교차 없이 그릴 수 있는 그래프
표현
인접 리스트	각 정점에 연결된 정점의 리스트
인접 행렬	정점 간 연결 관계를 나타내는 행렬
연결 행렬	정점과 간선의 연결 관계를 나타내는 행렬
속성
차수 (Degree)	정점에 연결된 간선의 수
경로 (Path)	정점의 시퀀스
사이클 (Cycle)	시작 정점과 끝 정점이 같은 경로
연결 요소 (Connected component)	연결된 정점들의 최대 집합
거리 (Distance)	두 정점 사이의 최단 경로 길이
지름 (Diameter)	그래프 내 가장 먼 두 정점 사이의 거리
클러스터링 계수 (Clustering coefficient)	정점 주변의 연결 정도
알고리즘
탐색	깊이 우선 탐색 (DFS) 너비 우선 탐색 (BFS)
최단 경로	다익스트라 알고리즘 벨만-포드 알고리즘 플로이드-워셜 알고리즘
최소 신장 트리	프림 알고리즘 크루스칼 알고리즘
위상 정렬	방향 비순환 그래프의 정점을 정렬하는 알고리즘
네트워크 플로우	포드-풀커슨 알고리즘 에드몬드-카프 알고리즘
응용
소셜 네트워크 분석	사용자 간 관계 분석
웹 검색	웹 페이지 간 링크 분석
추천 시스템	사용자-아이템 관계 분석
교통망 분석	도로망, 철도망 분석
통신망 분석	네트워크 장비 간 연결 분석
생물 정보학	유전자, 단백질 간 상호작용 분석

2. 정의

그래프 이론에서 정의는 다양하며, 그래프와 관련된 수학적 구조를 정의하는 여러 방법이 있다.

'''그래프''' ('''무향 그래프''' 또는 '''단순 그래프''')^[14]는 순서쌍 이다. 여기서 는 꼭짓점(vertex)이라고 불리는 원의 집합이고, 는 꼭짓점 쌍의 집합이며, 그 원소는 변(edge)이라고 불린다.
'''루프'''(자기 루프): 꼭짓점을 그 자신과 연결하는 변이다.^[15]
'''다중 그래프''': 두 꼭지점 사이에 여러 개의 변(다중 변)이 있는 그래프이다.^[16]^[17]

변 {}에 포함된 꼭짓점 와 는 그 변의 "단점"이라고 불린다. 변은 꼭짓점 와 를 "연결(join)", 나 에 "접속한다(incident)"라고 표현한다. 꼭지점이 어떤 변에도 포함되지 않는 경우도 있으며, 이 경우에는 다른 어떤 꼭짓점과도 연결되지 않는다.

그래프의 변은 "인접 관계"라고 불리는 꼭짓점 간의 대칭 관계를 정의한다. 구체적으로, 가 변이면, 두 꼭짓점 와 는 "인접(adjacent)"해 있다.

3개의 정점과 4개의 유향 변으로 구성된 유향 그래프 (이중 화살표는 양방향 유향 변 2개를 나타냄)

'''유향 그래프(:en:Directed graph)''' (directed graph, digraph): 변에 방향이 있는 그래프이다.

'''혼합 그래프(mixed graph)''': 일부 변은 유향, 일부 변은 무향인 그래프이다.

10개의 정점과 12개의 변으로 구성된 가중 그래프의 예시. 변에 붙은 숫자는 가중치(거리, 소요 시간 등)를 나타낸다.

'''가중 그래프(weighted graph)''' 혹은 '''네트워크(network)'''^[20]^[21]: 각 변에 수치(가중치)가 할당된 그래프^[22]이다.

그래프는 표준적으로 CW 복합체의 구조를 가진다. 이 경우, 그래프의 각 꼭짓점은 0-세포에, 변은 1-세포에 대응한다.

'''공 그래프''': 꼭짓점과 변이 둘 다 없는 그래프이다.
'''한원소 그래프''': 한 개의 꼭짓점을 가지고, 변이 없는 그래프이다.
'''무변 그래프''': 변이 없는 그래프이다.
'''완전 그래프''': 모든 꼭짓점이 다른 꼭짓점과 인접해 있는 그래프이다.
'''완전 이분 그래프''': 꼭짓점 집합이 두 그룹으로 나뉘고, 한 그룹의 모든 꼭짓점이 다른 그룹의 모든 꼭짓점과 연결된 그래프이다.
'''이분 그래프''': 꼭짓점 집합을 두 그룹으로 나누어, 같은 그룹 내의 꼭짓점끼리는 연결되지 않도록 할 수 있는 그래프이다.
'''정규 그래프''': 모든 꼭짓점이 동일한 수의 이웃을 가지는 그래프이다.
'''평면 그래프''': 평면 상에 변이 교차하지 않도록 그릴 수 있는 그래프이다.
'''나무''': 모든 꼭짓점이 연결되어 있고 순환을 포함하지 않는 그래프이다.
'''숲''': 순환을 포함하지 않는 그래프이다.

2. 1. 기본 정의

그래프는 순서쌍 로 정의되는데, 여기서 는 ''꼭짓점''들의 집합이고, 는 ''변''들의 집합이다. 변은 꼭짓점들의 순서 없는 쌍 {}으로 표현된다.^[4]

변 {}의 꼭짓점 와 는 변의 ''끝점''이라고 불린다. 이 변은 와 를 ''연결''하고, 이 두 꼭짓점에 ''접속''한다고 한다. 꼭짓점은 변에 속하지 않을 수도 있는데, 이 경우 다른 꼭짓점과 연결되지 않아 ''고립''되었다고 한다. 변 가 존재할 때, 꼭짓점 와 는 ''인접''(adjacent|어자सेंट^영어)한다고 한다.

다중 그래프는 여러 변이 동일한 끝점을 가질 수 있도록 일반화된 그래프이다. 일부 텍스트에서는 다중 그래프를 단순히 그래프라고 부르기도 한다.^[5]

때로는 그래프가 자신을 연결하는 변인 ''루프''를 포함하는 경우도 있다. 이러한 그래프를 ''루프가 있는 그래프''라고 하며, 문맥상 루프가 허용된다는 것이 명확할 때는 단순히 ''그래프''라고도 한다.

2. 2. 그래프의 종류

그래프는 꼭짓점(vertex)과 변(edge)으로 구성된 구조로, 다양한 종류가 있다.

'''무향 그래프'''(Undirected graph): 변에 방향이 없는 그래프이다.^[4] 순서쌍 $(V, E)$로 정의되며, $V$는 꼭짓점의 집합, $E$는 꼭짓점의 순서 없는 쌍 $\{v_1, v_2\}$의 집합이다.
'''유향 그래프'''(Directed graph): 변에 방향이 있는 그래프이다.^[19] 제한적인 의미에서^[19] 유향 그래프는 $(V, E)$로 정의된다. $V$는 꼭짓점의 집합, $E \subseteq \{(x,y) \mid (x,y) \in V^2 \;\textrm{ and }\; x \neq y \}$는 꼭짓점의 순서쌍 집합이다.
'''혼합 그래프'''(Mixed graph): 일부 변은 방향이 있고, 일부 변은 방향이 없는 그래프이다. 혼합 단순 그래프는 순서쌍 $(V, E, A)$로, 혼합 멀티그래프는 $(V, E, A, \phi_E, \phi_A)$로 표현된다.
'''가중 그래프'''(Weighted graph): 각 변에 숫자(가중치)가 할당된 그래프이다.^[6]^[7]
10개의 꼭짓점과 12개의 변을 가진 가중 그래프
가중치는 문제에 따라 비용, 길이, 용량 등을 나타낸다.^[8]

이 외에도 완전 그래프, 정규 그래프, 이분 그래프, 경로 그래프, 평면 그래프, 사이클 그래프, 트리 등 다양한 종류의 그래프가 있다.

3. 그래프의 성질

어떤 그래프에서 모든 꼭짓점 차수의 합은 변의 수의 두 배가 된다. 따라서 꼭짓점 차수의 합은 짝수이며, 차수가 홀수인 꼭짓점의 수도 짝수이다.^[32]

그래프에서 두 변이 공통 정점을 공유하면 '인접'하다고 한다. 유향 그래프에서 두 변이 연속되려면, 첫 번째 변의 머리가 두 번째 변의 꼬리여야 한다. 두 정점이 공통 변을 공유하면 '인접'하다고 하며, 유향 그래프에서는 첫 번째 정점이 꼬리이고 두 번째 정점이 머리일 때 '연속'이라고 한다. 이 때 공통 변은 두 정점을 '연결'한다고 한다. 변과 그 변에 연결된 정점은 '접한다'고 한다.^[32]

정점 하나만 있고 변이 없는 그래프는 '자명 그래프', 정점만 있고 변이 없는 그래프는 '무변 그래프'라고 한다. 정점과 변이 모두 없는 그래프는 '영 그래프'라고도 하지만, 이 용어는 통일되지 않았고 모든 수학자가 사용하는 것은 아니다.^[32]

일반적으로 그래프의 정점은 집합의 원소로서 구별 가능하다. 이런 그래프를 '정점 라벨링 그래프'라고 한다. 그러나 많은 문제에서 정점을 구별할 수 없는 것으로 취급하는 것이 더 낫다. (물론 정점은 그래프 자체의 속성, 예를 들어 연결된 변의 수 등으로 구별될 수 있다.) 변에 라벨이 붙은 그래프는 '변 라벨링 그래프'라고 한다. 변이나 정점에 라벨이 붙은 그래프는 일반적으로 '라벨링 그래프'라고 한다. 정점과 변을 구별할 수 없는 그래프는 '비라벨링 그래프'라고 한다.^[32]

3. 1. 범주론적 성질

그래프의 범주는 그로텐디크 준토포스를 이룬다. 특히, 그래프의 범주는 다음과 같은 성질들을 만족시킨다.

모든 유한 극한이 존재한다.
국소적으로 작은 범주이다. 즉, 두 그래프 사이의 준동형의 모임은 집합을 이룬다.
쌍대 완비 범주이다. 즉, 모든 (작은) 쌍대극한이 존재한다.
데카르트 닫힌 범주이다.

그러나 이 범주는 부분 대상 분류자를 갖지 않아, 토포스가 아니다.

그래프의 범주

\operatorname{Graph}

는 그래프를 그 꼭짓점 집합으로 대응시키는 망각 함자

V\colon\operatorname{Graph}\to\operatorname{Set}

를 갖는다. 이 함자는 극한과 쌍대극한을 보존시키며, 왼쪽·오른쪽 수반 함자를 갖는다.

:

\bar K\dashv V\dashv K

여기서

K\colon\operatorname{Set}\to\operatorname{Graph}

는 완전 그래프 함자이며,

\bar K\colon\operatorname{Set}\to\operatorname{Graph}

는 무변 그래프(완전 그래프의 여 그래프) 함자이다.

그래프의 범주에서, 쌍대곱은 그래프의 분리합집합

G\sqcup H

이며, 구체적으로 다음과 같다.

:

V(G\sqcup H)=V(G)\sqcup V(H)

:

u\sim v\iff (u,v\in V(G)\land u\sim_Gv)\lor (u,v\in V(H)\land u\sim_Hv)

그래프의 범주에서, 곱은 '''텐서곱'''(tensor product^영어)

G\times H

이라고 하며, 다음과 같다.

:

V(G\times H)=V(G)\times V(H)

:

(u_1,u_2)\sim(v_1,v_2)\iff u_1\sim v_1\land u_2\sim v_2

그래프의 범주에서, 시작 대상은 공 그래프

\varnothing

이다 (

V(\varnothing)=E(\varnothing)=\varnothing

). 그래프의 범주에서, 끝 대상은 하나의 꼭짓점만을 갖는 그래프

K_1

이다.

데카르트 닫힌 범주로서, 두 그래프

G,H

사이의 지수 대상

H^G

은 다음과 같다.

:

V(H^G)=\hom_{\operatorname{Graph}}(G,H)

:

\phi\chi\in E(H^G)\iff\forall u,v\in V(G)\colon u\sim v\implies\phi(u)\sim\chi(v)

또한, 이 범주는 자연수 대상

\bar K(\mathbb N)

을 갖는다. 이는 자연수 집합에 대한 무변 그래프이다. 이 경우, 바로 다음 수 함수

s\colon\bar K(\mathbb N)\to\bar K(\mathbb N)

은

n

번째 꼭짓점을

n+1

번째 꼭짓점으로 대응시키는 그래프 준동형이다.

3. 2. 위상수학적 성질

그래프는 CW 복합체이므로, 하우스도르프 파라콤팩트 공간이다.

그래프

G

에 대하여, 다음 두 조건은 서로 동치이다.

$G$ 는 국소 콤팩트 공간이다.
$G$ 는 국소 유한 그래프이다.

그래프

G

에 대하여, 다음 두 조건은 서로 동치이다.

$G$ 는 콤팩트 공간이다.
$G$ 는 유한 그래프이다.

그래프는 CW 복합체이므로 세포 호몰로지를 정의할 수 있다. (이는 특이 호몰로지와 일치한다.) 그래프는 0-세포 및 1-세포만으로 구성되어 있으므로, 0차 및 1차 호몰로지

H_0(G)

,

H_1(G)

만이 자명하지 않다. 0차 베티 수는 연결 성분의 수, 1차 베티 수는 선형독립 순환의 수이다.

3. 3. 논리학적 성질

그래프의 1차 논리 모형 이론은 상당히 약하다. 하나의 1차 논리 명제로 정의할 수 있는 성질들은 다음과 같다.

완전 그래프의 모임 $\forall u\forall v\colon u\sim v$
임의의 자연수 $n$ 에 대하여, $n$ -정규 그래프의 모임
임의의 하나의 유한 그래프 $G$ 만을 포함하는 집합 $\{G\}$
임의의 자연수 $n$ 에 대하여, $n$ 개의 꼭짓점을 갖는 그래프들의 집합

하나의 1차 논리 명제로 정의할 수 없는 성질들은 다음을 들 수 있다.

연결 그래프의 모임
유한 그래프의 집합
짝수 개의 꼭짓점을 갖는 유한 그래프의 집합
이분 그래프의 모임

유한 그래프에 대하여, 기본 동치(elementary equivalence|기본 동치^영어)는 그래프의 동형과 같다.

:

G\cong H\iff\operatorname{Th}(G)=\operatorname{Th}(H)

또한, 임의의 유한 그래프

G

에 대하여,

:

H\models\phi_G\iff H\cong G

인 1차 논리 명제

\phi_G

가 존재한다.

무한 그래프의 경우, 기본 동치이지만 서로 동형이지 않는 두 그래프가 존재한다. 예를 들어, 꼭짓점 집합이

\mathbb Z

이고, 변 집합이

\{(n,(n+1))\colon n\in\mathbb Z\}

인 그래프

C_\infty

를 생각해 보자. 이 경우,

C_\infty

와

C_\infty\sqcup C_\infty

는 동형이 아니지만 기본 동치이다.^[32]

4. 그래프의 종류

그래프는 다양한 종류로 분류될 수 있으며, 각각의 특징에 따라 다음과 같이 나뉜다.

공 그래프: 꼭짓점과 변이 모두 없는 그래프이다.
한원소 그래프: 꼭짓점이 하나뿐이고, 변은 없는 그래프이다.
무변 그래프: 변이 없는 그래프이다.
완전 그래프: 모든 꼭짓점이 서로 연결되어 있는 그래프이다. ''n''개의 꼭짓점을 가진 완전 그래프는 ''n''(''n''-1)/2개의 변을 가지며, 정규 그래프이다.^[1]
이분 그래프: 꼭짓점 집합을 두 그룹으로 나누어, 같은 그룹 내의 꼭짓점끼리는 서로 연결되지 않도록 할 수 있는 그래프이다.
완전 이분 그래프: 이분 그래프 중에서도, 서로 다른 그룹에 속하는 꼭짓점끼리는 모두 연결되어 있는 그래프이다.
정규 그래프: 모든 꼭짓점이 같은 수의 이웃을 가지는 그래프이다. 이웃의 수가 k개이면, k-정규 그래프라고 한다.^[11]
평면 그래프: 평면 위에 변이 서로 교차하지 않도록 그릴 수 있는 그래프이다.
나무: 연결되어 있고 순환이 없는 그래프이다.
숲: 순환이 없는 그래프이다.

4. 1. 유향 그래프

'''유향 그래프''' (또는 '''방향 그래프''')는 간선에 방향이 있는 그래프이다.

제한적이지만 매우 일반적인 의미에서, '''유향 그래프'''는 다음으로 구성된 쌍이다.

꼭짓점 (또는 ''노드'' 또는 ''점'')의 집합
간선 (또는 ''유향 간선'', ''유향 링크'', ''유향 선'', ''화살표'' 또는 ''호'')의 순서쌍 집합으로, 서로 다른 꼭짓점의 순서쌍:

모호성을 피하기 위해, 이러한 유형의 객체를 정확히 '''유향 단순 그래프'''라고 부를 수 있다.

에서 로 향하는 간선 에서 꼭짓점 와 를 간선의 ''끝점''이라고 하며, 는 간선의 ''꼬리'', 는 간선의 ''머리''라고 한다. 간선은 와 를 ''연결''하고 와 에 ''부속''된다고 한다. 꼭짓점은 그래프에 존재할 수 있지만 간선에 속하지 않을 수 있다. 간선 는 의 ''반전 간선''이라고 한다. ''다중 간선''은 꼬리와 머리가 모두 같은 두 개 이상의 간선이다.

다중 간선을 허용하는 더 일반적인 의미에서 유향 그래프는 다음으로 구성된 순서 삼중 로 정의된다.

, ''꼭짓점'' (또는 ''노드'' 또는 ''점'')의 집합
, ''간선'' (또는 ''유향 간선'', ''유향 링크'', ''유향 선'', ''화살표'' 또는 ''호'')의 집합
, 모든 간선을 꼭짓점의 순서쌍에 매핑하는 ''사건 함수'' (즉, 간선은 서로 다른 두 개의 꼭짓점과 연관됨):

모호성을 피하기 위해, 이러한 유형의 객체를 정확히 '''유향 멀티그래프'''라고 부를 수 있다.

''루프''는 꼭짓점을 자신과 연결하는 간선이다. 유향 그래프는 루프를 가질 수 없다. 꼭짓점 를 자신과 연결하는 루프는 간선 (유향 단순 그래프의 경우)이거나 에 부속되기 때문이다 (유향 멀티그래프의 경우). 따라서 루프를 허용하려면 정의를 확장해야 한다. 유향 단순 그래프의 경우, 의 정의를 로 수정해야 한다. 유향 멀티그래프의 경우, 의 정의를 로 수정해야 한다. 모호성을 피하기 위해 이러한 유형의 객체를 각각 정확히 '''루프를 허용하는 유향 단순 그래프'''와 '''루프를 허용하는 유향 멀티그래프''' (또는 ''Quiver'')라고 부를 수 있다.

루프를 허용하는 유향 단순 그래프 의 간선은 의 꼭짓점에 대한 균질 관계 ~이며, 이를 의 ''인접 관계''라고 한다. 각 간선 에 대해, 그 끝점 와 는 서로 ''인접''하다고 하며, 이는 로 표시된다.

''방향 그래프''는 와 중 최대 하나만 그래프의 변일 수 있는 유향 그래프이다. 즉, 방향이 없는 (단순) 그래프의 방향으로 형성될 수 있는 방향 그래프이다.

일부 저자는 "방향 그래프"를 "유향 그래프"와 같은 의미로 사용한다. 일부 저자는 "방향 그래프"를 주어진 무방향 그래프 또는 멀티그래프의 모든 방향을 의미하는 데 사용한다.

4. 2. 정규 그래프

'''정규 그래프'''는 모든 꼭짓점이 같은 수의 인접한 꼭짓점을 갖는, 즉 모든 꼭짓점이 동일한 차수를 갖는 그래프이다. 차수가 ''k''인 정규 그래프는 ''k''-정규 그래프 또는 차수 ''k''의 정규 그래프라고 한다.^[11]

5개의 정점과 10개의 변을 가진 완전 그래프. 각 정점은 다른 모든 정점으로의 변을 갖는다.

'''완전 그래프'''는 각 정점 쌍이 변으로 연결된 그래프이다. 완전 그래프는 가능한 모든 변을 포함한다.

4. 3. 완전 그래프

완전 그래프는 그래프에 속하는 모든 꼭짓점이 다른 모든 꼭짓점과 연결(인접)되어 있는 그래프이다.^[1] 완전 그래프는 모든 꼭짓점 쌍이 변으로 연결된 그래프이다. 완전 그래프는 가능한 모든 변을 포함한다.

완전 그래프의 모든 꼭짓점들은 모두 같은 수의 꼭짓점과 연결되어 있기 때문에 정규 그래프이다. ''n''개의 꼭짓점을 가진 완전 그래프는 ''n''(''n''-1)/2개의 변을 가진다.

4. 4. 유한 그래프

'''유한 그래프'''는 정점 집합과 변 집합이 유한 집합인 그래프이다. 그렇지 않은 경우, '''무한 그래프'''라고 부른다.

그래프 이론에서 논의되는 그래프는 대부분 유한 그래프를 의미한다. 그래프가 무한 그래프인 경우, 보통 명시적으로 언급한다.^[14]

4. 5. 연결 그래프

무향 그래프에서, 두 정점 ''x''와 ''y''를 잇는 경로가 존재하면 순서쌍 는 '연결되었다'고 한다. 경로가 없으면 '단절되었다'고 한다.
연결 그래프는 그래프 내의 모든 정점 쌍이 연결된 무향 그래프이다. 그렇지 않은 그래프는 단절 그래프라고 한다.^[23]

유향 그래프에서, 정점 ''x''에서 ''y''로 가는 유향 경로가 있으면 순서쌍 (''x'', ''y'')는 '강하게 연결되었다'고 한다. 유향 경로는 없지만, 모든 유향 간선을 무향 간선으로 바꾼 후 ''x''에서 ''y''로 가는 무향 경로가 있으면 '약하게 연결되었다'고 한다. 그렇지 않으면 이 순서쌍은 '단절되었다'고 한다.
강하게 연결된 그래프는 모든 정점 쌍이 강하게 연결된 유향 그래프이다. 모든 정점 쌍이 약하게 연결된 유향 그래프는 약하게 연결된 그래프라고 한다. 그 외의 경우는 단절 그래프라고 한다.^[23]

4. 6. 이분 그래프

'''이분 그래프'''는 정점 집합을 두 개의 집합 ''W''와 ''X''로 분할하여, ''W''의 어떤 두 정점도 공통된 변을 공유하지 않고, ''X''의 어떤 두 정점도 공통된 변을 공유하지 않는 단순 그래프이다. 또는, 채색수가 2인 그래프이다.

완전 이분 그래프에서 정점 집합은 두 개의 상호소 집합 ''W''와 ''X''의 합집합이며, ''W''의 모든 정점은 ''X''의 모든 정점에 인접하지만, ''W'' 또는 ''X'' 내에는 변이 없다.

4. 7. 경로 그래프

차수

n \ge 2

인 '''경로 그래프'''(path graph) 또는 '''선형 그래프'''(linear graph)는 정점을

v_1, v_2, \cdots, v_n

순서로 나열할 수 있는 그래프로, 이때 변은

\{v_i, v_{i+1} \}

이며 여기서

i = 1, 2, \cdots, n-1

이다. 경로 그래프는 두 개의 정점을 제외한 모든 정점의 차수가 2이고 나머지 두 정점의 차수가 1인 연결 그래프로 특징지을 수 있다. 경로 그래프가 다른 그래프의 부분 그래프로 나타나면, 해당 그래프의 경로가 된다.

4. 8. 평면 그래프

평면 그래프는 꼭짓점과 변을 평면에 그렸을 때 변끼리 교차하지 않도록 그릴 수 있는 그래프이다.

4. 9. 사이클 그래프

''n'' ≥ 3 차수의 사이클 그래프(원형 그래프)는 꼭짓점을 ''v''₁, ''v''₂, …, ''v''_''n'' 순서로 나열할 수 있으며, 변은 ''i'' = 1, 2, …, ''n'' − 1에 대해 이고, 추가로 변 을 갖는 그래프이다. 모든 꼭짓점의 차수가 2인 연결 그래프로 특징지을 수 있다. 사이클 그래프가 다른 그래프의 부분 그래프로 나타나는 경우, 해당 그래프에서 사이클 또는 회로가 된다.

사이클 그래프는 경로 그래프와 유사하지만, 시작점과 끝점이 연결되어 닫힌 형태를 이룬다는 차이점이 있다.

4. 10. 트리

'''트리'''는 모든 꼭짓점들이 연결되어 있고 순환을 포함하지 않는 그래프이다. 또는 두 정점이 정확히 하나의 경로로 연결된 무방향 그래프, 또는 동등하게 연결된 비순환 무방향 그래프라고도 정의할 수 있다.

'''숲'''은 순환을 포함하지 않는 그래프이다. 또는 두 정점이 최대 하나의 경로로 연결된 무방향 그래프, 또는 동등하게 비순환 무방향 그래프, 또는 동등하게 트리의 분리된 합으로 정의할 수 있다.

4. 11. 폴리트리

'''폴리트리'''(또는 '''유향 트리''', '''지향 트리''', '''단일 연결 네트워크''')는 기저 무향 그래프가 트리인 유향 비순환 그래프(DAG)이다.

'''폴리포레스트'''(또는 '''유향 숲''', '''지향 숲''')는 기저 무향 그래프가 숲인 유향 비순환 그래프이다.

4. 12. 고급 그래프 클래스

페테르센 그래프와 그 일반화
완전 그래프
코그래프
현 그래프
자기 동형 그룹이 큰 다른 그래프: 정점 추이, 호 추이, 거리 추이 그래프
강 정규 그래프와 그 일반화인 거리 정규 그래프

5. 연산

그래프 연산은 초기 그래프로부터 새로운 그래프를 생성하는 다양한 방법을 말한다. 크게 하나의 그래프를 변형하는 단항 연산과 두 개의 그래프를 결합하는 이항 연산으로 나눌 수 있다.

단항 연산에는 변 수축, 선 그래프, 쌍대 그래프, 여 그래프, 그래프 재작성 등이 있다.
이항 연산에는 그래프의 분리 합집합, 그래프의 데카르트 곱, 그래프의 텐서 곱, 그래프의 강한 곱, 그래프의 사전식 곱, 직렬-병렬 그래프 등이 있다.

5. 1. 단항 연산

초기 그래프에서 새로운 그래프를 생성하는 단항 연산은 다음과 같다.

변 수축: 어떤 한 변을 축약하여 양쪽 끝점을 하나의 정점으로 만드는 연산이다.
선 그래프^[28]
쌍대 그래프
여 그래프: 정점 집합은 그대로 두고 인접 관계를 반전시키는 연산이다.^[29]
그래프 재작성

5. 2. 이항 연산

두 그래프에서 새로운 그래프를 생성하는 이항 연산에는 다음이 있다.

그래프의 분리 합집합
그래프의 데카르트 곱
그래프의 텐서 곱
그래프의 강한 곱
그래프의 사전식 곱
직렬-병렬 그래프

6. 관련 개념

그래프 $(V, \sim)$ 는 집합 $V$ 와 $V$ 위의 반사 대칭관계 $\sim$ 의 순서쌍이다. 그래프의 꼭짓점은 $V$ 의 원소이며, $u, v \in V$ 에 대하여 $u \sim v$ 라면 $u$ 와 $v$ 는 인접한다. $(V, \sim)$ 의 변은 $v_1 \sim v_2$ 이지만 $v_1 \ne v_2$ 인 두 꼭짓점으로 이루어진 집합이며, $v_1v_2$ 로 표기한다.

두 그래프 $G, H$ 사이의 준동형 $\phi \colon G \to H$ 는 다음 성질을 만족시키는 함수 $V(G) \to V(H)$ 이다.

임의의 $u, v \in V(G)$ 에 대하여, $u \sim v$ 라면 $\phi(u) \sim \phi(v)$

두 그래프 사이의 전단사 준동형을 동형사상이라고 하며, 동형사상이 존재하는 두 그래프를 서로 동형이라고 한다.

\iota \colon G \to H

가 단사준동형이라면,

G

를

H

의 부분 그래프라고 한다. 만약

u, v \in G

에 대하여

u \sim v \iff \phi(u) \sim \phi(v)

라면,

G

가

H

의 유도 부분 그래프라고 한다.

그래프

G

의 꼭짓점

v \in V(G)

의 차수

\deg v

는 기수

\deg v = |\{u \in V(G) \colon u \sim v\} \setminus \{v\}|

이다. 그래프

G

의 최대 차수

\Delta(G)

는

\Delta(G) = \sup_{v \in V(G)} \deg(v)

이다.

꼭짓점의 집합이 유한 집합인 그래프를 유한 그래프라고 한다. 모든 꼭짓점의 차수가 유한한 그래프를 국소 유한 그래프라고 한다. CW 복합체인 위상 공간)으로서 연결 공간인 그래프를 연결 그래프라고 한다.

그래프는 표준적으로 CW 복합체의 구조를 가진다. 이 경우, 그래프의 각 꼭짓점은 0-세포에, 변은 1-세포에 대응한다.

6. 1. 유향 그래프

'''유향 그래프'''(directed graph, digraph^영어) 또는 '''방향 그래프'''는 변이 방향을 갖춘 그래프이다. 그래프를 유향 그래프와 구별하기 위해 '''무향 그래프'''라고 부르는 경우도 있다.

유향 단순 그래프

G

는 무향 단순 그래프처럼 순서쌍

G=(V,E)

로 정의되지만, 변

e

가 두 꼭짓점의 집합이 아니라 순서쌍으로 정의된다. 즉, 다음과 같은 집합이다.

:

E\subseteq\{(u,v)|(u,v)\in V^2,u\neq v\}

유향 그래프의 변은 화살표(arrow, arc^영어)라고도 부른다. 변

e=(u,v)

을

u

에서

v

로 가는 변이라 표현하며,

u

를 변의 '''꼬리'''(tail^영어),

v

를 변의 '''머리'''(head^영어)라 한다.

유향 다중 그래프

G

는 함수

\phi

가 정의된 튜플

G=(V,E,\phi)

이며, 여기서

\phi

는 다음과 같은 함수이다.

:

\phi \colon E\to \{(u,v)\colon (u,v)\in V^2, u\neq v\}

6. 2. 고리 그래프

'''고리 그래프'''(loop graph^영어)는 양끝이 같은 꼭짓점인 변을 허용하는 그래프이며, 이러한 변을 '''고리'''(loop|루프^영어)라고 한다. 이는 각 꼭짓점에 0 또는 1의 값(고리의 유무)을 추가한 그래프로 볼 수 있다.

6. 3. 다중 그래프

다중 그래프는 변 집합이 집합 대신 중복집합인 그래프로, 두 꼭짓점 사이에 여러 개의 변이 있을 수 있다. 이는 각 변에 양의 정수(변의 중복수)를 추가한 그래프로 볼 수 있다. 다중 그래프와 구별하기 위해 변이 하나만 있는 그래프를 '''단순 그래프'''(simple graph^영어)라고 한다.^[4]^[5]

6. 3. 1. 다중 그래프

'''다중 그래프'''(multigraph^영어)는 같은 두 끝점을 가지는 여러 개의 변을 가질 수 있도록 허용한 그래프이다. 같은 두 끝점을 가지는 변이 최대 하나인 그래프는 '''단순 그래프'''(simple graph^영어)라고 한다.

다중 그래프는 함수

\partial

가 정의된 튜플

G=(V,E,\partial)

이며, 여기서

\partial

는 아래와 같은 함수이다.

:

\partial \colon E\to S^2(V), S^2(V)=\{\{u,v\}\colon u,v\in V\}

\partial e=\{u,v\}

일 때

u

와

v

를

e

의 끝점이라고 하며, 다중 그래프에서 양 끝점이 같은 변을 '''고리'''(loop^영어) 또는 '''루프'''라고 한다.^[4]^[5]

6. 3. 2. 유향 그래프

변이 방향을 가지는 그래프를 '''유향 그래프'''(directed graph, digraph^영어) 또는 '''방향 그래프'''라 한다. ''유향 단순 그래프''

G

는 무향 단순 그래프처럼 순서쌍

G=(V,E)

로 정의되며, 단 변

e

가 두 꼭짓점의 집합이 아니라 순서쌍으로 정의된다. 즉

E

는 아래와 같은 집합이다.

:

E\subseteq\{(u,v)|(u,v)\in V^2,u\neq v\}

유향 그래프의 변은 화살표(arrow, arc^영어)라고도 부른다. 변

e=(u,v)

을

u

에서

v

로 가는 변이라 표현하며,

u

를 변의 '''꼬리'''(tail^영어),

v

를 변의 '''머리'''(head^영어)라 한다.

''유향 다중 그래프''

G

는 함수

\phi

가 정의된 튜플

G=(V,E,\phi)

이며, 여기서

\phi

는 아래와 같은 함수이다.

:

\phi \colon E\to \{(u,v)\colon (u,v)\in V^2, u\neq v\}

7. 응용

그래프 개념은 정보과학 등에서 다양한 데이터를 나타내는 데 응용된다. 소셜 네트워크 분석에 응용되어, 트위터와 같이 한 사용자가 다른 사용자를 팔로우하는 정보 네트워크를 유향 그래프로 모델링할 수 있다.^[9]^[10] 추천 시스템에서 사용자와 아이템 간의 관계를 모델링하고 추천을 생성하는 데 사용될 수 있으며, 지식 그래프를 표현하는 데도 사용된다.

7. 1. 정보과학

그래프 개념은 정보과학 등에서 다양한 데이터를 나타내는 데 응용된다.

컴퓨터 과학에서 유향 그래프는 지식(예: 개념적 그래프), 유한 상태 기계 및 기타 여러 이산 구조를 표현하는 데 사용된다.^[25]
집합 ''X''에 대한 이항 관계 ''R''은 유향 그래프를 정의한다. ''X''의 원소 ''x''가 ''X''의 원소 ''y''의 직접적인 선행 요소인 것은 ''xRy''일 때만 해당한다.
유향 그래프는 한 사용자가 다른 사용자를 팔로우하는 트위터와 같은 정보 네트워크를 모델링할 수 있다.^[9]^[10]^[26]^[27]
특히 규칙적인 유향 그래프의 예로는, 유한 생성군의 케이리 그래프나 슈라이어 코셋 그래프 등이 있다.

7. 2. 소셜 네트워크 분석

그래프 이론은 소셜 네트워크 분석에도 응용된다. 예를 들어, 트위터와 같이 한 사용자가 다른 사용자를 팔로우하는 정보 네트워크를 유향 그래프로 모델링할 수 있다.^[9]^[10]

7. 3. 추천 시스템

그래프 이론은 사용자와 아이템 간의 관계를 모델링하고 추천을 생성하는 데 사용될 수 있다. 예를 들어, 소셜 네트워크 서비스인 트위터에서는 한 사용자가 다른 사용자를 팔로우하는 유향 그래프를 통해 정보 네트워크를 모델링할 수 있다.^[9]^[10]

7. 4. 지식 그래프

컴퓨터 과학에서 유향 그래프는 지식(예: 개념적 그래프) 등을 표현하는 데 사용된다.^[9]^[10]

8. 일반화

하이퍼그래프에서 간선은 임의의 양수 개의 정점을 연결할 수 있다.^[1]

무향 그래프는 1-단순 (간선)과 0-단순체(정점)로 구성된 단순 복합체로 볼 수 있다. 따라서 복합체는 더 높은 차원의 단순체를 허용하므로 그래프의 일반화이다.^[2]

모든 그래프는 매트로이드를 생성한다.^[3]

모형 이론에서 그래프는 단순한 구조이다. 하지만 이 경우 간선의 수에는 제한이 없으며, 이는 임의의 기수가 될 수 있다. 자세한 내용은 연속 그래프를 참조하라.^[4]

계산 생물학에서 파워 그래프 분석은 무향 그래프의 대안적인 표현으로 파워 그래프를 도입한다.^[5]

지리 정보 시스템에서 기하 네트워크는 그래프를 밀접하게 모델링하며, 그래프 이론의 많은 개념을 차용하여 도로 네트워크 또는 유틸리티 그리드에 대한 공간 분석을 수행한다.^[6]

참조

_[1] 서적 Introduction to Graph Theory http://store.doverpu[...] Dover Pub. 2012-08-08
_[2] 간행물 Chemistry and algebra https://books.google[...] 1878-02-07
_[2] 간행물 On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices https://books.google[...] 1878
_[3] 서적 Handbook of graph theory https://books.google[...] CRC Press 2016-02-16
_[4] 문서 See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.
_[5] 문서 Graham et al., p. 5.
_[6] Citation Linear Algebra and Its Applications Brooks Cole
_[7] Citation Java Software Structures Pearson
_[8] 서적 Foundations of Discrete Mathematics PWS-KENT Pub. Co.
_[9] 저널 A social network analysis of Twitter: Mapping the digital humanities community https://serval.unil.[...] 2019-09-16
_[10] 간행물 WTF: The who-to-follow system at Twitter http://dl.acm.org/ci[...]
_[11] 서적 Introduction to Graph Theory http://store.doverpu[...] Dover Pub. 2012-08-08
_[12] 간행물 Chemistry and algebra, https://books.google[...] 1878-02-07
_[12] 간행물 On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, - with three appendices, https://books.google[...] 1878
_[13] 서적 Handbook of graph theory https://books.google[...] CRC Press
_[14] 문서 See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.
_[15] 문서 陳・和田,2014年,p.116
_[16] 문서 陳・和田,2014年,pp115-116
_[17] 문서 Graham et al., p. 5.
_[18] 문서 加納,2013年,pp.72-73
_[19] 문서 陳・和田,2014年,pp116-117
_[20] Citation Linear Algebra and Its Applications https://books.google[...] Brooks Cole
_[21] Citation Java Software Structures Pearson
_[22] 서적 Foundations of Discrete Mathematics PWS-KENT Pub. Co.
_[23] 문서 陳・和田,2014年,p.118
_[24] 문서 加納,2013年,p.74
_[25] 문서 加納,2013年,pp.104-108
_[26] 저널 A social network analysis of Twitter: Mapping the digital humanities community https://serval.unil.[...] 2016
_[27] 간행물 WTF: The who-to-follow system at Twitter http://dl.acm.org/ci[...]
_[28] 문서 白井朋之「The spectrum of the infinitely extended Sierpinski lattice」京都大学数理解析研究所、2-3頁京都大学
_[29] 문서 加納,2013年,p.75
_[30] 간행물 Chemistry and algebra, https://books.google[...] 1878-02-07
_[30] 간행물 On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, — with three appendices, https://books.google[...] 1878
_[31] 서적 Handbook of graph theory https://books.google[...] CRC Press
_[32] 웹인용 Is non-connectedness of graphs first order axiomatizable? https://mathoverflow[...]

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

문의하기 : help@durumis.com