그래프의 종류와 경로에 대해서 알아보자
그래프의 종류
그래프는 방향성, 연결 종류 등에 따라 여러종류로 나눌 수 있다.
무방향 그래프
-
그래프의 노드들 간에 이동 방향이 정해져 있지 않은 그래프
-
무방향 그래프의 차수 : 하나의 정점에 연결된 다른 정점의 수
G1에서 정점 0의 차수 : 2
방향 그래프
-
무방향 그래프와 달리 노드들 간에 이동 방향이 정해져 있다.
-
방향 그래프의 차수 : 진입차수, 진출차수로 나눌 수 있다.
- 진입차수 : 외부에서 해당 노드로 들어오는 간선의 수
- 진출차수 : 노드 내부에서 외부로 향하는 간선의 수
-
모든 진입차수나 진출차수의 합은 간선의 수와 같다.
3. 네트워크
-
간선 사이에 비용이나 가중치가 할당되어 있는 그래프.
-
가중치 그래프라고 부르기도 한다.
4. 부분 그래프
- 한 그래프의 정점과 간선집합의 부분집합으로 이루어진 그래프
그래프의 경로
당장 모르면 곤란할 용어 몇가지에 대해서 알아본다. 그래프의 경로에 대해서 더 궁금하다면 그래프 이론을 공부해보세요.
경로
- 한 정점에서 다른 정점으로 가는 간선 집합.
단순 경로
-
경로 중에서 반복되는 간선이 없는 경로
-
즉, 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로
사이클
- 단순 경로의 시작 정점과 종료정점이 동일한 경로
그래프의 연결정도
완전 그래프
- 모든 정점들 사이가 연결되어 있는 그래프.
