[자료구조] 그래프(Graph)의 개념 설명

1. 그래프

그래프(Graph)는 연결되어있는 원소간의 관계를 표현한 자료구조입니다.

그래프

· 그래프는 연결할 객체를 나타내는 정점(Vertext)과 객체를 연결하는 간선(Edge)의 집합으로 구성됩니다.

· 그래프 G를 G=(V, E)로 정의하는데, V는 정점의 집합, E는 간선들의 집합을 의미합니다.

2. 그래프 종류

① 무방향 그래프

무방향 그래프(Undirected Graph)는 두 정점을 연결하는 간선에 방향이 없는 그래프.

무방향 그래프 G1

· 무향방 그래프에서 정점 Vi와 Vj를 연결하는 간선을 (Vi, Vj)로 표현하는데, 이때 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 나타냅니다.

· V(G1)={A,B,C,D}, E(G1)={(A,B), (A,D), (B,C), (B,D), (C,D)}

 

② 방향 그래프

방향 그래프(Directed Graph)는 간선에 방향이 있는 그래프.

방향 그래프 G2

· 방향 그래프에서 정점 Vi와 Vj를 연결하는 간선을 <Vi, Vj>로 표현하는데 Vi를 꼬리(tail), Vj를 머리(head)라고 합니다. 이때 <Vi, Vj>와 <Vj, Vi>는 서로 다른 간선입니다.

· V(G1)={A,B,C,D} E(G1)={<A,B>, <A,D>, <B,C>, <B,D>, <C,D>}

 

③ 완전 그래프

완전 그래프(Complete Graph)는 한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프.

완전 그래프 G3와 G4

· 정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수는 n(n-1)/2이고 방향 그래프의 최대 간선 수는 n(n-1)입니다.

 

④ 부분 그래프

부분 그래프(Subgraph)는 기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프.

그래프 G5과 부분 그래프 G5'

 

⑤ 가중 그래프

가중 그래프(Weight Graph)는 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프.

가중치 그래프 G6과 G7

⑥ 유향 비순환 그래프(DAG, Directed Acyclic Graph)

방향 그래프에서 사이클이 없는 그래프.

유향 비순환 그래프 G8

 

⑦ 연결 그래프(Connected Graph)

떨어져 있는 정점이 없는 그래프.

연결 그래프 G9

 

⑧ 단절 그래프(Disconnected Graph)

연결되지 않은 정점이 있는 그래프.

단절 그래프 G10

3. 그래프 용어

그래프에서 두 정점 Vi와 Vj가 연결되어 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를 인접(adjacent)한다 하고, 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어 있다고 말합니다.

 

· 차수(Dgree): 정점에 부속되어 있는 간선의 수

 -진입차수(in-degree): 정점을 머리로 하는 간선의 수

 -진출차수(out-degree): 정점을 꼬리로 하는 간선의 수

 

· 경로(Path): 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트

 -단순 경로(Simple Path): 모두 다른 정점으로 구성된 경로

 

· 경로 길이(Path Length): 경로를 구성하는 간선의 수

 

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