그래프 알고리즘_기본 용어정리

그래프 알고리즘

 

그래프는 정점과 간섭의 집합이다.

정점 :  일반적으로 이름을 가지는 원으로 표시 ( 0 ,1 ,2, 3...)

간섭 : 두 정점간을 연결하는 선으로 표현 (0과1을 이어주는 선,1과 4를 이어주는 선...)

정점의 위치는 의미가 없고, 정점간의 연결 상태만이 중요하다.

경로 : 정점x로부터 정점y에 이르는 간선으로 연결된 정점들의 순서 집합이다.

단순경로 : 처음 정점 외에 중복된 정점이 없는 경우를 의미( 그래프 G1에서 정점 A에서 정점 C까지의 경로 중 (A-B-C)는 단순 경로이고 A-B-D-A-B-C는 단순 경로가 아니다)

회로(cycle) :  첫 정점과 끝 정점이 같은 경우 (G1에서 A-B-C-D-A)

위키 백과 : 신장 부분 나무 그래프

신장 나무 : 어떤 그래프의 부분 그래프로서 정점의 집합V는 원래의 그래프와 같은 나무 구조를 말한다. 즉 회로(cycle)가 없는 그래프

나무구조는 정점이 v개일 경우 간선은 v-1개 정점개수가 v라면 트리구조일 수 가 없다 => 회로가 존재

위키 백과 : 무방향

무향 그래프 : 간선의 방향성이 없는 그래프

위키 백과 : 방향 그래프

방향 그래프 : 간선의 방향성이 있는 그래프

위키 백과 : 가중/네트워크

가중 그래프 : 간선의 방향성과 가중치까지 표현한 그래프

네트워크 : 가중 그래프이면서 방향 그래프 인것

정점에 이어진 간선의 수로 차수를 결정한다. 무향 그래프일 경우 단순하게 차수라 할 수 있지만 방향이 있는 방향 그래프인 경우는 나가는 선과 들어오는 선을 구분 할 필요가 있다.

외차수 : 정점으로 부터 나가는 간선의 수 ( 정점 V1에 e2,e3)

내차수 : 정점으로 들어오는 간선의 수 (정점 V1에 e1,e5)

학습 참고

1) c로배우는 알고리즘 

2) https://ko.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

3) https://m.blog.naver.com/PostView.nhn?blogId=k97b1114&logNo=140163248655&proxyReferer=https%3A%2F%2Fwww.google.com%2F