20. 그래프(10-2)

1. 그래프의 개념 

 산술식의 내부 표현(polish notation) 

 그래프의 정의 

 정점(vertex)이라고 불리는 원소들의 집합 V와 간선(edges)이라 불리는 V의 원소들의 비순서화된 쌍들의 집합 E로 구성 

 V는 공집합이 아닌 정점들의 유한집합   

 E는 간선, 즉 연결선의 집합 

 V(G)는 그래프의 정점의 집합 

 E(G)는 그래프의 간선의 집합 

 케인즈버그(Koenigsberg)의 다리 

*이산수학 그래프파트에서 수학적으로 자세히 다룹니다.

 그래프의 예 <그림 6-2> 

 그래프의 예 설명 

V(G1) = 1, 2, 3, 4 

E(G1) = (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) 

V(G2) = 1, 2, 3, 4, 5, 6, 7 

E(G2) = (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7) 

V(G3) = 1, 2, 3 

E(G3) = <1, 2>, <2, 1>, <2,3> 

V(G4) = 1, 2, 3, 4 

E(G4) = (1, 2), (1, 3), (2, 4), (3, 4), <2,3> 

 그래프의 용어 

 인접(adjacent)과 부속(incident) 

 무방향 그래프에서 간선(V1, V2)가 E(G)에 존재한다면 V1 과 V2는 인접(adjacent) 한가고 하며, 이 때 간선 (V1, V2)는 정점 V1 과 V2에 부속(incident) 된다고 한다. 

 방향성 그래프에서는 연결된 간선의 방향에 따라 인접 개념이 달라진다. 

즉, <V1, V2>가 하나의 연결 간선이라면 정점 V1은 정점 V2에 인접하다라고 하며, 정점 V2는 정점 V1로부터 인접 되었다고 한다. 

 차수(degree) 

 그래프의 어떤 특정한 정점에 연결된 간선의 수 

 정점의 진출 차수(out degree) 

해당 정점에서 나가는 간선의 수 

 정점의 진입 차수(in degree) 

해당 정점으로 들어오는 간선의 수 

 데이터 처리 과정 

 무방향 그래프에서는 진출차수와 진입 차수의 개념은 적용될 수 없으므로 각 정점의 차수는 정점과 직접적으로 연결된 간선들의 수가 된다.  

 무방향 그래프 

 경로(path) 와 사이클(cycle) 

 경로 

그래프에서 임의의 정점 Vi에서 Vi에 이르는 연결선 

 사이클 

방향성 그래프에서 처음 정점과 마지막 정점이 같은 다순경로 

 경로의 길이(length)   

경로를 구성하는 간선의 수 

 단순 경로(simple path)   

한 경로상에 있는 모든 정점들이 서로 다른 경로 

 연결 요소(connected components) 

 무방향 그래프의 경우 최대 연결 서브 그래프(maximum connected subgraph)를 의미 

 즉, 그래프를 운행했을 때 방문된 정점과 그것에 부속된 간선들로 구성 

 N개의 정점과 e개의 간선을 갖는 그래프 G에서 임의의 정점 i의 차수를 d라 하면 그래프의

간선(edge)의 수 e는 

2. 그래프의 종류 

 무방향 그래프 (undirected graph 또는 graph) 

 G1, G2에서 처럼 두 정점간에 연결된 간선들이 방향이 없는 지정되지 않은 그래프

 방향 그래프(directed graph 또는 digraph) 

 각 정점들간의 연결선인 간선들이 방향이 표시된 쌍으로 나타낸 그래프 

 다중 그래프(multi graph 또는 multiple graph) 

 다중 그래프는 같은 정점들을 연결한 간선이 여러 개 존재하는 그래프 

 순환(loop)를 허용 

 다중 그래프 

 단순 그래프(single graph 또는 tree graph) 

 정점을 연결한 간선들은 순환이 없고 연결한 간선이 한 개만 존재하는 그래프 

 서브그래프(subgraph) 

 그래프 G = {V, E}가 있을 때, 어떤 그래프 G’ = {V’, E’} 이고 

이 두 개의 그래프 G, G’의 관계에서 V(G’)⊆V(G) 이고 E(G’)⊆E(G)인 조건을 만족하는 그래프 G’ 

 서브 그래프 

 서브그래프(subgraph) 

 서브 그래프의 예 

 정규 그래프(regular graph) 

 그래프의 모든 정점이 같은 차수(degree)를 가진 그래프 

 모든 정점이 차수가 k이면, 그 그래프를 k 차 정규 그래프 (k-th regualr graph) 

 연결그래프(connected graph)와 단절그래프(disconnected graph) 

 그래프에서 모든 정점들에 대하여 서로 다른 두 개의 정점에 이르는 경로가 존재하면 그 그래프는 연결그래프라 하고, 그렇지 않으면 그 그래프를 단절 그래프 

 연결 그래프와 단절 그래프 

 강력 연결 그래프(strongly connected graph) 

 방향성 그래프에서 임의의 두 정점 V1과 V2에 <V1, V2> 그리고 <V2, V1>로 양방향 직접 경로가 존재할 경우 그래프 

 약 연결 그래프(weakly connected graph) 

 방향성 그래프에서 임의의 두 정점 V1과 V2에 <V1, V2> 그리고 <V2, V1>로 단방향 직접 경로가 존재할 경우 그래프