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

그래프 ${\displaystyle (V,\sim )}$는 집합 ${\displaystyle V}$와 ${\displaystyle V}$ 위의 반사 대칭관계 ${\displaystyle \sim }$의 순서쌍이다. 그래프 ${\displaystyle (V,\sim )}$의 꼭짓점(-點, 영어: vertex 버텍스^[*])은 ${\displaystyle V}$의 원소이며, ${\displaystyle u,v\in V}$에 대하여 ${\displaystyle u\sim v}$라면 ${\displaystyle u}$와 ${\displaystyle v}$가 인접(영어: adjacent)한다고 한다.

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

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

모형 이론의 관점에서, 그래프는 (반사 법칙·대칭 법칙을 만족시키는) 이항 관계 ${\displaystyle \sim }$가 주어진 구조이며, 이 경우 그래프의 준동형은 구조의 준동형이다. 범주론의 관점에서, 그래프의 범주 ${\displaystyle \operatorname {Graph} }$는 다음과 같은 쉼표 범주이다.

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

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

${\displaystyle 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}}}$

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

이다.

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

${\displaystyle (V,\sim )}$의 변(영어: edge 에지^[*]) ${\displaystyle \{v_{1},v_{2}\}}$은 ${\displaystyle v_{1}\sim v_{2}}$이지만 ${\displaystyle v_{1}\neq v_{2}}$인 두 꼭짓점으로 이루어진 집합이며, 흔히 ${\displaystyle v_{1}v_{2}}$로 표기한다. 그래프 ${\displaystyle G=(V,\sim )}$의 꼭짓점의 집합은 ${\displaystyle V(G)}$로, 변의 집합은 ${\displaystyle E(G)}$로 표기한다.

그래프 ${\displaystyle G}$의 꼭짓점 ${\displaystyle v\in V(G)}$의 차수(영어: degree) ${\displaystyle \deg v}$는 기수

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

이다. 그래프 ${\displaystyle G}$의 최대 차수 ${\displaystyle \Delta (G)}$는

${\displaystyle \Delta (G)=\sup _{v\in V(G)}\deg(v)}$

이다.

두 그래프 사이의 전단사 준동형을 동형사상이라고 하며, 동형사상이 존재하는 두 그래프를 서로 동형이라고 한다. 만약 ${\displaystyle \iota \colon G\to H}$가 단사준동형이라면, ${\displaystyle G}$를 ${\displaystyle H}$의 부분 그래프라고 한다. 또한, 만약 ${\displaystyle u,v\in G}$에 대하여

${\displaystyle u\sim v\iff \phi (u)\sim \phi (v)}$

라면, ${\displaystyle G}$가 ${\displaystyle H}$의 유도 부분 그래프라고 한다.

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

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

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

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

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

그래프의 범주 ${\displaystyle \operatorname {Graph} }$는 그래프를 그 꼭짓점 집합으로 대응시키는 망각 함자 ${\displaystyle V\colon \operatorname {Graph} \to \operatorname {Set} }$를 갖는다. 이 함자는 극한과 쌍대극한을 보존시키며, 왼쪽·오른쪽 수반 함자를 갖는다.

${\displaystyle {\bar {K}}\dashv V\dashv K}$

여기서 ${\displaystyle K\colon \operatorname {Set} \to \operatorname {Graph} }$는 완전 그래프 함자이며, ${\displaystyle {\bar {K}}\colon \operatorname {Set} \to \operatorname {Graph} }$는 무변 그래프(완전 그래프의 여 그래프) 함자이다.

그래프의 범주에서, 쌍대곱은 그래프의 분리합집합 ${\displaystyle G\sqcup H}$이며, 구체적으로 다음과 같다.

${\displaystyle V(G\sqcup H)=V(G)\sqcup V(H)}$

${\displaystyle 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) ${\displaystyle G\times H}$이라고 하며, 다음과 같다.

${\displaystyle V(G\times H)=V(G)\times V(H)}$

${\displaystyle (u_{1},u_{2})\sim (v_{1},v_{2})\iff u_{1}\sim v_{1}\land u_{2}\sim v_{2}}$

그래프의 범주에서, 시작 대상은 공 그래프 ${\displaystyle \varnothing }$이다 (${\displaystyle V(\varnothing )=E(\varnothing )=\varnothing }$). 그래프의 범주에서, 끝 대상은 하나의 꼭짓점만을 갖는 그래프 ${\displaystyle K_{1}}$이다.

데카르트 닫힌 범주로서, 두 그래프 ${\displaystyle G,H}$ 사이의 지수 대상 ${\displaystyle H^{G}}$은 다음과 같다.

${\displaystyle V(H^{G})=\hom _{\operatorname {Graph} }(G,H)}$

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

또한, 이 범주는 자연수 대상 ${\displaystyle {\bar {K}}(\mathbb {N} )}$을 갖는다. 이는 자연수 집합에 대한 무변 그래프이다. 이 경우, 바로 다음 수 함수 ${\displaystyle s\colon {\bar {K}}(\mathbb {N} )\to {\bar {K}}(\mathbb {N} )}$은 ${\displaystyle n}$번째 꼭짓점을 ${\displaystyle n+1}$번째 꼭짓점으로 대응시키는 그래프 준동형이다.

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

그래프 ${\displaystyle G}$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle G}$는 국소 콤팩트 공간이다.
• ${\displaystyle G}$는 국소 유한 그래프이다.

그래프 ${\displaystyle G}$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle G}$는 콤팩트 공간이다.
• ${\displaystyle G}$는 유한 그래프이다.

그래프의 경우, CW 복합체이므로 세포 호몰로지를 정의할 수 있다. (이는 특이 호몰로지와 일치한다.) 그래프는 0-세포 및 1-세포만으로 구성되어 있으므로, 0차 및 1차 호몰로지 ${\displaystyle H_{0}(G)}$, ${\displaystyle H_{1}(G)}$만이 자명하지 않다. 0차 베티 수는 연결 성분의 수, 1차 베티 수는 선형독립 순환의 수이다.

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

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

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

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

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

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

또한, 임의의 유한 그래프 ${\displaystyle G}$에 대하여,

${\displaystyle H\models \phi _{G}\iff H\cong G}$

인 1차 논리 명제 ${\displaystyle \phi _{G}}$가 존재한다.

무한 그래프의 경우, 기본 동치이지만 서로 동형이지 않는 두 그래프가 존재한다. 예를 들어, 꼭짓점 집합이 ${\displaystyle \mathbb {Z} }$이고, 변 집합이 ${\displaystyle \{(n,(n+1))\colon n\in \mathbb {Z} \}}$인 그래프 ${\displaystyle C_{\infty }}$를 생각해 보자. 이 경우, ${\displaystyle C_{\infty }}$와 ${\displaystyle C_{\infty }\sqcup C_{\infty }}$는 동형이 아니지만 기본 동치이다.^[3]

• 공 그래프는 꼭짓점과 변이 둘 다 없는 그래프이다. 즉, ${\displaystyle (V,E)=(\varnothing ,\varnothing )}$이다.
• 한원소 그래프는 한 개의 꼭짓점을 가지고, 변이 없는 그래프이다. 즉, ${\displaystyle V(G)=\{\bullet \}}$, ${\displaystyle E(G)=\varnothing }$이다.
• 무변 그래프는 변이 없는 그래프이다. 즉, ${\displaystyle E(G)=\varnothing }$이다.
• 완전 그래프는 그래프에 속하는 모든 꼭짓점이, 다른 꼭짓점과 인접해 있는 그래프이다.
  • 완전 그래프의 꼭짓점들은 모두 같은 개수의 꼭짓점과 연결되어 있기 때문에 완전 그래프는 정규 그래프이다. ${\displaystyle n}$개의 꼭짓점을 가진 완전 그래프는 ${\displaystyle n(n-1)/2}$개의 변을 가진다.
• 완전 이분 그래프는 꼭짓점의 집합이 ${\displaystyle V_{1}}$과 ${\displaystyle V_{2}}$의 합집합이고, 모든 ${\displaystyle V_{1}}$의 꼭짓점이 ${\displaystyle V_{2}}$의 꼭짓점 각각과 변으로 연결되어 있는 경우이다.
• 이분 그래프: 그래프 ${\displaystyle G=(V,E)}$에서, 꼭짓점 집합 ${\displaystyle V}$를 두 개의 집합 ${\displaystyle V_{1}}$와 ${\displaystyle V_{2}}$로 나누되 모든 변은 ${\displaystyle V_{1}}$의 꼭짓점과 ${\displaystyle V_{2}}$의 꼭짓점과 동시에 접하도록 할 수 있는 경우 ${\displaystyle G}$를 이분 그래프라고 한다.
• 정규 그래프는 모든 꼭짓점이 동일한 수의 이웃(즉, 동일한 차수)을 가지는 그래프이다. 정규 그래프에서 꼭짓점에 연결된 이웃이 k 개인 경우, k-정규 그래프라 불린다.
• 평면 그래프는 평면 상에 꼭짓점과 변을 그리되 변과 변이 꼭짓점이 아닌 곳에서는 교차하지 않도록 그릴 수 있는 그래프이다.
• 나무는 모든 꼭짓점들이 연결되어 있고 순환을 포함하지 않는 그래프이다.
• 숲은 순환을 포함하지 않는 그래프이다.

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

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

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

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

같은 두 끝점을 가지는 여러 개의 변을 가질 수 있도록 허용한 그래프를 다중 그래프(영어: multigraph)라 한다. 같은 두 끝점을 가지는 변이 최대 하나인 그래프는 단순 그래프(영어: simple graph)라 한다. 다중 그래프는 함수 ${\displaystyle \partial }$가 정의된 튜플 ${\displaystyle G=(V,E,\partial )}$이며, 여기서 ${\displaystyle \partial }$는 아래와 같은 함수이다.

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

${\displaystyle \partial e=\{u,v\}}$일 때 ${\displaystyle u}$와 ${\displaystyle v}$를 ${\displaystyle e}$의 끝점이라고 하며, 다중 그래프에서 양 끝점이 같은 변을 고리(영어: loop) 또는 루프라고 한다.

변이 방향을 가지는 그래프를 유향 그래프영어: directed graph, digraph) 또는 방향 그래프라 한다. 유향 단순 그래프 ${\displaystyle G}$는 무향 단순 그래프처럼 순서쌍 ${\displaystyle G=(V,E)}$로 정의되며, 단 변 ${\displaystyle e}$가 두 꼭짓점의 집합이 아니라 순서쌍으로 정의된다. 즉 ${\displaystyle E}$는 아래와 같은 집합이다.

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

유향 그래프의 변은 화살표(영어: arrow, arc)라고도 부른다. 변 ${\displaystyle e=(u,v)}$을 ${\displaystyle u}$에서 ${\displaystyle v}$로 가는 변이라 표현하며, ${\displaystyle u}$를 변의 꼬리(영어: tail), ${\displaystyle v}$를 변의 머리(영어: head)라 한다.

유향 다중 그래프 ${\displaystyle G}$는 함수 ${\displaystyle \phi }$가 정의된 튜플 ${\displaystyle G=(V,E,\phi )}$이며, 여기서 ${\displaystyle \phi }$는 아래와 같은 함수이다.

${\displaystyle \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》 (영어).