[자료구조] 그래프 개념 - (1)

1. 그래프(Graph) 란?

G=(V,E)　where　V=Vertex,E=Edge 로 정의

V(G) = 노드 또는 정점, 공백이 아닌 유한집합
E(G) = 상이한 두 Vertex(정점)를 잇는 Edge(간선), 유한집합

 

1-1. 무향 그래프, 유향 그래프

Undirected Graph (무향 그래프)

• 물리학에서 정의하는 '속력' 과 같은 개념
• Edge를 표현하는 Vertex의 쌍에서 방향(순서) 가 없는 그래프
• 두 Vertec V0 와 V1을 잇는 Edge는 '( )' 로 표현
• (V0, V1) , (V1, V0) 는 같은 Edge를 나타낸다.
  (i.e E(V0,V1)=E(V1,V0))

Directed Graph (유향 그래프)

• Edge를 표현하는 Vertex의 쌍에서 방향(순서) 가 있는 그래프
  - 두 Vertex V0와 V1을 잇는 Edge는 '< >' 로 표현

• 물리학에서 정의하는 '속도' 와 같은 개념
• <V0, V1> , <V1, V0> 는 서로 다른 Edge를 나타낸다.
  (i.e E<V0,V1>≠ E<V1,V0>)
  

  

 

1-2. 완전 그래프 (Complete graph)

• Edge(간선)을 최대한으로 가진 그래프
• 그래프 최대 Edge 수
  정점이 n개인 무방향 그래프에서 최대 간선 수: C(n,2)=n(n−1)/2개
  정점이 n개인 방향 그래프에서 최대 간선 수: P(n,2)=n(n−1)개

[G5의 Edge(간선) 수]

Vertex(정점)의 개수: 4개 & 무방향 그래프
완전 그래프가 되기 위한 Edge(간선) 수: C(4,2)=4(4−1)/2=6개

 

[G6의 Edge(간선) 수]

Vertex(정점) 개수:4개고 & 방향 그래프
완전 그래프가 되기 위한 Edge(간선) 수: P(4,2)=4(4−1)=12개

 

1-3. 인접(Adjacent)과 부속(Incident)

무방향 그래프의 한 간선 (Vi​,Vk​)에 대하여

• Vj​와 Vk​ 는 서로 인접한다.
• Edge(간선) (Vj​,Vk​)은 Vertex(정점) Vj​와 Vk​에 부속한다.

 

1-4. 부분 그래프 (Sub Graph)

G =(V,E) 를 그래프를 나타내는 함수라고 하자. 다음과 같을때 (V', E')를 G의 부분 그래프(SubGraph)라 한다.

(a) V′⊆V 와 E′⊆E

(b) 모든 간선  ε∈E′ 에 대하여  ε가 v′ 와 w′에 부속된다면 v′,w′∈V′

 

1-5. 사이클(cycle)

• 첫 번째 지점과 마지막 정점이 동일한 단순 경로
• 무방향 그래프에서 Cycle의 길이는 항상 3 이상이고, 방향 그래프에서 Cycle의 길이는 항상 2 이상이다.
• 이러한 Cycle이 없는 그래프를 DAG(Directed Acyclic Graph)라고 한다.

아래 그림은 무방향 그래프와 방향 그래프에서 사이클을 나타낸 것이다.
그림의 a 그래프는 정점 V0​,V1​,V2​,V0​이 사이클이며 그림 b 그래프는 정점 V0​,V1​이 사이클이다.

 

---

참조

• https://kosaf04pyh.tistory.com/131
• https://kingpodo.tistory.com/45
• https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kimchoyoungg&logNo=220840052418