그래프

라뷰 추상화

공통된 개념을 뽑아서 압축한 형태로 보자

 

---

그래프

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

• 전기회로 분석
• 최단 거리 탐색
• 프로젝트 계획
• 스케줄링
• 운송
• 컴퓨터 네트워크 시뮬레이션 등

 

그래프 정의

G = [V,E]

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

• 무방향 그래프(실선, 정점 쌍,순서 상관 없음) / 방향 그래프(화살, 순서쌍, 순서 중요) / 혼합 그래프(무방향+방향)

{v1,v2} = {v2, v1}
(v1, v2) ≠ (v2, v1)

방향 그래프

G(b) = (V,E), V ={v1,v2}, E ={(v1,v2)}

 

G(e) = (V,E), V = {v1,v2,v3,v4}, E{(v1,v2),(v2,v4),(v2,v3),(v4,v3),(v3,v1)}

무방향 그래프

G(f) = (V,E), V ={v1,v2,v3,v4,v5}, E ={ {v1,v2} , {v1,v3} , {v2,v3} , {v3,v4} }

혼합 그래프

G(d) = (V,E), V ={v1,v2,v3,v4}, E ={ (v2,v1) , (v2,v3)  , {v2,v4} , {v1,v3} , (v4,v3) }

---

그래프의 성질

• 정점 n개 무방향 그래프 최대 정점 쌍 수: n(n-1)/2
• 정점 n개 방향 그래프 최대 순서 쌍 수 : n(n-1)
• 완전 그래프인 무방향 그래프의 간선 수:  n(n-1)/2
• 두 정점 v(i)와 v(j)가 서로 인접한다.
• 독립 정점 : 다른 어떤 정점과도 인접하지 않은 정점
• 널 그래프 : 독립 정점만으로 구성한 그래프, 간선의 집합 E는 공집합
• 경로 : 임의의 두 정점을 연결하는 어떤 간선의 끝 정점에서 그 간선의 시작 정점으로 이어지는 간선의 연속(열)

순서 있는 간선들
(vp,v1),(v1,v2),.........,(v(n-1),v(n)),(v(n),vq)
특별한 언급이 없는 경우
vp,v1,,,....,vn,vq와 같은 경로상의 간선을 구성하는 정점 순서열로 표시

• 경로 길이 : 경로에 있는 간선의 수
• 단순 경로 : 경로 상에 있는 모든 정점이 서로 다른 경로 (같은 곳 또 방문하면 안됨)
• 기본 경로 : 경로 상에 있는 모든 간선이 서로 다른 경로 (한 붓 그리기)
• 사이클 : 출발점과 도착점이 동일한 "단순 경로"
• 사이클 그래프 : 사이클이 있는 그래프
• 방향 그래프
  • 진입 차수 : 주어진 정점으로 향한 간선의 개수
  • 진출 차수 : 주어진 정점에서 시작하는 간선의 개수
  • 정점의 차수 : 진출 차수와 진입 차수의 합
• 무방향 그래프
  • 차수 : 정점에 연결된 간선들의 개수
• 루프 : 간선의 시작점과 끝점이 같은 정점인 길이가 "1"인 경로( 즉 자기에서 출발해서 자기로 바로 도착)
• 무사이클 그래프 : 사이클이 없는 그래프, "트리"라고 도 부름.
• 방향이 있는 무사이클 그래프를 DAG라고 부름

---

깊이 우선 탐색

무방향 그래프

• 스택을 사용하여 가장 최근에 선택의 지점에 있던 정점을 찾아냄
• 출발점 v를 방문
• v에 인접하고 아직 방문하지 않은 정점 w를 선택
• w를 출발점으로 다시 깊이 우선 탐색(인접하고 아직 방문하지 않은 정점을 선택)
  • 만약 인접한 모든 정점들이 이미 방문한 정점인 경우는 가장 최근에 방문했던 정점 중에서, 방문하지 않은 w 정점을 가진 정점을 선택하여 정점 w로부터 깊이 우선 탐색을 시작
• 모든 정점을 한 번씩 방문할 때까지 반복

방향 그래프

인접한 정점 중에 가지 못한 정점만 스택에 보관 한다.

막다른 골목에 오면 그떄 스택을 사용하기 위해서 스택에 보관.

너비우선탐색

• 큐를 많이 사용 함.
• 출발점 v를 방문
• v에 인접한 정점 w를 모두 방문한 후, 다시 w에 인접한 방문하지 않은 정점들을 차례로 방문함
• 두 과정을 모든 정점을 한 번씩 방문할 때까지 반복

---

최소비용신장트리

사이클이 없는 것이 신장트리

그 신장 트리 중 가중치가 가장 적은게 최소비용신장트리

 

---

참조사이트:
https://news.seoul.go.kr/traffic/archives/1551

서울지하철 현황 및 이용안내

https://cis.seoul.go.kr/TotalAlimi_new/SearchMap.action?cmd=searchmap#list

지도검색서비스:지도검색서비스:서울특별시 건설알림이