data structure graph
data structure playlist
https://www.youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P
https://youtu.be/gXgEDyodOJU
tree의 경우 node가 N개 있는 경우 edge는 N-1개가 있다.
graph는 이런 rule 이 없음
tree는 graph의 한 형태 이다.
ordered pair를 표현할때는 ( )
unordered pair를 표현할때는 { } 를 사용한다.
.
.
.
.
.
https://youtu.be/AfYqN3fGapc
self loop의 한 예로 한웹페이지에 있는 자기자신으로의 link를 예로 들수 있다. 링크를 클릭하면 자기자신 페이지가 리프레쉬 된다.
만약 self-loop, multiedge가 없는 경우 simple graph라고 한다.
simple graph라고 가정할때 n 개의 node는 n(n-1)의 directed edges를 가질수 있다.
simple graph의 경우 n개의 node는 n(n-1)/2의 edges를 가진다.
edges를 많이 가진 graph의 경우 dense하다고 하며
edges를 적게 가진 graph의 경우 sparse하다고 한다.
simple graph : self-loop , multiedges를 가지지 않는 graph
simple path : path가 반복되는 vertices(node)를 가지지 않는 path (물론 당연히 반복되는 edges 도 없게된다)
또 반복되는 vertices(node)를 가지지 않는 walk (물론 당연히 반복되는 edges 도 없게된다)를 흔히 path라고 하기도 한다.
trail의 경우 vertices(nodes)는 반복되도 되지만 edge는 반복되지 말아야 한다.
어느 node에서건 다른 모든 node로 갈수 있는 경우(다른 node를 거쳐서 가는것 허용됨) strongly connected graph 라고 한다.