[그래프 이론] 용어 및 기본 개념 정리

기본 용어

그래프
점과 선으로 이루어진 도형 ($G(V,E)$)

그래프의 예시

 
꼭짓점
그래프에서의 점 (그래프에서 꼭짓점 집합: V)
 
변
꼭짓점을 연결한 선 (그래프에서 변 집합: E)
 
같은 그래프이다.
꼭짓점의 위치를 바꾸거나 변을 구부리거나 늘이거나 줄여도 두 그래프를 같은 그림으로 그릴 수 있다.
 
꼭짓점의 차수
그래프에서 한 꼭짓점에 연결된 변의 개수
그래프에서 모든 꼭짓점의 차수의 합 = 2*변의 개수
 
완전그래프
서로 다른 두 꼭짓점 사이에 항상 변이 오직 한 개 있는 그래프 ($K_{n}$)
 
연결그래프
임의의 서로 다른 두 꼭짓점이 연결된 그래프

경로
그래프의 한 꼭짓점에서 다른 꼭짓점으로 이동할 때, 한 번 지난 변을 반복하지 않으면서 연결된 변을 따라 순서대로 꼭짓점을 나열한 것
 
경로의 길이
한 꼭짓점에서 다른 꼭짓점으로 가는 경로에서 지나는 변의 개수
 
회로
한 꼭짓점에서 출발하여 출발한 꼭짓점으로 돌아오는 경로
 
인접행렬
어떤 그래프의 두 꼭짓점이 한 변으로 연결되어 있으면 1, 변으로 연결되어 있지 않으면 0으로 하여 그래프의 두 꼭짓점 사이의 관계를 나타낸 행렬
https://scian.tistory.com/175 

[그래프 이론] 인접행렬과 거듭제곱의 성질

---

여러 그래프

평면그래프
평면에서 변들이 꼭짓점에서만 교차하는 그래프
오일러공식: 연결된 평면그래프에서 $v-e+f=2$

• $e \leq 3v-6$ (단, $v \geq 3$)
• 차수가 5 이하인 꼭짓점이 적어도 하나 있음

 
오일러 경로
연결된 그래프의 모든 변을 지나며 한 번 지난 변을 다시 지나지 않는 경로
⇔ 홀수점의 개수 0개 혹은 2개, 시작점과 끝점이 홀수점
 
오일러 회로
회로인 오일러 경로
⇔ 홀수점을 가지지 않음
 
오일러 그래프
오일러 회로를 갖는 그래프
 
해밀턴 경로
연결된 그래프의 모든 꼭짓점을 한 번씩만 지나는 경로
 
해밀턴 회로
회로인 해밀턴 경로
n개의 꼭짓점을 갖고 있는 연결그래프에서 인접하지 않은 임의의 두 꼭짓점의 차수의 합이 n 이상일 경우, 해밀턴회로가 존재 (단, n≥3)
 
해밀턴 그래프
해밀턴 회로를 갖는 그래프

---

수형도

수형도
회로를 가지고 있지 않는 연결그래프
수형도이면, $e=v-1$ 만족 (항상 $f=1$)

G가 n개의 꼭짓점을 갖는 연결그래프일 때, 아래는 모두 동치.
G는 수형도이다.
⇔ 임의의 꼭짓점 u, v에 대하여 u에서 v로 가는 유일한 경로가 있다.
⇔ G에서 임의의 한 변을 제거하면 남은 그래프는 연결그래프가 아니다.
⇔ G는 n-1개의 변을 가지고 있다.

 
생성수형도
연결된 그래프에 회로가 포함된 경우 변을 일부 제거하여 수형도가 될 때, 그 수형도

• $G(V,E)$의 부분그래프 $G^{\prime}(V^{\prime},E^{\prime})$에 대해 $V=V^{\prime}$이고, $G^{\prime}$이 수형도이면 $G^{\prime}$은 $G$의 생성수형도이다.
• 연결그래프에는 항상 생성수형도가 있다.
• n개의 꼭짓점을 갖는 서로 다른 수형도의 개수는 $n^{n-2}$개