정보처리기사 데이터베이스 요약 10

10장

 

1.     그래프

-      정점과 간선의 두 집합으로 이루어져 있음

-      Tree는 사이클이 없는 그래프

-      인접 행렬은 그래프의 방향 간선이 있으면 행렬의 Pij = 1 , 없으면 Pij = 0

-      그래프의 방향 간선이 없으면 ( 무방향 그래프 ) 인접했을 때 Pij = 1 , 인접하지 않았을 때 Pij = 0

 

2.     최대 간선 수

-      정점이 n개일 때 무방향 그래프 : n(n-1)/2

-      정점이 n개일 때 방향 그래프 : n(n-1)