Graph Basics

Graph Basics

그래프 G는 Vertex와 Edge의 집합니다.

방향성 그래프 Directed graph   E<=V2

무방향성 그래프 Undirected graph E<=V(V-1)/2

인접 Adjacency : (u,v)라는 간선이 있다면, 정점 v와 정점 u가 인접하다고 한다.

       (무방향성 그래프는 인접관계 동일, 방향성 그래프에서는 같지 않음)

degree = out-degree + in-degree

경로 Path : 길이는 간선의 수

순환, 단일순환 cycle, simple cycle graph

비순환 그래프 An acyclic graph

연결 그래프 A connected graph

연결요소 Connected components

Strongly connected : 각 vertex가 서로 도달가능

A complete graph : 무방향성 그래프에서 모든 정점의 쌍이 서로 인접하는 경우.

Forest 순환하지 않는 무방향성 그래프

Tree 포레스트가 연결된 경우, 연결된 비순환 무방향성 그래프 ( Connected, Acyclic, Undirected Graph)

1. 두 정점은 단일 단순 경로(unique simple path)로 연결된다.
2. 간선을 제거 한다면 그래프틑 더이상 연결되지 않는다.
3. 간선하나를 추가하면 그래프는 순환을 포함하게된다.
4. E=V-1 만족

Dag 비순환 방향성 그래프 

Graph representation

• Adjacency-list 인접리스트
• Adjacency-matrix 인접행렬