Graph

●Graph G = (V, E)

 ▷정점(Vertex)과 변(Edge)으로 구성된 자료 구조.

  ▷V = {v1, v2, ... , vn} : vertex, node, 정점

  ▷E = {e1, e2, ..., en} : edge, arc, 간선, 변

 

 ▶Directed / Undirected

  ▷Directed: ek = (vi, vj), 방향이 있음 (순서가 의미 O)

   ▷e = (a, b)에서의 표현

  ▷Undirected: ek = {vi, vj}, 방향이 없음 (순서가 의미 X)

 

 

○Connected Graph

 ▷Undirected Graph G = (V,E)에 대해, 어느 두 Vertex를 잡아도 Path가 존해하는 Graph

 

 ▶Connected Components

  ▷Undirected Graph의 일부로 만든 Connected Graph.

  ▷κ(G): Connected Components의 개수, 1이면 Conncted Graph

 

 ▶Connectivity (directed에서)

  ▷Strongly: 모든 {a, b}에 대해 a->b, b->a의 path가 존재.

  ▷Unilaterally: 모든 {a, b}에 대해 path가 최소 하나 존재함. (a->b, b->a 중 하나)

  ▷Weakly: direction을 무시했을때, 모든 {a, b}에 대해 path가 존재함.

 

 

○Multigraph

 ▷x, y ∈ V에 대해 2개 이상의 edge가 존재함.

 ▶Multiplicity: x, y사이의 edge의 개수

 

 

○Subgraph

 ▷그래프의 일부를 가져온 그래프.

 ▷G=(V,E)에서 V1 ∈ V, E1 ∈ E인 G1(V1,E1)

 

 ▶Spanning Subgraph

  ▷V1 = V인 Subgraph (Vertex는 동일하고, Edge가 다름)

  ▷G1은 G의 Spanning Subgraph이다.

  ▷G - e = Spanning Subgraph

 

 ▶Induced Subgraph

  ▷가져온 Vertex들에 대해 원래의 모든 Edge를 가진 Subgraph

  ▷G - v = Induced Subgraph

 

 

○Complete Graph (Kn)

 ▷n개의 Vertex에 대해 모든 a,b가 연결된 그래프. (Loop는 없음)

 

 

○Complement Graph

 ▷Loop가 없고 n개의 Vertex를 가진 Undirected Graph에 대해, 모든 Vertex를 가졌으며 Kn과 비교했을때 없는 Edge들만을 가진 Graph

 ▷Edge들에 대해 Kn - G

 

 

○Bipartite Graph (

 ▷Vertices를 2개를 그룹으로 나눴을때, 같은 Vertex 그룹 사이에서는 edge가 없는 그래프.

 ▷V = V1 ∪ V2, V1 ∩ V2 = ø, {a, b}: a ∈ V1, b ∈ V2

 

 ▶Complete Bipartite Graph (K_m,n)

  ▷Bipartite에서 연결가능한 것을 모두 연결.

  ▷m개와 n개의 그룹으로 나뉨.