[ 이산 수학 ] 19. 그래프 (3) path / connected

Path

 

Path ( 경로 ) : 인접한 vertex간 연결되어있는 길 

* n개의 vertex로 연결된 path는 n-1개의 edge가 있다. = 경로의 길

 

 

1) a - d - c - f - e 각 vertex 순서대로 이동하는 경로가 있고, vertex는 5개, 그 경로의 길이는 4

2) 이건 e > c edge가 없음

3) 이거도 1)이랑 같게 생각하면 됨

4) 길이는 5가 맞는데 한 번 갔던 edge 또 밟으면 simple path가 아니다.

 

 

---

 

Connectedness

: 특정 vertex 두 개를 기준으로 Path가 존재할 때 connected라고 한다.

 

connected component 이지, connected graph가 아님 

 

---

 

●  Cut Vertices 

: 1개의 vertex를 없앴을 때 disconnected가 되면 그 vertex = cut vertex

 

●  Cut Edge 

: 1개의 Edge를 없앴을 때 disconnected가 되면 그 edge = cut edge

 

---

 

 

Cut vertex 는 Disconnected로 만드는 하나의 vertex만 됐는데, Vertex Cut에서는  그런 역할을 하는 vertex set를 구하는 것이다.

 

왼쪽 그래프에서 disconnect로 만드는 vertex set은 {b,d} , {c,e} , {f,e} , ... 여러 개가 있는데 왜 K(G)= 1인가?

--> set는 무조건 2개의 원소가 있을 필요가 없다. 왼쪽 그래프에서 b,c,e 모두 verteex cut이 가느앟다.

 

 

 

 

K(G) 는 Minmum number  of vertex cut이다.

 

 

● Strongly Connected : 방향 고려하여 서로에 대한 경로가 있는 그래프

 

● weakly Connected : 방향은 고려하지 않고, Indirect로 생각했을 때 모두 연결되어 있는 그래프

 

 

 

 

 

 

---

 

 

 

 

---

Euler Paths and Circuits

 

 

●   Euler Paths  : 가기만 함 ( 안 돌아옴 )

     →  모든 Edge를 지나고 끝나는 거 , 다시 돌아오지 않음
          그래서 시작과 끝 vertex의 deg는 홀수다.

         = 단 2개의 vertex만 deg가 홀수여도 됨 

 

 

●  Euler Circuits : 갔다 올 수 있어야 함

     → 모든 노드의 degree가 짝수여야한다
     ex) 하나는 들어오는 용, 하나는 나가는 용

다른 vertex를 돌고 다시 돌아온다

 

 

 

(참고)

http://bigdata.dongguk.ac.kr/lectures/disc_math/_book/9.5-%EC%97%B0%EA%B2%B0-%EA%B7%B8%EB%9E%98%ED%94%84.html

 

(출처)

 

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