[그래프] 1-2. 필수 기초 개념

1. 그래프 유형 및 분류

---

방향의 유무

간선에 방향이 없는 그래프 (Undirected Graph)	간선에 방향이 있는 그래프 (Directed Graph)
협업 관계 그래프 페이스북 친구 그래프	인용 그래프 트위터 팔로우 그래프

---

가중치의 유무

간선에 가중치가 없는 그래프 (Unweighted Graph)	간선에 가중치가 있는 그래프 (Weighted Graph)
웹 그래프 페이스북 친구 그래프	전화 그래프(횟수 등) 유사도 그래프

---

정점의 종류

동종 그래프 - 단일 종류의 정점 (Unpartite Graph)	이종 그래프 - 두 종류의 정점 (Bipartite Graph)
웹 그래프 페이스북 친구 그래프	전자 상거래 구매 내역 (사용자, 상품) 영화 출연 그래프 (배우, 영화)

---

 

2. 필수 기초 개념

그래프 (Graph)

• 집합과 간선으로 이루어진 수학적 구조
• 정점들의 집합 : V
• 간선들의 집합 :  E
• 그래프 :  G = (V, E)

 

정점의 이웃 (Neighbor)

• 해당 정점과 연결된 다른 정점을 의미
• 표기 : $N(v)$, $N_v$
• 예시 

$N(1) = {2, 5}$ $N(2) = {1, 3, 5}$ $N(3) = {2, 4}$ $N(4) = {3, 5, 6}$ $N(5) = {1, 2, 4}$ $N(6) = {4}$

 

방향의 구분

• 방향이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분
• 나가는 이웃 : 정점 v에서 간선이 나가는 경우, Out-Neighbor, Outgoing Neighbor, $N_{out}(v)$
• 들어오는 이웃 : 정점 v로 간선이 들어가는 경우, In-Neighbor, incoming Neighbor, $N_{in}(v)$
• 예시

$N_{in}(1) = {5}, N_{out}(1) = {2}$ $N_{in}(2) = {1, 3, 5}, N_{out}(2) = {5}$ $N_{in}(3) = {}, N_{out}(3) = {2, 4}$ $N_{in}(4) = {3}, N_{out}(4) = {5, 6}$ $N_{in}(5) = {2, 4}, N_{out}(5) = {1, 2}$ $N_{in}(6) = {4}, N_{out}(6) = {}$

 

 

---

edwith의 그래프와 추천시스템 강의를 듣고 정리 한 내용입니다. 

https://www.edwith.org/ai211/joinLectures/316864

그래프와 추천 시스템 강좌소개 : edwith