그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
6개의 꼭짓점과 7개의 변을 갖는 그래프

그래프 이론에서, 그래프(영어: graph, 문화어: 그라프)는 일련의 꼭짓점들과 그 사이를 잇는 변들로 구성된 조합론적 구조이다.

정의[편집]

그래프 (V,\sim)는 집합 VV 위의 반사 대칭관계 \sim순서쌍이다. 그래프 (V,\sim)꼭짓점(-點, 영어: vertex 버텍스[*])은 V의 원소이며, u,v\in V에 대하여 u\sim v라면 uv인접(영어: 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)\}

이다.

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

기본 정의[편집]

(V,\sim)(영어: edge 에지[*]) \{v_1,v_2\}v_1\sim v_2이지만 v_1\ne v_2인 두 꼭짓점으로 이루어진 집합이며, 흔히 v_1v_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가 단사 준동형사상이라면, GH부분 그래프라고 한다. 또한, 만약 u,v\in G에 대하여

u\sim v\iff \phi(u)\sim\phi(v)

라면, GH유도 부분 그래프라고 한다.

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

성질[편집]

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

범주론적 성질[편집]

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

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

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

그래프의 범주에서, 시작 대상은 공 그래프 \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번째 꼭짓점으로 대응시키는 그래프 준동형사상이다.

위상수학적 성질[편집]

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

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

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

그래프의 경우, 세포 복합체이므로 세포 호몰로지를 정의할 수 있다. (이는 특이 호몰로지와 일치한다.) 그래프는 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_\inftyC_\infty\sqcup C_\infty는 동형이 아니지만 기본 동치이다.[1]

[편집]

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

관련 개념[편집]

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

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

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

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

응용[편집]

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

참고 문헌[편집]

바깥 고리[편집]

같이 보기[편집]