그래프

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

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

정의[편집]

그래프 는 집합 위의 반사 대칭관계 순서쌍이다. 그래프 꼭짓점(-點, 영어: 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차 논리 명제 가 존재한다.

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

[편집]

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

관련 개념[편집]

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

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

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

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

응용[편집]

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

참고 문헌[편집]

바깥 고리[편집]

같이 보기[편집]