18. 그래프의 표현방법과 여러 가지 그래프(9-2)

1. 그래프의 표현방법

그래프의 표현방법 

(1) 인접행렬(adjacency matrix) 

(2) 인접리스트  (adjacency  list) 

임의의 연결선  (u,  v)∈E에 대하여  u와  v를 서로 인접했다(adjacent)라고 하고, 정점  u와  v를 연

결선  e의  끝점(end  point)이라고  한다.  또  정점  u가  연결선  e의  끝점이면  e는  u에  접했다

(incident, 또는 부속)라고 한다. 

2) 인접리스트(adjacency  list) 

. 그래프의 한 정점에서 연결되어 있는 정점들을 하나의 연결리스트로 표현하는 방법 

. 인접행렬의 n행들의 값을  n개의 연결 리스트로 나타낸다. 

. 인접리스트 방식은 각 정점에 인접한 정점들을 순서와 상관 없이 일일이 열거하는 것이다. 

. 인접리스트로 나타낼 때 헤드(head)에서 출발한 각 정점은 적어도 두 개의 필드를 갖는다. 

. 필드의 구성 

. 시작 정점  : 헤드(head) 

. 첫 번째 필드  : 정점(vertex) 

. 두 번째 필드  : 링크(link)필드 

3) 정규 그래프

정의3

그래프  G의 모든 정점들이 같은 차수를 갖는다면  G를 정규그래프(regular  graph)라고 한다. 이

때 차수가  k값을 가지면  k-정규그래프라고 한다.

. 정규 그래프(regular graph) 

. 그래프 G 의 모든 정점들이 같은 차수를 갖는 경우 

.  K-정규 그래프(regular  graph) 

. 차수가  k인 정규그래프