Day_01_2. Graph Essentials

Special graph
--gree& forest
----트리는 비방향성 그래프의 예, 어떤 node의 쌍이던 길이 1개만 있다, cycle이 없다, tree상의 |V|=|E|+1 (전체 노드 = 전체 엣지+1)
----forest 숲 = tree의 집합

--spanning tree
----모든 노드를 포함하는 그래프의 subgraph ,1개의 graph에 다수의 spanning tree가 있다
----대다수의 spanning tree가 가중치 그래프를 기반으로 작성되고 최소비용 spanning tree를 minimum spanning tree(MST)라 한다

--steiner tree
----spanning tree와 비슷하나 terminal 노드(여러 개의 node를 연결해주는 노드)가 2개 있을 때 가중치가 가장 줄어든다는 이론

--complete graph
----엣지들이 서로 겹치지 않는 상태로 그려진 그래프

--bipartite graph – 이분그래프
----인접 노드(서로 연결된) 끼리 서로 다른 색으로 칠할수 있는 그래프, 모든 노드가 2가지로 나눌수 있으며 같은 그룹끼리는 연결되지 않는 그래프


--affiliation graph
----이분 그래프의 일종으로 개인, 그룹으로 볼수있어서 다tndml 개인 노드가 특정 노드에 연결되어 있는 형태

--social affiliation network
----소셜 네트워크는 거대한 affiliation 의 조합이다, 1개인이 여러그룹(독서,운동 클럽등)에 소속될수 있고 해당 그룹의 집합이 소셜 네트워크를 이루기 때문


--regular graph
----모든 노드가 동일한 degree를 가지는 형태( 각노드의 연결된 엣지의 수가 같다)
----complete graph 는 regular graph의 한가지 예이다


--bridge
----다리처럼 해당 엣지를 제거하면 연결된 컴포넌트가 줄어드는 것, 그래프가 조작나는 중요한 엣지

--egocentric network
----전체 그래프에서 특정인원을 기준으로 추출한 네트워크



Graph algorithms -->graph/Netwok traversal algorithms
--graph와 tree의 탐색
----소셜미디어에서 사용자의 평균 나이를 계산한다면?
----하나의 시작지점에서 모든 사용자를 방문한다, 이때 한 사용자는 1번만 방문한다
----깊이를 먼저 탐색할까? = Depth first search –DFS
----넓이를 먼저 탐색할까? = Breadth First search - BFS


--깊이 우선 탐색=DFS
----노드에서 다음 노드로 이동시 하단에 있는 노드를 먼저 방문
----STACK 구조 기반

--넓이 우선 탐색=BFS
----노드에서 다음노드 이동시 옆에 있는 노드를 먼저 방문
----Queue 구조 기반



Finding shortest paths
--shortest path – 최단거리
----graph가 connected (모든 노드가 연결된상태)에서 임의의 노드 pair에서 가장 빠르게 갈수 있는길(path)

--Dijkstra’s algorithm = 다익스트라 알고리즘
----비-방향성 가중치 그래프에서 효과가 있다
----시작노드 s에서 어떤 노드든 해당 노드로 이동하는 최소한의 node비용을 계산
----최단거리와 해당 거리의 길이를 산출한다



Finding Minimum Spanning Tree
--Prim’s algorithms
----Minimum spanning tree
------random 노드를 선택
------다음 노드 선택시 엣지의 가중치가 낮은 노드로 이동(아직 선택되지 않은 노드에서)
-----막다른 노드에 왔을 때 이전 노드로 돌아와서 다시 낮은 가중치를 탐색한다
-----전체로 확장 될때까지 진행한다