그래프 (그래프 이론) 문서 원본 보기

{{위키데이터 속성 추적}}
{{다른 뜻|그래프}}
[[파일:6n-graf.svg|섬네일|6개의 [[꼭짓점]]과 7개의 변을 갖는 그래프]]
[[수학]]에서 '''그래프'''({{llang|en|graph}}, {{문화어|그라프}})는 일련의 [[꼭짓점]]들과 그 사이를 잇는 변들로 구성된 [[조합론]]적 구조이다. 그래프를 연구하는 수학의 분야를 '''[[그래프 이론]]'''이라고 한다. “그래프”라는 용어는 1878년 [[제임스 조지프 실베스터|J. J. 실베스터]]에 의해 처음 사용되었다.<ref>See:
* J. J. Sylvester (February 7, 1878) [https://books.google.com/books?id=KcoKAAAAYAAJ&vq=Sylvester&pg=PA284#v=onepage&q&f=false "Chemistry and algebra,"] ''Nature'', ''17'' : 284. {{doi|10.1038/017284a0}}. From page 284: "Every invariant and covariant thus becomes expressible by a ''graph'' precisely identical with a Kekuléan diagram or chemicograph."
* J. J. Sylvester (1878) [https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64#v=onepage&q&f=false "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, — with three appendices,"] ''American Journal of Mathematics, Pure and Applied'', ''1'' (1) : 64–90. {{doi|10.2307/2369436}}. {{JSTOR|2369436}}. The term "graph" first appears in this paper on page 65.</ref><ref>{{서적 인용
 | title = Handbook of graph theory
 | first1 = Jonathan L.
 | last1 = Gross
 | first2 = Jay
 | last2 = Yellen
 | publisher = CRC Press
 | year = 2004
 | page = [https://books.google.com/books?id=mKkIGIea_BkC&pg=PA35&lpg=PA35 35]
 | isbn = 978-1-58488-090-5
 | url = https://books.google.com/?id=mKkIGIea_BkC
 | postscript = <!--None-->}}</ref>

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

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

== 정의 ==
'''그래프''' <math>(V,\sim)</math>는 집합 <math>V</math>와 <math>V</math> 위의 [[반사관계|반사]] [[대칭관계]] <math>\sim</math>의 [[순서쌍]]이다. 그래프 <math>(V,\sim)</math>의 '''꼭짓점'''(-點, {{llang|en|vertex|버텍스}})은 <math>V</math>의 원소이며, <math>u,v\in V</math>에 대하여 <math>u\sim v</math>라면 <math>u</math>와 <math>v</math>가 '''인접'''({{llang|en|adjacent}})한다고 한다.

두 그래프 <math>G,H</math> 사이의 '''[[준동형]]'''({{llang|en|homomorphism}}) <math>\phi\colon G\to H</math>은 다음 성질을 만족시키는 [[함수]] <math>V(G)\to V(H)</math>이다.
* 임의의 <math>u,v\in V(G)</math>에 대하여, <math>u\sim v</math>라면 <math>\phi(u)\sim\phi(v)</math>

[[모형 이론]]의 관점에서, 그래프는 ([[반사관계|반사 법칙]]·[[대칭관계|대칭 법칙]]을 만족시키는) [[이항 관계]] <math>\sim</math>가 주어진 [[구조 (논리학)|구조]]이며, 이 경우 그래프의 준동형은 구조의 준동형이다. 그래프와 그래프 준동형은 [[범주 (수학)|범주]]를 이룬다. 이를 <math>\operatorname{Graph}</math>로 표기한다.

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

== 연산 ==
=== 꼭짓점과 변 ===
꼭짓점은 '''정점''' 또는 '''노드'''라고도 한다. <math>(V,\sim)</math>의 '''변'''({{llang|en|edge|에지}}) <math>\{v_1,v_2\}</math>은 <math>v_1\sim v_2</math>이지만 <math>v_1\ne v_2</math>인 두 꼭짓점으로 이루어진 집합이며, 흔히 <math>v_1v_2</math>로 표기한다. 이때 <math>v_1</math>와 <math>v_2</math>를 변의 두 '''끝점'''이라고 하며, 변이 꼭짓점 <math>v_1</math>과 <math>v_2</math>를 '''잇는다'''({{llang|en|join}})고 한다. 그래프 <math>G=(V,\sim)</math>의 꼭짓점의 집합은 <math>V(G)</math>로, 변의 집합은 <math>E(G)</math>로 표기한다.

=== 차수 ===
그래프 <math>G</math>의 꼭짓점 <math>v\in V(G)</math>의 '''차수'''({{llang|en|degree}}) <math>\deg v</math>는 [[기수 (수학)|기수]]
:<math>\deg v=|\{u\in V(G)\colon u\sim v\}\setminus\{v\}|</math>
이다. 그래프 <math>G</math>의 '''최대 차수''' <math>\Delta(G)</math>는
:<math>\Delta(G)=\sup_{v\in V(G)}\deg(v)</math>
이다.

=== 동형 사상과 부분 그래프 ===
두 그래프 사이의 [[전단사]] 준동형 가운데 역함수 역시 준동형인 것을 '''[[그래프 동형 사상|동형 사상]]'''이라고 하며, 동형 사상이 존재하는 두 그래프를 서로 '''동형'''이라고 한다. 만약 <math>\iota\colon G\to H</math>가 단사 준동형이라면, <math>G</math>를 <math>H</math>의 '''[[부분 그래프]]'''라고 한다. 즉 부분 그래프는 기존 그래프의 꼭짓점과 변들의 부분집합으로 구성된 그래프이다. 또한, 만약 <math>u,v\in G</math>에 대하여
:<math>u\sim v\iff \phi(u)\sim\phi(v)</math>
라면, <math>G</math>가 <math>H</math>의 '''[[유도 부분 그래프]]'''라고 한다. 즉, 유도 부분 그래프는 포함하는 꼭짓점들 사이의 변을 빠짐 없이 포함하는 부분 그래프이다. 만약 <math>\iota\colon G\to H</math>가 전단사 준동형이라면, <math>G</math>가 <math>H</math>의 '''[[신장 부분 그래프]]'''라고 한다. 즉, 신장 부분 그래프는 모든 꼭짓점을 포함하는 부분 그래프이다.

=== 분리합집합 ===
{{본문|분리합집합}}
그래프의 범주는 작은 [[쌍대곱]]을 갖는다. 이는 [[분리합집합]] <math>G\sqcup H</math>이며, 구체적으로 다음과 같다.
:<math>V(G\sqcup H)=V(G)\sqcup V(H)</math>
:<math>u\sim v\iff (u,v\in V(G)\land u\sim_Gv)\lor (u,v\in V(H)\land u\sim_Hv)</math>

=== 텐서곱 ===
그래프의 범주는 유한 [[곱 (범주론)|곱]]을 갖는다. 이를 '''텐서곱'''({{llang|en|tensor product}}) <math>G\times H</math>이라고 하며, 다음과 같다.
:<math>V(G\times H)=V(G)\times V(H)</math>
:<math>(u_1,u_2)\sim(v_1,v_2)\iff u_1\sim v_1\land u_2\sim v_2</math>
([[가군]]의 [[텐서곱]]과 다른 개념이다.)

=== 데카르트 곱 ===
{{본문|그래프 데카르트 곱}}
그래프의 데카르트 곱 <math>G\mathbin\square H</math>은 다음과 같다.
:<math>V(G\mathbin\square H)=V(G)\times V(H)</math>
:<math>uv\in E(G\mathbin\square H)\iff(u_1v_1\in E(G)\land u_2=v_2)\lor(u_1=v_1\land u_2v_2\in E(H))</math>

== 종류 ==
* 꼭짓점의 집합이 [[유한 집합]]인 그래프를 '''유한 그래프'''({{llang|en|finite graph}})라고 한다. 모든 꼭짓점의 차수가 유한한 그래프를 '''국소 유한 그래프'''({{llang|en|locally finite graph}})라고 한다.
* [[CW 복합체]]인 [[위상 공간 (수학)|위상 공간]])으로서 [[연결 공간]]인 그래프를 '''[[연결 그래프]]'''라고 한다.
* '''[[이분 그래프]]''':  그래프 <math>G = (V,E)</math>에서, 꼭짓점 집합 <math>V</math>를 두 개의 집합 <math>V_1</math>와 <math>V_2</math>로 나누되 모든 변은 <math>V_1</math>의 꼭짓점과 <math>V_2</math>의 꼭짓점과 동시에 접하도록 할 수 있는 경우 <math>G</math>를 이분 그래프라고 한다.
* '''[[정규 그래프]]'''는 모든 꼭짓점이 동일한 수의 이웃(즉, 동일한 차수)을 가지는 그래프이다. 정규 그래프에서 꼭짓점에 연결된 이웃이 k 개인 경우, '''k-정규 그래프'''라 불린다.
* '''[[평면 그래프]]'''는 평면 상에 꼭짓점과 변을 그리되 변과 변이 꼭짓점이 아닌 곳에서는 교차하지 않도록 그릴 수 있는 그래프이다.
* '''[[나무 (그래프 이론)|나무]]'''는 모든 꼭짓점들이 [[그래프 이론 용어#용어|연결]]되어 있고 [[순환 (그래프 이론)|순환]]을 포함하지 않는 그래프이다.
* '''[[나무 (그래프 이론)|숲]]'''은 [[순환 (그래프 이론)|순환]]을 포함하지 않는 그래프이다.

== 예 ==
<gallery mode="packed" heights="250px">
Basic graph.jpg|유한 그래프 <math>G_1</math>
Subgraph.jpg|<math>G_1</math>의 비유도 부분 그래프 <math>G_2</math>
Induced subgraph.jpg|그래프 <math>G</math>의 유도 부분 그래프
</gallery>
유한 그래프
:<math>V(G_1)=\{1,2,3,4,5,6\}</math>
:<math>E(G_1)=\{12,13,16,34,35,36,45\}</math>
는 6개의 꼭짓점과 7개의 변을 갖는다. 꼭짓점 1은 꼭짓점 2, 3, 6과 인접한다. 꼭짓점 1의 차수는 3이며, 그래프 <math>G_1</math>의 차수는 4이다.

유한 그래프
:<math>V(G_2)=\{1,2,3,4,5\}</math>
:<math>E(G_2)=\{12,13,34,45\}</math>
는 <math>G_1</math>의 부분 그래프이다. 꼭짓점 3과 5는 원래 그래프에서 인접하지만, 이 부분 그래프에서는 인접하지 않는다. 따라서, <math>G_2</math>는 <math>G_1</math>의 유도 부분 그래프가 아니다.

유한 그래프
:<math>V(G_2)=\{1,2,3,4,5\}</math>
:<math>E(G_2)=\{12,13,34,35,45\}</math>
는 <math>G_1</math>의 유도 부분 그래프이다.

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

=== 범주론적 성질 ===
그래프의 범주는 [[그로텐디크 준토포스]]를 이룬다. 특히, 그래프의 범주는 다음과 같은 성질들을 만족시킨다.
* 모든 유한 [[극한 (범주론)|극한]]이 존재한다.
* [[국소적으로 작은 범주]]이다. 즉, 두 그래프 사이의 준동형의 [[모임 (집합론)|모임]]은 [[집합]]을 이룬다.
* [[쌍대 완비 범주]]이다. 즉, 모든 (작은) [[쌍대극한]]이 존재한다.
* [[데카르트 닫힌 범주]]이다.
그러나 이 범주는 [[부분 대상 분류자]]를 갖지 않아, [[토포스]]가 아니다.

그래프의 범주 <math>\operatorname{Graph}</math>는 그래프를 그 꼭짓점 집합으로 대응시키는 망각 함자 <math>V\colon\operatorname{Graph}\to\operatorname{Set}</math>를 갖는다. 이 함자는 극한과 쌍대극한을 보존시키며, 왼쪽·오른쪽 [[수반 함자]]를 갖는다.
:<math>\bar K\dashv V\dashv K</math>
여기서 <math>K\colon\operatorname{Set}\to\operatorname{Graph}</math>는 [[완전 그래프]] 함자이며, <math>\bar K\colon\operatorname{Set}\to\operatorname{Graph}</math>는 [[무변 그래프]]([[완전 그래프]]의 [[여 그래프]]) 함자이다.

그래프의 범주에서, [[쌍대곱]]은 [[분리합집합]]이며, [[곱 (범주론)|곱]]은 텐서곱이다. ([[가군]]의 [[텐서곱]]과 다른 개념이다.)

그래프의 범주에서, [[시작 대상]]은 공 그래프 <math>\varnothing</math>이다 (<math>V(\varnothing)=E(\varnothing)=\varnothing</math>). 그래프의 범주에서, [[끝 대상]]은 하나의 꼭짓점만을 갖는 그래프 <math>K_1</math>이다.

[[데카르트 닫힌 범주]]로서, 두 그래프 <math>G,H</math> 사이의 [[지수 대상]] <math>H^G</math>은 다음과 같다.
:<math>V(H^G)=\hom_{\operatorname{Graph}}(G,H)</math>
:<math>\phi\chi\in E(H^G)\iff\forall u,v\in V(G)\colon u\sim v\implies\phi(u)\sim\chi(v)</math>
또한, 이 범주는 [[자연수 대상]] <math>\bar K(\mathbb N)</math>을 갖는다. 이는 자연수 집합에 대한 [[무변 그래프]]이다. 이 경우, 바로 다음 수 함수 <math>s\colon\bar K(\mathbb N)\to\bar K(\mathbb N)</math>은 <math>n</math>번째 꼭짓점을 <math>n+1</math>번째 꼭짓점으로 대응시키는 그래프 준동형이다.

=== 위상수학적 성질 ===
그래프는 [[CW 복합체]]이므로, [[하우스도르프 공간|하우스도르프]] [[파라콤팩트 공간]]이다.

그래프 <math>G</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>G</math>는 [[국소 콤팩트 공간]]이다.
* <math>G</math>는 국소 유한 그래프이다.
그래프 <math>G</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>G</math>는 [[콤팩트 공간]]이다.
* <math>G</math>는 유한 그래프이다.

그래프의 경우, [[CW 복합체]]이므로 [[세포 호몰로지]]를 정의할 수 있다. (이는 [[특이 호몰로지]]와 일치한다.) 그래프는 0-세포 및 1-세포만으로 구성되어 있으므로, 0차 및 1차 호몰로지 <math>H_0(G)</math>, <math>H_1(G)</math>만이 자명하지 않다. 0차 [[베티 수]]는 연결 성분의 수, 1차 [[베티 수]]는 [[선형독립]] [[순환 (그래프 이론)|순환]]의 수이다.

=== 논리학적 성질 ===
그래프의 [[1차 논리]] [[모형 이론]]은 상당히 약하다. 하나의 1차 논리 명제로 정의할 수 있는 성질들은 다음을 들 수 있다.
* [[완전 그래프]]의 모임 <math>\forall u\forall v\colon u\sim v</math>
* 임의의 자연수 <math>n</math>에 대하여, <math>n</math>-[[정규 그래프]]의 모임
* 임의의 하나의 유한 그래프 <math>G</math>만을 포함하는 집합 <math>\{G\}</math>
* 임의의 자연수 <math>n</math>에 대하여, <math>n</math>개의 꼭짓점을 갖는 그래프들의 집합
하나의 1차 논리 명제로 정의할 수 없는 성질들은 다음을 들 수 있다.
* 연결 그래프의 모임
* 유한 그래프의 집합
* 짝수 개의 꼭짓점을 갖는 유한 그래프의 집합
* [[이분 그래프]]의 모임

유한 그래프에 대하여, 기본 동치({{llang|en|elementary equivalence}})는 그래프의 동형과 같다.
:<math>G\cong H\iff\operatorname{Th}(G)=\operatorname{Th}(H)</math>
또한, 임의의 유한 그래프 <math>G</math>에 대하여,
:<math>H\models\phi_G\iff H\cong G</math>
인 1차 논리 명제 <math>\phi_G</math>가 존재한다.

무한 그래프의 경우, 기본 동치이지만 서로 동형이지 않는 두 그래프가 존재한다. 예를 들어, 꼭짓점 집합이 <math>\mathbb Z</math>이고, 변 집합이 <math>\{(n,(n+1))\colon n\in\mathbb Z\}</math>인 그래프 <math>C_\infty</math>를 생각해 보자. 이 경우, <math>C_\infty</math>와 <math>C_\infty\sqcup C_\infty</math>는 동형이 아니지만 기본 동치이다.<ref>{{웹 인용|url=https://mathoverflow.net/questions/37034/is-non-connectedness-of-graphs-first-order-axiomatizable/37049#37049|제목=Is non-connectedness of graphs first order axiomatizable?|웹사이트=Math Overflow|언어=en}}</ref>

==  예  ==
* '''[[공 그래프]]'''는 꼭짓점과 변이 둘 다 없는 그래프이다. 즉, <math>(V,E)=(\varnothing,\varnothing)</math>이다.
* '''[[한원소 그래프]]'''는 한 개의 꼭짓점을 가지고, 변이 없는 그래프이다. 즉, <math>V(G)=\{\bullet\}</math>, <math>E(G)=\varnothing</math>이다.
* '''[[무변 그래프]]'''는 변이 없는 그래프이다. 즉, <math>E(G)=\varnothing</math>이다.
* '''[[완전 그래프]]'''는 그래프에 속하는 모든 꼭짓점이, 다른 꼭짓점과 인접해 있는 그래프이다.
** 완전 그래프의 꼭짓점들은 모두 같은 개수의 꼭짓점과 연결되어 있기 때문에 완전 그래프는 [[정규 그래프]]이다. <math>n</math>개의 꼭짓점을 가진 완전 그래프는 <math>n(n-1)/2</math>개의 변을 가진다.
* '''[[완전 이분 그래프]]'''는 꼭짓점의 집합이 <math>V_1</math>과 <math>V_2</math>의 합집합이고, 모든 <math>V_1</math>의 꼭짓점이 <math>V_2</math>의 꼭짓점 각각과 변으로 연결되어 있는 경우이다.

== 관련 구조 ==
{{참고|그래프 이론 용어}}
'''[[유향 그래프]]'''는 각 변이 방향을 갖춘 그래프이다. 유향 그래프와 구별하기 위해, 그래프를 '''무향 그래프'''로 부르는 경우도 있다. 이는 각 변에 방향 구조를 갖춘 그래프로 볼 수 있다 (양향적인 변도 허용되어야 한다).

'''고리 그래프'''({{llang|en|loop graph}})는 양끝이 같은 꼭짓점인 변을 허용하는 그래프이며, 이러한 변을 '''고리'''({{llang|en|loop|루프}})라고 한다. 이는 각 꼭짓점에 <math>\{0,1\}</math>의 원소(고리의 유무 여부)를 추가한 그래프로 볼 수 있다.

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

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

=== 다중 그래프 ===
{{본문|다중 그래프}}
[[파일:Multi-pseudograph.svg|섬네일|right|다중 그래프의 예시. 회색의 원은 꼭짓점을, 푸른 선은 고리를, 붉은 선은 중복되는 변을, 검은 선은 중복되지 않는 변을 나타낸다.]]
같은 두 끝점을 가지는 여러 개의 변을 가질 수 있도록 허용한 그래프를 '''[[다중 그래프]]'''({{llang|en|multigraph}})라 한다. 같은 두 끝점을 가지는 변이 최대 하나인 그래프는 '''단순 그래프'''({{llang|en|simple graph}})라 한다. 다중 그래프는 [[함수]] <math>\partial</math>가 정의된 [[튜플]] <math>G=(V,E,\partial)</math>이며, 여기서 <math>\partial</math>는 아래와 같은 함수이다.
:<math>\partial \colon E\to S^2(V), S^2(V)=\{\{u,v\}\colon u,v\in V\}</math>

<math>\partial e=\{u,v\}</math>일 때 <math>u</math>와 <math>v</math>를 <math>e</math>의 끝점이라고 하며, 다중 그래프에서 양 끝점이 같은 변을 '''고리'''({{llang|en|loop}}) 또는 '''루프'''라고 한다.

=== 유향 그래프 ===
{{본문|유향 그래프}}
[[파일:Directed.svg|섬네일|upright|3개의 꼭짓점과 4개의 변을 가지는 그래프의 예시. 양쪽 화살표는 서로 반대 방향으로 가는 두 화살표를 의미한다.]]
변이 방향을 가지는 그래프를 '''유향 그래프'''{{llang|en|directed graph, digraph}}) 또는 '''방향 그래프'''라 한다. ''유향 단순 그래프'' <math>G</math>는 무향 단순 그래프처럼 순서쌍 <math>G=(V,E)</math>로 정의되며, 단 변 <math>e</math>가 두 꼭짓점의 집합이 아니라 순서쌍으로 정의된다. 즉 <math>E</math>는 아래와 같은 집합이다.
:<math>E\subseteq\{(u,v)|(u,v)\in V^2,u\neq v\}</math>
유향 그래프의 변은 화살표({{llang|en|arrow, arc}})라고도 부른다. 변 <math>e=(u,v)</math>을 <math>u</math>에서 <math>v</math>로 가는 변이라 표현하며, <math>u</math>를 변의 '''꼬리'''({{llang|en|tail}}), <math>v</math>를 변의 '''머리'''({{llang|en|head}})라 한다.

''유향 다중 그래프'' <math>G</math>는 함수 <math>\phi</math>가 정의된 튜플 <math>G=(V,E,\phi)</math>이며, 여기서 <math>\phi</math>는 아래와 같은 함수이다.
:<math>\phi \colon E\to \{(u,v)\colon (u,v)\in V^2, u\neq v\}</math>

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

== 같이 보기 ==
* [[매트로이드]]

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Graph}}
* {{eom|title=Graph isomorphism}}
* {{매스월드|id=Graph|title=Graph}}
* {{매스월드|id=Subgraph|title=Subgraph}}
* {{매스월드|id=Supergraph|title=Supergraph}}
* {{매스월드|id=ConnectedGraph|title=Connected graph}}
* {{웹 인용|url=http://ncatlab.org/nlab/show/graph|제목=Graph|웹사이트=nLab|언어=en}}
* {{웹 인용|url=http://ncatlab.org/nlab/show/category+of+simple+graphs|제목=Category of simple graphs|웹사이트=nLab|언어=en}}

[[분류:그래프 이론]]