주 메뉴 열기
6개의 꼭짓점과 7개의 변을 갖는 그래프

수학에서, 더 구체적으로 그래프 이론에서, 그래프(영어: graph, 문화어: 그라프)는 일부 객체들의 쌍들이 서로 연관된 객체의 집합을 이루는 구조이다. 일련의 꼭짓점들과 그 사이를 잇는 변들로 구성된 조합론적 구조로 볼 수 있다.

그래프는 그래프 이론에 의해 연구되는 기초적 주제이다. "그래프"라는 용어는 1878년 J. J. 실베스터에 의해 처음 사용되었다.[1][2]

목차

용어편집

그래프 이론 용어 참고

  • 꼭지점(정점,점) :점은 선과 다르다, 점에는 1개 이상의 선이 연결된다, 따라서 꼭지점이 된다.
  • 변(간선,선분,선): 점과 점, 즉 두 점을 연결하는 선이다.
  • 인접한 점: 두 점의 연결이 두 점 외의 점을 포함하지 않고 하나 이상의 변을 포함하면 두 점을 서로에 대해 인접한 점이라한다.
  • 차수: 점에 연결된 선의 개수

정의편집

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

두 그래프   사이의 준동형(영어: homomorphism)  은 다음 성질을 만족시키는 함수  이다.

  • 임의의  에 대하여,  라면  

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

 

여기서 함자  

 
 

이다.

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

기본 정의편집

 (영어: edge 에지[*])   이지만  인 두 꼭짓점으로 이루어진 집합이며, 흔히  로 표기한다. 그래프  의 꼭짓점의 집합은  로, 변의 집합은  로 표기한다.

그래프  의 꼭짓점  차수(영어: degree)  기수

 

이다. 그래프  최대 차수  

 

이다.

두 그래프 사이의 전단사 준동형을 동형사상이라고 하며, 동형사상이 존재하는 두 그래프를 서로 동형이라고 한다. 만약  가 단사 준동형이라면,   부분 그래프라고 한다. 또한, 만약  에 대하여

 

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

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

성질편집

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

범주론적 성질편집

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

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

그래프의 범주  는 그래프를 그 꼭짓점 집합으로 대응시키는 망각 함자  를 갖는다. 이 함자는 극한과 쌍대극한을 보존시키며, 왼쪽·오른쪽 수반 함자를 갖는다.

 

여기서  완전 그래프 함자이며,  무변 그래프(완전 그래프여 그래프) 함자이다.

그래프의 범주에서, 쌍대곱은 그래프의 분리합집합  이며, 구체적으로 다음과 같다.

 
 

그래프의 범주에서, 텐서곱(영어: tensor product)  이라고 하며, 다음과 같다.

 
 

그래프의 범주에서, 시작 대상은 공 그래프  이다 ( ). 그래프의 범주에서, 끝 대상은 하나의 꼭짓점만을 갖는 그래프  이다.

데카르트 닫힌 범주로서, 두 그래프   사이의 지수 대상  은 다음과 같다.

 
 

또한, 이 범주는 자연수 대상  을 갖는다. 이는 자연수 집합에 대한 무변 그래프이다. 이 경우, 바로 다음 수 함수   번째 꼭짓점을  번째 꼭짓점으로 대응시키는 그래프 준동형이다.

위상수학적 성질편집

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

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

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

  •  콤팩트 공간이다.
  •  는 유한 그래프이다.

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

논리학적 성질편집

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

  • 완전 그래프의 모임  
  • 임의의 자연수  에 대하여,  -정규 그래프의 모임
  • 임의의 하나의 유한 그래프  만을 포함하는 집합  
  • 임의의 자연수  에 대하여,  개의 꼭짓점을 갖는 그래프들의 집합

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

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

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

 

또한, 임의의 유한 그래프  에 대하여,

 

인 1차 논리 명제  가 존재한다.

무한 그래프의 경우, 기본 동치이지만 서로 동형이지 않는 두 그래프가 존재한다. 예를 들어, 꼭짓점 집합이  이고, 변 집합이  인 그래프  를 생각해 보자. 이 경우,   는 동형이 아니지만 기본 동치이다.[3]

편집

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

관련 개념편집

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

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

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

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

응용편집

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

같이 보기편집

참고 문헌편집

  1. See:
  2. Gross, Jonathan L.; Yellen, Jay (2004). 《Handbook of graph theory》. CRC Press. 35쪽. ISBN 978-1-58488-090-5. 
  3. “Is non-connectedness of graphs first order axiomatizable?”. 《Math Overflow》 (영어). 

외부 링크편집