그래프 정의
그래프는 다대다의 연결관계를 표현한다. 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조이다.
- 정점(Vertex): 그래프의 구성요소로 하나의 연결점
-인접 정점 : 두 개의 정점 간 간선이 존재하면 인접하다고 함 - 차선(Edge): 두 정점을 연결하는 선
- 차수(Degree): 정점 하나에 연결된 간선의 수
- V 개 정점을 갖는 그래프의 최대 간선의 수는 V * (V-1)/2 (무향 그래프- 양방향)
그래프 용어 (간선에 방향으로 화살표가 있는지 없는지 차이)
무향간성 (Undirected Edge)
- 정점을 연결하는 간선에 방향이 존재하지 않는다
- 임의의 간선(a, b)에 대해서 (a, b)=(b,a)이다
유향간선 (Directed Edge)
- 정점을 연결하는 간선에 방향이 존재한다
- 임의의 간선(a, b)에 대해서 (a, b)≠(b,a)이다
인접 (Adjacent)
- 정점 a,b에 대해서 간선 e=(a,b)가 존재한다.
<=> 정점 a와 b는 인접(Adjacent)한다.
(어딜 거치지 않고 바로 다이렉트길이 있기때문에 인접한다 라고함
인접은 정점 기준에서 얘기하는것)
부속(Incident)
- 정점 a,b에 대해서 간선 e=(a,b)가 존재한다
<=> 간선 e는 정점 a와 b에 부속(Incident)한다.
(간선의 관점에서 "나는 a와 b에 부속한다 거기에 속해있는 간선이다")
차수(Degree)
- 정점에 부속(incident)된 간선의 수
-in-degree: 유향 간선 그래프에서 정점에 들어오는 간선의 수
-out-degree: 유향 간선 그래프에서 정점에서 나가는 간선의 수
다중간선
- 정점 a,b에 대해서 간선 e1 = a2 = (a,b)가 존재한다
Self-loop
- 정점 a에 대해 간선 e=(a,a)가 존재한다
(루프백이라고 보면됨 출발지와 목적지가 동일한 정점으로 표현되있는것)
(문제에서는 이런식으로나옴 : 어떤경로를 통해서 첫번째지점에서 어떤 목적지 지점으로 이동을하는데 간선들을 순서대로 나열을 하는데 중복해서 지나갈수 없다라는 조건이 붙을때, 이런 변수들이 많이 나옴)
경로(Path)
-
정점과 간선이 교대로 구성된 시퀀스를 말함
(시퀀스란? 어떤 순서 개념이 좀 있는 그러한 나열된 것을 말함)
Path(A,B)=[A, e1, E] or [A, e2, C, e3, B] -
단순 경로(Simple path): 정점과 간선이 중복되지 않는 경로
Path(A, B) = [A, e1, B] or [A, e2, C, e3, B]
회로(Cycle)
- 시작 정점과 끝정점이 같은 경로를 뜻함
Cycle(A,A)=[A, e1, B, e3, C, e2, A]
(Path 이지만 Path에서 시작정점과 목적지정점이 같은경우)
connected
- 정점 A에서 정점 B로의 경로가 존재하면, A와 B는 연결되어 있다고 한다.
그래프의 종류
무향 그래프(Undirected Graph)
- 무향 간선으로 이루어진 그래프
유향 그래프(directed Graph)
- 유향 간선으로 이루어진 그래프
가중치 그래프(Weighted Graph)
- 가중치(or비용)를 갖는 간선으로 이루어진 그래프
(고속도로를 이용하면 톨게이트 비용? 정도)
a에서 c로가는 가장저렴한 코스트는 어떻게되는가 ?
정규 그래프(Regular Graph)
- 모든 정점이 동일한 차수를 가지는 그래프
완전 그래프(Complete Graph)
- 임의의 두 정점 A, B에 대해서 A, B를 잇는 간선 e(A, B)이 존재하는 그래프
- 완전 그래프는 정규 그래프
- N개의 정점을 가지는 무향그래프의 경우 :
간선의 개수 = 2/1N(N-1) [간선의개수는 2분의1 N(N-1)] - N개의 정점을 가지는 유향 그래프의 경우:
간선의 개수 = N(N-1)
연결 그래프(Connected Graph)
- 임의의 두 정점 A, B 에 대해서 경로 Path(A, B)가 존재하는 그래프
트리 그래프
- 순환을 갖지 않는 연결 그래프
- 임의의 두 정점에 대해서 경로가 정확히 1개 존재
