[이산수학] (7) Connection

그래프 G에서 Walk란 모든 vertices가 그다음 vertices에 대해 adjacent(ex. v0~v1~v2~...~ve)한 sequence다. 

 

예를 들어 w1 = (v1,v2,v3,v2,v4,v5,v6,v4,v6,v7)은 (v1,v7), 길이 9의 walk다. 

walk의 vertices는 중복되어도 상관없다. 

 

만약 vertices가 중복되지 않은 walk라면 이는 path다.

위 예시에서 w3은 path다. 

 

그래프 G에서 (x,y) walk가 있다면, (x,y) path는 반드시 존재한다.

가령 walk가 v0~v1~ ... ~ vi ~ u ~ (... ~ u) ~ vj ~ ... ~ ve 이고, (... ~ u) 와 같이 중복되는 부분을 모두 잘라내면 path가 된다. 

 

V(G)의 x,y가 존재할 때, (x,y) walk가 존재한다면 x가 y에 connected되었다고 말한다.

 

adjacent와 connected는 다르다.

만약 x~y라면, x는 y에 connected되었지만

x가 y에 connected되었다고해서, x~y는 아니다.

 

connected라면 equiv relation에 놓여있음을 뜻한다.

첫째, 모든 V(G)의 v에 대해, (v, v) walk가 존재한다.

둘째, 만약 (x,y)라면, (y,x) walk가 존재한다. 

셋째, 만약 x가 y에 connected되었고 y가 z에 connected라면, (x,z) walk가 존재한다. 

 

x가 V(G)에 속할 때, x의 equiv class는 connected component다. 

그래프 G는 오직 하나의 connected component를 가질 때에 connected graph라 부른다. 이는 곧, 모든 x,y vertices에 대해 x가 y에 connected여야만 한다. 

 

e가 E(G)에 속할 때, 만약 G-e가 G보다 더 많은 connected components를 가진다면 e는 G의 cut edge다. 

 

예시1) G의 connected components는 2개 뿐인데, e edge를 없애주니까 3개로 늘었다. 이는 Null graph도 connected component로 처리하기 때문이다. 따라서 e는 cut edge다.

예시2) G의 connected component는 1개뿐인데, e를 제외해주면 2개가 되기 때문에 e는 cut edge다.

e'의 경우 G-e'의 connected component는 여전히 1개이기 때문에 cut edge가 아니다.

 

cut edge인지 아닌지 체크하기 좋은 방법:

G의 사이클은 length가 3 이상, 그리고 어떠한 vertices도 시점과 종점을 제외하곤 반복되지 않는 walk이다. 

 

e가 사이클에 포함되지 않을 때에만, e는 cut edge다.

증명) 

given, e = uv가 cut edge가 아니다. 

G와 G-e는 같은 수의 connected comp를 가진다.

만약 두개의 vertices가 G에서 connected되어있다면, G-e에서도 이 둘은 connected되어있다. 

 

G에서 u~v이다.

u는 v에 connected되어있다.

u는 G-e에서도 v에 connected되어있다. 

(u,v)라는 path p가 G-e에서 존재한다.

p + e는 G에서 사이클이며, 이는 e를 포함한다.

 

반대로, 

given e는 cycle에 포함되어있다.

두 vertices가 G에서 connected되어있다면, G-e에서도 vertices가 여전히 connected되어있다. 

만약 u1, u2가 G에서 connected되어있다고 가정해보자. 이 때 정의에 의해서 (u1, u2) walk w는 존재한다.

case1) 만약 w가 e를 포함하지 않는다면, (u1, u2)는 여전히 G-e에 존재한다. 따라서 u1은 u2에 connected다.

case2) 만약 w가 e를 포함한다면, (w-e) + (c-e) 는 (u1, u2) walk이다. 따라서 G-e에서 u1은 u2에 connected다.