그래프 (그래프 이론)

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

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

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

정의

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

그래프 $(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》 (영어).