그래프 (조합론)

그래프 6개의 꼭짓점과 7개의 변을 갖는 그래프 수학에서 **그래프**(graph, 그라프)는 일련의 꼭짓점들과 그 사이를 잇는 변들로 구성된 조합론적 구조이다. 그래프를 연구하는 수학의 분야를 **그래프 이론**이라고 한다. “그래프”라는 용어는 1878년 J. J. 실베스터에 의해 처음 사용되었다.See: * J. J. Sylvester (February 7, 1878) "Chemistry and algebra," *Nature*, *17* : 284. 10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a *graph* precisely identical with a Kekuléan diagram or chemicograph." * J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, — with three appendices," *American Journal of Mathematics, Pure and Applied*, *1* (1) : 64–90. 10.2307/2369436. 2369436. The term "graph" first appears in this paper on page 65.postscript = 그래프는 꼭짓점은 점으로, 변은 점과 점을 잇는 선으로 평면 위에 그려서 나타낸다. 일반적으로 변을 나타내는 선은 끝점이 아닌 꼭짓점을 나타내는 점에서 교차하지 않도록 그리며, 이는 자명하게 항상 가능하다. 점이나 선의 모양은 나타내는 그래프와 무관하다. 오직 점과 선의 연결 관계만 나타내는 그래프에 대한 정보를 제공한다. 그래프의 변은 방향을 갖지 않으며, 그래프의 두 꼭짓점 사이에는 하나 이하의 변이 존재한다. 그래프는 유향 그래프와의 구분을 위해 **무향 그래프**(undirectd graph)라고 부르기도 한다. 또한, 다중 그래프와의 구분을 위해 **단순 그래프**(simple graph)라고 부르기도 한다.
# 정의
**그래프** (V,\sim)는 집합 V와 V 위의 반사 대칭관계 \sim의 순서쌍이다. 그래프 (V,\sim)의 **꼭짓점**(-點, 버텍스)은 V의 원소이며, u,v\in V에 대하여 u\sim v라면 u와 v가 **인접**(adjacent)한다고 한다. 두 그래프 G,H 사이의 **준동형**(homomorphism) \phi\colon G\to H은 다음 성질을 만족시키는 함수 V(G)\to V(H)이다. * 임의의 u,v\in V(G)에 대하여, u\sim v라면 \phi(u)\sim\phi(v) 모형 이론의 관점에서, 그래프는 (반사 법칙·대칭 법칙을 만족시키는) 이항 관계 \sim가 주어진 구조이며, 이 경우 그래프의 준동형은 구조의 준동형이다. 그래프와 그래프 준동형은 범주를 이룬다. 이를 \operatorname{Graph}로 표기한다. 그래프는 표준적으로 CW 복합체의 구조를 가진다. 이 경우, 그래프의 각 꼭짓점은 0-세포에, 변은 1-세포에 대응한다.
# 연산

## 꼭짓점과 변
꼭짓점은 **정점** 또는 **노드**라고도 한다. (V,\sim)의 **변**(에지) \\{v_1,v_2\\}은 v_1\sim v_2이지만 v_1\ne v_2인 두 꼭짓점으로 이루어진 집합이며, 흔히 v_1v_2로 표기한다. 이때 v_1와 v_2를 변의 두 **끝점**이라고 하며, 변이 꼭짓점 v_1과 v_2를 **잇는다**(join)고 한다. 그래프 G=(V,\sim)의 꼭짓점의 집합은 V(G)로, 변의 집합은 E(G)로 표기한다.
## 차수
그래프 G의 꼭짓점 v\in V(G)의 **차수**(degree) \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) 이다.
## 동형 사상과 부분 그래프
두 그래프 사이의 전단사 준동형 가운데 역함수 역시 준동형인 것을 **동형 사상**이라고 하며, 동형 사상이 존재하는 두 그래프를 서로 **동형**이라고 한다. 만약 \iota\colon G\to H가 단사 준동형이라면, G를 H의 **부분 그래프**라고 한다. 즉 부분 그래프는 기존 그래프의 꼭짓점과 변들의 부분집합으로 구성된 그래프이다. 또한, 만약 u,v\in G에 대하여 :u\sim v\iff \phi(u)\sim\phi(v) 라면, G가 H의 **유도 부분 그래프**라고 한다. 즉, 유도 부분 그래프는 포함하는 꼭짓점들 사이의 변을 빠짐 없이 포함하는 부분 그래프이다. 만약 \iota\colon G\to H가 전단사 준동형이라면, G가 H의 **신장 부분 그래프**라고 한다. 즉, 신장 부분 그래프는 모든 꼭짓점을 포함하는 부분 그래프이다.
## 분리합집합
분리합집합 그래프의 범주는 작은 쌍대곱을 갖는다. 이는 분리합집합 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 (가군의 텐서곱과 다른 개념이다.)
## 데카르트 곱
그래프 데카르트 곱 그래프의 데카르트 곱 G\mathbin\square H은 다음과 같다. :V(G\mathbin\square H)=V(G)\times V(H) :uv\in E(G\mathbin\square H)\iff(u_1v_1\in E(G)\land u_2=v_2)\lor(u_1=v_1\land u_2v_2\in E(H))
# 종류
* 꼭짓점의 집합이 유한 집합인 그래프를 **유한 그래프**(finite graph)라고 한다. 모든 꼭짓점의 차수가 유한한 그래프를 **국소 유한 그래프**(locally finite graph)라고 한다. * CW 복합체인 위상 공간)으로서 연결 공간인 그래프를 **연결 그래프**라고 한다. * **이분 그래프**: 그래프 G = (V,E)에서, 꼭짓점 집합 V를 두 개의 집합 V_1와 V_2로 나누되 모든 변은 V_1의 꼭짓점과 V_2의 꼭짓점과 동시에 접하도록 할 수 있는 경우 G를 이분 그래프라고 한다. * **정규 그래프**는 모든 꼭짓점이 동일한 수의 이웃(즉, 동일한 차수)을 가지는 그래프이다. 정규 그래프에서 꼭짓점에 연결된 이웃이 k 개인 경우, **k-정규 그래프**라 불린다. * **평면 그래프**는 평면 상에 꼭짓점과 변을 그리되 변과 변이 꼭짓점이 아닌 곳에서는 교차하지 않도록 그릴 수 있는 그래프이다. * **나무**는 모든 꼭짓점들이 연결되어 있고 순환을 포함하지 않는 그래프이다. * **숲**은 순환을 포함하지 않는 그래프이다.
# 예
Basic 그래프 G_1 비유도 부분 그래프 G_2 Induced G의 유도 부분 그래프 유한 그래프 :V(G_1)=\\{1,2,3,4,5,6\\} :E(G_1)=\\{12,13,16,34,35,36,45\\} 는 6개의 꼭짓점과 7개의 변을 갖는다. 꼭짓점 1은 꼭짓점 2, 3, 6과 인접한다. 꼭짓점 1의 차수는 3이며, 그래프 G_1의 차수는 4이다. 유한 그래프 :V(G_2)=\\{1,2,3,4,5\\} :E(G_2)=\\{12,13,34,45\\} 는 G_1의 부분 그래프이다. 꼭짓점 3과 5는 원래 그래프에서 인접하지만, 이 부분 그래프에서는 인접하지 않는다. 따라서, G_2는 G_1의 유도 부분 그래프가 아니다. 유한 그래프 :V(G_2)=\\{1,2,3,4,5\\} :E(G_2)=\\{12,13,34,35,45\\} 는 G_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}는 무변 그래프(완전 그래프의 여 그래프) 함자이다. 그래프의 범주에서, 쌍대곱은 분리합집합이며, 곱은 텐서곱이다. (가군의 텐서곱과 다른 개념이다.) 그래프의 범주에서, 시작 대상은 공 그래프 \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번째 꼭짓점으로 대응시키는 그래프 준동형이다.
## 위상수학적 성질
그래프는 CW 복합체이므로, 하우스도르프 파라콤팩트 공간이다. 그래프 G에 대하여, 다음 두 조건이 서로 동치이다. * G는 국소 콤팩트 공간이다. * G는 국소 유한 그래프이다. 그래프 G에 대하여, 다음 두 조건이 서로 동치이다. * G는 콤팩트 공간이다. * G는 유한 그래프이다. 그래프의 경우, CW 복합체이므로 세포 호몰로지를 정의할 수 있다. (이는 특이 호몰로지와 일치한다.) 그래프는 0-세포 및 1-세포만으로 구성되어 있으므로, 0차 및 1차 호몰로지 H_0(G), H_1(G)만이 자명하지 않다. 0차 베티 수는 연결 성분의 수, 1차 베티 수는 선형독립 순환의 수이다.
## 논리학적 성질
그래프의 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는 동형이 아니지만 기본 동치이다.언어=en
# 예
* **공 그래프**는 꼭짓점과 변이 둘 다 없는 그래프이다. 즉, (V,E)=(\varnothing,\varnothing)이다. * **한원소 그래프**는 한 개의 꼭짓점을 가지고, 변이 없는 그래프이다. 즉, V(G)=\\{\bullet\\}, E(G)=\varnothing이다. * **무변 그래프**는 변이 없는 그래프이다. 즉, E(G)=\varnothing이다. * **완전 그래프**는 그래프에 속하는 모든 꼭짓점이, 다른 꼭짓점과 인접해 있는 그래프이다. ** 완전 그래프의 꼭짓점들은 모두 같은 개수의 꼭짓점과 연결되어 있기 때문에 완전 그래프는 정규 그래프이다. n개의 꼭짓점을 가진 완전 그래프는 n(n-1)/2개의 변을 가진다. * **완전 이분 그래프**는 꼭짓점의 집합이 V_1과 V_2의 합집합이고, 모든 V_1의 꼭짓점이 V_2의 꼭짓점 각각과 변으로 연결되어 있는 경우이다.
# 관련 구조
**유향 그래프**는 각 변이 방향을 갖춘 그래프이다. 유향 그래프와 구별하기 위해, 그래프를 **무향 그래프**로 부르는 경우도 있다. 이는 각 변에 방향 구조를 갖춘 그래프로 볼 수 있다 (양향적인 변도 허용되어야 한다). **고리 그래프**(loop graph)는 양끝이 같은 꼭짓점인 변을 허용하는 그래프이며, 이러한 변을 **고리**(루프)라고 한다. 이는 각 꼭짓점에 \\{0,1\\}의 원소(고리의 유무 여부)를 추가한 그래프로 볼 수 있다. **다중 그래프**(multigraph)는 무향 또는 유향 그래프의 정의와 유사하나, 변 집합 E가 집합 대신 중복집합이다. 즉, 두 꼭짓점 사이에 여러 개의 변이 있을 수 있다. 이는 각 변에 양의 정수(변의 중복수)를 추가한 그래프로 볼 수 있다. 그래프를 다중 그래프와 구별하기 위해 **단순 그래프**(simple graph)라고 하기도 한다. 마찬가지로, **고리 다중 그래프**나 **유향 다중 그래프** 등을 정의할 수 있다.
## 다중 그래프
다중 그래프 다중 그래프의 예시. 회색의 원은 꼭짓점을, 푸른 선은 고리를, 붉은 선은 중복되는 변을, 검은 선은 중복되지 않는 변을 나타낸다. 같은 두 끝점을 가지는 여러 개의 변을 가질 수 있도록 허용한 그래프를 **다중 그래프**(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) 또는 **루프**라고 한다.
## 유향 그래프
유향 그래프 3개의 꼭짓점과 4개의 변을 가지는 그래프의 예시. 양쪽 화살표는 서로 반대 방향으로 가는 두 화살표를 의미한다. 변이 방향을 가지는 그래프를 **유향 그래프**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\\}
# 응용
그래프의 개념은 정보과학 등에서 다양한 데이터를 나타내기 위해 응용된다.