06-1 그래프의 구조

※ 그래프란?

 - 연결되어있는 원소간의 관계를 표현하는 자료구조.

 - 그래프는 연결할 객체를 나타내는 정점(vector)과 객체를 연결하는 간선(edge)의 집합으로 구성된다.

   그래프는 G = (V,E)로 정의하는데 V는 그래프에 있는 정점들의집합, E는 정점을 연결하는 간선들의 집합을 의미한다.

※ 그래프의 종류

1. 무방향 그래프 (방향이 없는 그래프, 간선을 (A,B) 로 표현 )
2. 방향 그래프 (방향을 가진 그래프, 간선을 <A,B>로 표현)
3. 완전 그래프 (한 정점에서 모든 정점과 연결 되어 있는 구조, 간선의 수는 방향 그래프 n(n-1) 무방향 그래프 n(n-1)/2 개를 갖는다.)
4. 부분 그래프 (원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프)
5. 가중 그래프 (정점을 연결하는 간선에 가중치를 할당한 그래프, 네트워크라고도 함)

무방향 그래프

완전그래프

완전 그래프

부분그래프

가중그래프

※ 그래프 관련 용어

 - 인접(adjacent) : 두 정점이 연결되어 간신이 있을때 두 정점은 인접되어 있다고 한다.

 - 부속(incident) : 인접한 두 정점사이에 간선을 두 정점에 부속되어 있다고 한다.

 - 차수(degree) : 정점에 부속되어 있는 간선의 수, 정점의 간선의 방향에 따라 차수는 진입차수와 진출차수로 나누어 진다.

 - 경로(path) : 간선을 따라갈 수 있는 길을 순서대로 나열한 것

 - 길이(path length) : 정점 A 에서 B 까지의 간선의 수

 - 단순 경로(simple path) : 어떤 경로에서 서로 다른 정점으로 구성된 경로

 - 사이클(cycle) : 단순 경로 중에서 경로의 시작과 마지막 정점이 같은 경로

 - 연결 그래프(connected graph) : 모든 정점들 사이가 연괼된 그래프

 - 단절 그래프(disconneccted graph) : 연결되지 않은 정점이 있는 그래프