[ 이산 수학 ] 18. 그래프 (2)

Adjacency List

 

 

Adjacency(인접) : 해당 vertex와 Edge하나로 이어져있는 관계를 뜻한다.

 

● Simple graph : [ Vertex - Adjacent vertices ] 관계로 이루어져있다.

● Directed graph : [ Initial vertex - Terminal vertices ] 관계로 이루어져있다.

 

 

---

행렬을 통한 그래프 표현

 

•  Adjacency matrix

  : 행과 열이 Vertex로 이루어져있다 + 두 vertex가 인접하면 1, 아니면 0

   1) n*n matrix이다.

 

   아래 그래프가 어떤 성향을 띄고있는지 분석해보자

 

 

0,1이 아닌, edge의 개수로 나타내는 matrix도 가능하다

 

 

*참고

●  Directed 는 ( a, b )= 순서 중요

●  Undirected 는 { a, b } = 순서 별로 안 중요

 

 

•  Incidence matrix

  : 행이 Edge  열이 Vertex 를 나타낸다. (세로: vertex / 가로: edge)

 

Vertex에 Edge가 연결되어 있으면 1, 아니면 0 

* Vertex끼리의 관계가 아니라, Vertex와 Edge의 관계를 나타낸다.

 

v1이 e1,e2와 연결되어 있으므로 둘 다 1로 표시한다.

 

---

Isomorphism

모양은 달라(져)도 연결 관계들이 같으면 ㅇㅋ

즉 두 개의 그래프를 함수로 Mapping 했을 때 같은 형태인 것

그리고 그 함수는 one-to-one함수여야 한다!

 

---

https://velog.io/@jnary/%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99-10.3-Representing-Graphs-and-Graph-Isomorphism

 

동형인지 판단하는 법 

 

두 개의 Graph가 ...

1. 전체 Vertex의 개수가 같은지

2. 전체 Edge의 개수가 같은지

3. Vertex의 Degree가 같은지 + 이웃한 vertex들의 Degree도 같은지

 

 

예) 아래 두 개의 그래프가 Isomorphic한지 보자.

 

1. 전체 vertex 수 4개로 같음

2. 전체 edge 수 4개로 같음

3. Vertex의 Degree : 모두 2 / 모두 2 

 + 이웃한 vertex의 degree도 두 그래프 모두 다 2

 

위 두 그래프는 Isomorphic하다.

 

 

---

예) 

왼쪽 G / 오른쪽 H

왼쪽에 두 그래프가 Isomorphic한가?

 

두 그래프 모두

1. Vertex 개수 : 8개

2. Edge   개수 : 10개

3. 4개의 vertex의 degree = 2 , 4개의 vertex의 degree = 4

 

이라서 Isomorphic으로 보일 수 있지만, 이웃 Vertex의 degree도 분석해야한다. 

1) G에서 deg(a) = 2이다.

2) H에서 deg(#) =2인 것은 t,u,x,y이다. 

마지막으로, Vertex a이웃의 deg 즉 , deg(b) = deg(d) = 3이다.

그럼 t,u,x,y의 이웃 vertex들의 deg를 보자

 

두 개의 deg가 3인 것은 아무것도 없다. 

 

따라서 Isomorphic하지 않다. 

 

---

 

예) 

 

이거도 분석해보셈

 

 

 

(참고)

https://velog.io/@jnary/%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99-10.3-Representing-Graphs-and-Graph-Isomorphism

 

(출처)

한동대학교 최희열교수님 - 이산수학