페미위키:포크 프로젝트/리브레 위키/그래프 (그래프 이론)

This page was last edited on 14 November 2021, at 11:48.
< 페미위키:포크 프로젝트‎ | 리브레 위키

1 정의

파일:Defgraph.png
다중 변과 고리를 가진 그래프

그래프(graph)는 꼭짓점과 변으로 이루어져 있다.

자세히 말해, 순서쌍 가 다음 두 조건

  1. 공집합이 아닌 유한집합이다. (이 조건은 논의의 편의를 위해 존재하며, 꼭짓점이 무한한 그래프를 다루기도 한다.)
  2. 는 '끝점'이 정의되는 변들의 모임이다. 즉, 에는 함수 가 있어 를 만족한다.

을 만족하면 그래프라고 한다.

이때 의 원소를 꼭짓점(vertex), 의 원소를 (edge)이라고 한다. 인 두 변은 다중 변(multiple edges) 또는 평행 변(parallel edges)라고 하며, 또 인 변을 고리(loop)라고 한다. 평행 변과 고리가 없는 그래프를 단순그래프(simple graph)라고 한다. 책에 따라, 단순그래프를 그래프라고 부르고, 평행 변과 고리를 허용하는 그래프를 다중그래프(multigraph)라고 하기도 한다.

2 그래프 알고리즘

3 그래프 색칠하기

4 그래프의 종류