그래프 (그래프 이론)

다른 뜻에 대해서는 그래프 문서를 참고하십시오.

수학에서 그래프(영어: graph, 문화어: 그라프)는 일련의 꼭짓점들과 그 사이를 잇는 변들로 구성된 조합론적 구조이다. 그래프를 연구하는 수학의 분야를 그래프 이론이라고 한다. “그래프”라는 용어는 1878년 J. J. 실베스터에 의해 처음 사용되었다.

6개의 꼭짓점과 7개의 변을 갖는 그래프

그래프는 꼭짓점은 점으로, 변은 점과 점을 잇는 선으로 평면 위에 그려서 나타낸다. 일반적으로 변을 나타내는 선은 끝점이 아닌 꼭짓점을 나타내는 점에서 교차하지 않도록 그리며, 이는 자명하게 항상 가능하다. 점이나 선의 모양은 나타내는 그래프와 무관하다. 오직 점과 선의 연결 관계만 나타내는 그래프에 대한 정보를 제공한다.

그래프의 변은 방향을 갖지 않으며, 그래프의 두 꼭짓점 사이에는 하나 이하의 변이 존재한다. 그래프는 유향 그래프와의 구분을 위해 무향 그래프(영어: undirectd graph)라고 부르기도 한다. 또한, 다중 그래프와의 구분을 위해 단순 그래프(영어: simple graph)라고 부르기도 한다.

정의

그래프 $(V,\sim )$는 집합 $V$와 $V$ 위의 반사 대칭관계 $\sim$의 순서쌍이다. 그래프 $(V,\sim )$의 꼭짓점(-點, 영어: vertex 버텍스^[*])은 $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 )$의 변(영어: edge 에지^[*]) $\{v_{1},v_{2}\}$은 $v_{1}\sim v_{2}$이지만 $v_{1}\neq v_{2}$인 두 꼭짓점으로 이루어진 집합이며, 흔히 $v_{1}v_{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 _{G}v)\lor (u,v\in V(H)\land u\sim _{H}v)$

텐서곱

그래프의 범주는 유한 곱을 갖는다. 이를 텐서곱(영어: 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_{1}v_{1}\in E(G)\land u_{2}=v_{2})\lor (u_{1}=v_{1}\land u_{2}v_{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-정규 그래프라 불린다.
• 평면 그래프는 평면 상에 꼭짓점과 변을 그리되 변과 변이 꼭짓점이 아닌 곳에서는 교차하지 않도록 그릴 수 있는 그래프이다.
• 나무는 모든 꼭짓점들이 연결되어 있고 순환을 포함하지 않는 그래프이다.
• 숲은 순환을 포함하지 않는 그래프이다.

예

• 
  유한 그래프 $G_{1}$
• 
  $G_{1}$의 비유도 부분 그래프 $G_{2}$
• 
  그래프 $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 }$는 동형이 아니지만 기본 동치이다.

예

• 공 그래프는 꼭짓점과 변이 둘 다 없는 그래프이다. 즉, $(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)는 양끝이 같은 꼭짓점인 변을 허용하는 그래프이며, 이러한 변을 고리(영어: loop 루프^[*])라고 한다. 이는 각 꼭짓점에 $\{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\}$

응용

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

같이 보기

• 매트로이드

외부 링크

• “Graph”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Graph isomorphism”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Subgraph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Supergraph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Connected graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Graph”. 《nLab》 (영어). 
• “Category of simple graphs”. 《nLab》 (영어).