그래프 (그래프 이론)

정의

다중 모서리와 고리를 가진 그래프

그래프(Graph)는 꼭짓점과 모서리로만 이루어진 도형이다.

자세히 말해, 순서쌍 [math]\displaystyle{ G=(V,E) }[/math]가 다음 두 조건

1. V는 공집합이 아닌 유한집합이다. (이 조건은 논의의 편의를 위해 존재하며, 꼭짓점이 무한한 그래프를 다루기도 한다.)
2. E는 [math]\displaystyle{ \{u,v\}\;(u,v\in V) }[/math]들의 모임인 유한집합이다.

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

이때 V의 원소를 꼭짓점(vertex), E의 원소를 변(edge)이라고 한다.

E는 집합이기는 하지만 같은 {u,v}가 여럿 있는 것도 허용하며, 이러한 모서리를 다중 변(multiple edges) 또는 평행 변(parallel edges)이라고 한다. 또, u=v인 경우는 고리(loop)라고 한다.

그래프의 종류

• 완전그래프
• 별그래프
• 순환그래프
• 바퀴그래프
• 사다리그래프
• 이분그래프
  • 완전이분그래프
• 평면그래프
• 나무 (그래프 이론)
• 정규그래프