14-1. 그래프

방향 그래프 - 사이클을 포함한 경로주요용어

그래프 : 정점 집합 V와 간선 집합 E에 대하여 그래프는 G=(V,E)
정점 : 그래프를 구성하는 대상
간선 : 그래프에 있는 대상들의 관계

방향 그래프 : 간선의 방향이 유의미한 그래프
무방향 그래프 : 간선의 방향이 무의미한 그래프
다중 그래프 : 두 정점쌍이 간선을 여러 개 가질 수 있는 그래프
가중 그래프 : 간선이 중요도/비용 등을 나타내는 가중 값을 갖는 그래프

경로 : 두 정점을 잇는 간선 열
루프 : 한 정점에서 출발하여 자신으로 연결하는 간선

사이클 : 시작점과 끝점이 같은 경로
사이클이 있는 그래프 : 하나 이상의 사이클을 갖는 그래프
무 사이클 그래프 : 사이클이 없는 그래프, 트리
인접 : 두 정점이 간선으로 연결되었을 때 두 정정은 인접함
인접 행렬 : 그래프의 표현방법의 하나로 정점 사이의 인접성을 행렬로 나타낸 것
인접 리스트 : 그래프의 표현방법의 하나로 정점 사이의 인접성을 연결 리스트로 나타낸 것

 

 

01. 개념 및 용어

그래프

: "관계"를 그래프로 추상화하여 다룰 수 있음

-> 전기회로의 분석, 최단 거리 탐색, 프로젝트 계획, 스케줄링, 운송, 컴퓨터 네트워크 등등

 

그래프의 정의 

- 그래프 G는 하나 이상의 정점(혹은 노드)을 포함하는 집합 V 와 두 정점의 쌍으로 구성되는 간선을 포함하는 집합 E 의 순서쌍으로 정의함

- 그래프 G = (V, E)

 

V (정점의 집합) = { a, b, c, d}

E (간선의 집합) = {1, 2, 3, 4, 5, 6, 7} 

G = ( V, E ) = ( { a, b, c, d}, {1, 2, 3, 4, 5, 6, 7 } )

그래프의 용어 정의

- 간선은 두 정점을 연결하는 선

- 그래프는 연결(간선)에 방향성이 없는 무방향 그래프와 방향성을 갖는 방향 그래프가 있음

- 무방향 그래프는 간선이 방향성이 없음

- 방향 그래프는 간선이 방향성이 있음

- 무방향 그래프의 간선은 실선으로 나타내고 방향 그래프의 간선은 화살표로 나타냄

 

- 간선은 두 정점 쌍으로 나타냄

- 무방향 그래프일 때는 정점 쌍이 순서를 나타낼 필요가 없으므로 어떤 간선이 두 정점 v₁, v₂를 잇는 것이라면 {v₁, v₂}로 나타냄

- 방향 그래프의 간선은 순서쌍 (v₁, v₂)로 표시함

 

그래프의 연결 ­ 방향,무방향,혼합 그래프

 

다중 그래프 : 두 정점을 잇는 간선이 여러 개인 그래프

방향 다중 그래프 : 방향성을 갖는 간선으로 이루어진 다중 그래프

가중 그래프 : 간선이 가중치를 갖는 그래프

그래프의 성질

- n 개의 정점을 갖는 무방향 그래프에서  v_i ≠ v_j 인 서로 다른 무순서쌍 { v_i ,v_j } 의 최대 개수

 

_nC₂ = n ( n-1) / 2

 

- n 개의 정점을 갖는 방향 그래프에서  v_i ≠ v_j 인 서로 다른 무순서쌍 { v_i, v_j } 의 최대 개수

 

_nP₂ = n ( n-1 )

 

- 완전 그래프(Completegraph) :모든 정점들이 간선으로 서로 연결된 그래프

- 완전 그래프인 (만일 정점의 수를 n이라고 하면) 무방향 그래프의 간선 개수

 

n ( n-1) / 2

 

 

- 두 정점 v_i와 v_j가 서로 인접한다 :무방향 그래프 간선 e ∈E가 {v_i ,v_j}으로 표현될 때, 즉,두 정점 v_i 와 v_j 를 연결하는 간선이 존재하는 경우를 말함 

- 독립 정점 : 다른 어떤 정점과도 인접하지 않은 정점

- 널(null)그래프 : 독립 정점만으로 구성한 그래프이며,간선의 집합 E 는 공집합임

   -> 정점만 있는 그래프 (간선이 존재하지 않는 그래프)

 

- 경로(path) : 임의의 두 정점을 연결하는 어떤 간선의 끝 정점(해당 간선의 머리)이 이어진 간선의 시작 정점(해당 간선의 꼬리)이 되는 간선의 열

 

- 무방향 그래프 G 에 대해 E(G)에 속하는 순서없는 간선 {v_p, v₁}, {v₁, v₂},…, { v_n-1, v_n}, {v_n, v_q}가 있을 때,그래프 G 의 정점 v_p에서 v_q까지 경로는 정점 v_p, v₁, v₂, … , v_n, v_q들의 연속을 말함

 

- 경로 길이 : 경로에 있는 간선의 수

- 단순 경로 : 경로 상에 있는 모든 정점이 서로 다른 경로

- 기본 경로 : 경로 상에 있는 모든 간선이 서로 다른 경로

 

 

방향 그래프 - 사이클을 포함한 경로

- 사이클 : 출발점과 도착점이 동일한 단순 경로

- 사이클 그래프 : 사이클이 있는 그래프

 

 

그래프 이론에서 사용하는 용어 정리

- 방향 그래프에서 진입 차수 : 주어진 정점으로 향한 간선의 개수

- 진출 차수 : 주어진 정점에서 시작하는 간선의 개수

- 정점의 차수 : 진출 차수와 진입 차수의 합

- 무방향 그래프에서 차수 : 정점에 연결된 간선들의 개수

- 루프 : 간선의 시작점과 끝점이 같은 정점인 길이가 1인 경로

- 무사이클 그래프 : 사이클이 없는 그래프를 ‘무사이클 그래프’ 혹은 ‘트리’ 라고 함 (방향이 있는 무사이클 그래프를 DAG(directed acyclicgraph)라고 부름)