Day_01_1. Graph Essentials

graph representation
--graph representation
----그래프는 보기에는 직관적이나 수학적 계산 및 컴퓨팅 tool을 사용하기에는 적합하지 않음
-----목적=정보를 손실하지 않고 그래프 그리기,컴퓨터로 계산하기 쉽고 수학적 방법론이 있다

--근접 행렬-adjacency metrix
----x축의 table에서 서로 관계가 있으면 1, 없으면 0으로 표현
----social media 에서는 사용하기 나쁨, 대다수의 field가 0으로 채워져 있기 때문(sparse 함)

--근접 리스트 – adjacency list
----실제 관계가 겅립된 사람들만 표시하는 것, nodes -- > connected to로 표현

--edge list
----각 노드간 엣지만 모아서 list화 시킨 것, 훨씬 간결하고 효과가 좋다


Type of graph
--null / empty graph
----null graph = 각 노드가 null인 것 , node가 하나도 없는 것, 당연히 edge도 없다
----empty graph = 노드는 있으나 노드 사이에 edge는 없다
----null graph는 는 empty그래프가 될수 있으나 역은 성립하지 않는다

--Directed / indirected / mixed graph
----방향성 directed에서의 엣지간의 역은 성립하지 않는다
----비-방향성 undirected에서는 역도 같다

--simple / multi graph
----각 node간의 연결이 1개일 때 = single , 1개이상 = multi graph , 근접행렬에서 table은 연결된 숫자만큼 적어둔다

--weighted graph
----가중치 그래프로서 각 node사이의 edge에 수치가 적혀있다 G(V,E,W)로 표기
----가중치 graph 상에서 w가 0이면 node가 연결 사항이 없는 것

--signed graph
----weigh의 표기가 binary(0/1 , +/- , -1/1)으로 표기된 것
----가중치 그래프 상에서 w가 0이면 node간 연결사항이 없는 것


--web graph
----web상에서 site가 어떻게 서로 연결되어 있는지 표현
----일반적으로 directed, multi graph 의 형태
----node는 site, edge는 link로 대입
----loop 도 존재한다( 자기자신에게 돌아오는 링크)


connectivity in graph
--Adhacent nodes and incident edges
----두개의 node가 연결되어 있을 때 adjacent 하다고 표현
----incedent = 2개의 edge가 1개의 end-point를 공유할 때 쓰는 표현, 방향성 graph에서는 방향성까지 같아야 incedent 하다고 표현한다


--walk/path/trail/tour/cycle
----walk = incedent 하면서(경로가 겹치면서) node를 방문하는 것
------------open walk = 시작지점에서 끝나지 않는 것
------------close walk = 시작 지점에서 끝나는 것
------------length of walk = 방문한 edge의 수
----trail = graph 상에서 각 엣지를 1회이상 방문하지않고 전체를 방문하는것
------------close tail = 시작지점에서 trail 이 끝나는 것, tour, circuit이라고 한다
----path = edge가 모두 같은 방향으로 이동하며 edge가 겹치지 않는 것,
------------모든 노드를 방문할 필요는 없다, path의 크기는 방문한 엣지의 수

----example)
----Eulerian tour – 모든 edge를 1회만 방문해서 전체 node탐색
----hamiltonian cycle – edge를 1회만 방문하여 다시 시작점으로 돌아온다


--random walk
----시작 node에서 다음 node로의 이동이 random 으로 진행
----mark a spot on the ground 게임(격자무늬의 바닥에 동전의 앞뒤에 따라 동서남북으로 이동하는것, 동전이 많으면 방향도 증가한다)


--connectivity 

----node i와 j가 엣지를 이용해 서로 연결되어 있을때를 의미
----방향성 graph에서의 strongly connection –노드 i에서 j로 가는 길이 있다
----방향성 graph에서의 weakly connection – 노드 i에서 j로 갈수 없다


--component
----비방향성 graph에서 -->연결된 subgraph
----방향성 graph 에서 --> 어떤 노드의 쌍에서도 이용이 가능하며 반대도 가능하다


--shortest path 최단거리
----2개의 node 사이에 가장 짧은 거리로 이동하는 것
----보통 node간의 이동은 최단거리를 기준으로 진행한다
----n- hop neighborhood 는 n번만에 이동 가능한 node들을 의미함


--Diameter 직경
----그래프상에서 가장 긴 거리의 path를 graph의 diameter

--근접행렬과 연결성
----근접행렬상에서 노드 I,j사이의 node의 수