그래프 (그래프 이론)

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

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

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

정의

 그래프 이론 용어 문서를 참고하십시오.

그래프 $(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}$는 다음과 같은 쉼표 범주이다.

$\operatorname {Graph} =\operatorname {Set} \downarrow F$

여기서 함자 $F\colon \operatorname {Set} \to \operatorname {Set}$는

$F(S)={\frac {S\times S\setminus \{(s,s)\colon s\in S\}}{(s_{1},s_{2})\sim (s_{2},s_{1})\forall s_{1},s_{2}\in S}}$

$F(f\colon S\to T)\colon \{s_{1},s_{2}\}\mapsto \{f(s_{1}),f(s_{2})\}$

이다.

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

기본 정의

$(V,\sim )$의 변(영어: edge 에지^[*]) $\{v_{1},v_{2}\}$은 $v_{1}\sim v_{2}$이지만 $v_{1}\neq v_{2}$인 두 꼭짓점으로 이루어진 집합이며, 흔히 $v_{1}v_{2}$로 표기한다. 그래프 $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$의 유도 부분 그래프라고 한다.

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

성질

어떤 그래프에 있는 모든 꼭짓점 차수의 합은 이 그래프가 가진 변의 수의 두 배가 된다. 따라서, 꼭짓점 차수의 합은 짝수가 되면, 차수가 홀수인 꼭짓점의 수도 짝수가 된다는 성질을 가진다.

범주론적 성질

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

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

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

그래프의 범주 $\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 _{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}$

그래프의 범주에서, 시작 대상은 공 그래프 $\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}$의 꼭짓점 각각과 변으로 연결되어 있는 경우이다.
• 이분 그래프: 그래프 $G=(V,E)$에서, 꼭짓점 집합 $V$를 두 개의 집합 $V_{1}$와 $V_{2}$로 나누되 모든 변은 $V_{1}$의 꼭짓점과 $V_{2}$의 꼭짓점과 동시에 접하도록 할 수 있는 경우 $G$를 이분 그래프라고 한다.
• 정규 그래프는 모든 꼭짓점이 동일한 수의 이웃(즉, 동일한 차수)을 가지는 그래프이다. 정규 그래프에서 꼭짓점에 연결된 이웃이 k 개인 경우, k-정규 그래프라 불린다.
• 평면 그래프는 평면 상에 꼭짓점과 변을 그리되 변과 변이 꼭짓점이 아닌 곳에서는 교차하지 않도록 그릴 수 있는 그래프이다.
• 나무는 모든 꼭짓점들이 연결되어 있고 순환을 포함하지 않는 그래프이다.
• 숲은 순환을 포함하지 않는 그래프이다.

관련 개념

유향 그래프는 각 변이 방향을 갖춘 그래프이다. 유향 그래프와 구별하기 위해, 그래프를 무향 그래프로 부르는 경우도 있다. 이는 각 변에 방향 구조를 갖춘 그래프로 볼 수 있다.

고리 그래프(영어: loop graph)는 양끝이 같은 꼭짓점인 변을 허용하는 그래프이며, 이러한 변을 고리(영어: loop 루프^[*])라고 한다. 이는 각 꼭짓점에 $\{0,1\}$의 원소(고리의 유무 여부)를 추가한 그래프로 볼 수 있다.

다중 그래프(영어: multigraph)는 무향 또는 유향 그래프의 정의와 유사하나, 변 집합 $E$가 집합 대신 중복집합이다. 즉, 두 꼭짓점 사이에 여러 개의 변이 있을 수 있다. 이는 각 변에 양의 정수(변의 중복수)를 추가한 그래프로 볼 수 있다. 그래프를 다중 그래프와 구별하기 위해 단순 그래프(영어: simple graph)라고 하기도 한다.

마찬가지로, 고리 다중 그래프나 유향 다중 그래프 등을 정의할 수 있다.

응용

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

같이 보기

• 그래프 이론
• 그래프 이론 용어
• 유향 그래프
• 매트로이드

외부 링크

• “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》 (영어).