- 그래프 이론
- 그래프 알고리즘 분류
- 그래프 이론 분류
- Graph thoery (그래프 이론) [강의노트]
- 그래프 용어사전
- [PPT] 제 5강 그래프 알고리즘
- 6장 그래프 알고리즘 - SlideShare
그래프(Graph)는 연결되어있는 원소간의 관계를 표현하는 자료구조이다.
버스 노선도나 전철 노선도를 보면 여러 지역이프프 연결되어 있는지를 알 수 있다.
나와 연관된 인간관계를 나타내느 인맥지도, 수도 배관에 대한 배수 시스템,
물질 분자구조 등은 연결구조가 너무 다양하기 때문에 선형 자료구조나 트리로는 표현할 수가 없다.
이러한 자료를 표현하기 위한 자료구조가 그래프이다.
그래프는 모든 연결 구조를 표현할 수 있기 때문에 여러 분야에서 폭 넓게 이용되고 있다.
그래프는 연결할 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합으로 구성된다.
그래프 G를 G=(V, E)로 정의하는데, V는 그래프에 있는 정점들의 집합을 의미하고 E는 정점을
연결한는 간선들의 집합을 의미한다.
그래프는 방향, 무방향, 완전, 부분, 가중 그래프등이 있다.
- 무방향 그래프
두 접점을 연결하는 간선에 영향이 없는 그래프
정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현
=> (Vi, Vj) = (Vj, Vi) - 방향 그래프
다이그래프 ( digraph )라고도 하는데, 간선에 방향이 있는 그래프
방향 그래프에서 정점 Vi에서 정점 Vj를 연결하는 간선, 즉 Vi→Vj를 <Vi, Vj>로 표현하고 화살표로 타나낸다.
그리고 Vi를 꼬리(Tail) Vj를 머리(head)라고 한다.
=> <Vi, Vj> ≠ <Vj, Vi> - 완전 그래프
완전 그래프 ( Complete Graph )는 한 정점에서 다른 모든 정점과 연결되어 최대의 간선 수를 가진 그래프 이다.
정점 n개인 무방향 그래프의 최대 간선 수는 n(n-1)/2개이며, 방향 그래프의 경우에는 두 정점에 대하여 방향이 다른 2개의 간선을 연결할 수 있으므로 무방향 그래프에서의 최대 간선 수의 2배가 되어 n(n-1_개가 된다.
- 부분 그래프
원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프 ( subgraph )라고 한다. - 가중 그래프
정점을 연결하는 간선에 가중치 ( weight )를 할당한 그래프를 가중 그래프 ( weight graph )또는 네트워크 ( network )라고 한다.
반응형