1. 그래프 정의
그래프 정의:
- 그래프는 수학에서 그래프 이론의 개념을 구현하는 추상 데이터 타입.
- 그래프 데이터 구조는 유한한 정점과 간선 집합으로 구성됨.
- 간선에는 심볼 레이블 또는 숫자 속성 같은 값을 연결할 수 있음.
그래프 구성 요소:
- 정점 (Vertex, V): 노드 또는 포인트라고도 함.
- 간선 (Edge, E): 두 정점을 연결. 아크 또는 선이라고도 함.
그래프 종류:
- 무방향 그래프: 간선에 방향이 없음.
- 방향 그래프: 모든 간선에 방향이 있음.
2. 그래프의 예제 및 응용
응용 예시:
- 통신 네트워크: 정점 = 도시, 간선 = 통신 링크
- 운전 거리/시간 지도: 정점 = 도시, 간선 가중치 = 운전 거리/시간
- 도로 지도: 일부 도로는 일방통행
완전 무방향 그래프:
- 모든 가능한 간선을 포함.
- n 개의 정점이 있는 그래프의 간선 수는 n(n-1)/2.
완전 방향 그래프:
- 모든 가능한 방향 간선을 포함.
- n 개의 정점이 있는 그래프의 간선 수는 n(n-1).
3. 정점의 차수
정점의 차수:
- 한 정점에 연결된 간선의 수.
- 예: degree(2) = 2, degree(5) = 3, degree(3) = 1
정점 차수의 합:
- 모든 정점의 차수 합 = 2e (e는 간선의 수)
정점의 진입 차수 및 진출 차수:
- 진입 차수 (In-Degree): 들어오는 간선의 수
- 진출 차수 (Out-Degree): 나가는 간선의 수
4. 그래프 문제와 연산
그래프 문제 유형:
- 경로 문제
- 연결성 문제
- 스패닝 트리 문제
경로 찾기:
- 예: 정점 1과 8 사이의 경로 찾기
연결 그래프:
- 모든 정점 쌍 사이에 경로가 있는 무방향 그래프
연결 컴포넌트:
- 최대 연결된 서브그래프
- 연결 그래프는 정확히 1개의 컴포넌트를 가짐
5. 스패닝 트리 (Spanning Tree)
트리:
- 사이클이 없는 연결된 그래프.
- n 개의 정점을 가진 연결 그래프는 n-1 개의 간선을 가짐.
스패닝 트리:
- 원래 그래프의 모든 정점을 포함하는 서브그래프.
- n 개의 정점을 가지며 n-1 개의 간선을 가짐.
최소 비용 스패닝 트리:
- 간선 가중치의 합이 최소인 스패닝 트리
6. 그래프 표현
인접 행렬 (Adjacency Matrix):
- 0/1 n x n 행렬로, n = 정점의 수
- A(i,j) = 1 이면 (i,j) 간선이 존재
- 무방향 그래프의 경우 대칭 행렬
인접 리스트 (Adjacency List):
- 각 정점 i에 대해 인접한 정점들의 리스트
- n 개의 인접 리스트 배열로 구성
가중 그래프 (Weighted Graph):
- 비용 인접 행렬
- C(i,j) = (i,j) 간선의 비용
- 인접 리스트는 각 리스트 요소가 (인접 정점, 간선 가중치) 쌍
Comments 0