그래프

1. 복잡한 작업 과정이나 구조를 시각적으로 표현하여 이해하기 쉽고 가시적으로 설명할 때 유용한 자료구조

2. 주어진 몇 개의 정점과 그 정점을 끝점으로 하는 선들로 이루어진 도형

3. 선형 자료구조로 표현하기 어려운 다대다 관계를 표현 가능

4. 서로 연결되어 있는 객체들 간의 관계를 표현할 수 있는 비선형 자료구조

 

<그래프 용어>

무방향 그래프

  1. 두 정점을 연결하는 간선의 방향이 없는 그래프

  2. 정점 v₁에서 정점 v₂로 연결되는 간선은 (v₁,v₂)와 같이 표현

방향 그래프

  1. 간선이 방향을 가지고 있는 그래프

  2. 정점 v₁에서 정점 v₂로 연결되는 간선은 <v₁, v₂>와 같이 표현

  3. 방향 그래프에서 간선 <v₁,v₂>와 <v₂,v₁>은 서로 다른 간선

인접

  1. 두 정점 v_i와 v_j를 연결하는 간선 (v_i, v_j)가 있을 때 두 정점 v_i와 v_j를 서로 인접하다고 함

  2. 간선 (v_i, v_j)는 정점 v_i과 v_j에 부속되어 있다고 표현

차수

  1. 정점에 연결되어 있는 간선의 수

  2. 하나의 정점에 연결된 다른 간선의 수

경로와 사이클

  1. 경로는 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것

  2. 사이클은 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로

연결 그래프

  그래프를 구성하는 모든 정점 사이에 경로가 있는 그래프

부분 그래프

  어떤 그래프 G가 있을 때 그래프에 포함되는 일부 정점과 간선으로만 그린 그래프

평면 그래프

  그래프의 간선들이 정점 이외에서는 서로 교차되는 일이 없도록 평면으로 그릴 수 있을 경우

완전 그래프 

  모든 정점들의 쌍 사이에 간선이 존재하는 그래프

동형 그래프 

  두 그래프가 모양은 다르지만 똑같은 정점과 똑같은 간선으로 구성되어 있는 그래프

가중 그래프

  정점을 연결하는 간선에 비용이나 거리 등의 가중치가 할당된 그래프

 

<그래프의 표현 방법>

1. 인접 행렬

  -그래프의 구조를 표현하기 위해서 정점들 사이의 인접 관계를 정점 수만큼의 행과 열을 갖는 행렬을 이용하여 표현하는 방법

  -두 정점을 연결하는 간선이 존재하면 행렬의 원소를 1로 표현하고 존재하지 않으면 0으로 표현

 

2. 인접 리스트 

  -그래프를 구성하는 각각의 정점에 대해 간선으로 연결되어 있는 정점들을 연결 리스트로 표현하는 방법

 

<그래프 순회>

1. 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산

2. 깊이 우선 탐색과 너비 우선 탐색이 있음

      1 깊이 우선 탐색

• 어떤 시작 정점에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하는 방법
• 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행
• 스택 사용  

       2 너비 우선 탐색

• 시작 정점에 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법
• 시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서 방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
• 큐 사용

<신장 트리>

1. 그래프 내의 모든 정점을 포함하는 트리

2. 모든 정점들이 연결되어 있어야 하고 트리의 성질을 만족해야 하므로 사이클을 포함하면 안 됨

 

<최소 비용 신장 트리>

1. 각 간선에 가중치가 부여된 그래프에서 가중치의 총합이 가장 적은 신장 트리

2. 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

3. Prim의 방법과 Kruskal의 방법이 있음

1. Prim의 방법

• 가중 그래프에서 가중치가 가장 작은 간선을 하나 선택하여 시작하고 선택된 간선에 연결된 모든 간선들 중 가중치가 가장 작은 간선을 선택해가며 최소 비용 신장 트리를 구성해 나가는 방식

2. Kruskal의 방법

• 사이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소 신장 트리를 만드는 방식
• 가중치를 기준으로 간선을 정렬한 후 최소 신장 트리가 될 때까지 하나씩 선택해 가는 방법

<PERT>

1. 주어진 프로젝트가 얼마나 완성되었는지 분석하고 검토하는 기법 

2. 프로젝트 진행 상황을 통계적인 방법으로 파악하고 각각의 작업에 필요한 시간을 계산하여 모든 프로젝트를 끝내는 최소 시간을 파악하는 데 활용

3. 경험이 없는 사업이나 소요 시간이 불확실한 사업에 적용 가능

<CRM>

1. 건설 공사와 같이 단위 작업이 확정적 소요 시간을 갖는 프로젝트인 경우에 적합

2. 최소의 비용 추가 투입을 고려하여 전체 프로젝트의 시간 단축을 목표로 함

3. 목표 기일 단축과 비용 최소화를 위해 과거 실적이나 경험 등의 확정적 결과값을 이용하여 활동 중심의 확정적 모델을 전개

4. 수행 시간을 하나의 값으로 예측하며 반복 사업이나 소요 시간이 확실한 사업 등 확정적인 경우에 이용

5. 현재는 PERT와 CRM을 통합하여 사용하며 PERT/CPM 기법이라 부름

<최단 경로>

1. 다양한 경로들 중에 가장 효과적이고 빠른 경로를 찾는 문제

2. 가중 그래프에서 출발점에서부터 도착점까지의 최단 경로를 찾는 문제

3. 도로망이나 네트워크 경로 등을 선택하는 데 응용

4. 다익스트라 알고리즘이 있음