🔸정의⭐

• (Node, Vertex) 와 (Edge, Link) 로 이루어진 자료구조.

• 집합으로 표현 가능

  $$ V=\lbrace A,B,C,D,E,F\rbrace \\E=\lbrace (A,B), (A,C),\cdots, (D,F)\rbrace \\G=(V,E) $$

• 인접 행렬(Adjacency matrix)로 표현 : edge에 해당하는 cell을 1로 표시. → 컴퓨터가 연산하기 편리

  	A	B	C	D	E	F
  A	0	1	1	0	0	0
  B	1	0	0	0	1	0
  C	1	0	0	1	1	0
  D	0	0	1	0	0	1
  E	0	1	1	0	0	0
  F	0	0	0	1	0	0

• 인접 리스트(Adjacency list)

  A	B	C
  B	A	E
  C	A	D	E
  D	C	F
  E	B	C
  F	D

• Order : the number of nodes

• Size : the number of edges

• Degree of nodes : the number of connected nodes

  

• Density : $\frac{2|E|}{|V|(|V|-1)}$

  • $\frac{|V|(|V|-1)}{2}$은 Complete Graph의 edge의 개수(=최대 edge 수)이다. 즉, |V| 개의 노드가 모두 연결되어 있는 그래프의 총 edge 개수는 $\frac{|V|(|V|-1)}{2}$ 이다.

  $$ D=\frac{2|E|}{|V|(|V|-1)}=\frac{|E|}{\frac{|V|(|V|-1)}{2}} \\0\leq\frac{|E|}{\frac{|V|(|V|-1)}{2}} \leq 1 $$

  ⇒ Density가 1이면 해당 그래프는 Complete graph이고, density가 0이면 edge가 없는 그래프. density가 1에 가까울수록 그래프는 촘촘하다(edge가 많다.).

🔻그래프의 종류

🔸Direction , Weight

• 방향성이 있는 여부에 따라

  

• edge의 가중치가 존재하는지 여부에 따라

  

🔸Complete Graph

• 모든 node가 연결된 그래프

  각 node별 edge의 개수 = (#node - 1)

🔸Cycle Graph

• cycle, loop graph