[이산수학] (6) Subgraphs

G, H를 그래프라고 가정하자. V(G)가 V(H)의, E(G)가 E(H)의 하위집합일때, 우리는 G가 H의 subgraph라 부른다.

위 예시처럼 vertices는 모두 같은데, E(H)가 E(G)보다 더 큰 집합일 경우 H가 G의 상위집합이다. 따라서 G는 H의 subgraph이다. 

 

G'는 E(H)에는 없는 v1v5 edge를 갖는다. 따라서 E(G')는 E(H)의 부분집합이 아니기에 G'은 H의 subgraph가 못된다.

 

G, H가 graph일때, 만약 G가 H의 subgraph이고 V(G)=V(H)라면, G는 H의 spanning graph이다.

즉 모든 꼭짓점이 동일한데 edge set만이 부분집합이면 spanning graph이다. 위 예시에선 G는 spanning이 아니지만 G~은 spanning subgraph이다. 

 

G가 graph일 때, E(G)의 특정 e에 대해 G-e는 V(G-e) = V(G)이고, E(G-e) = E(G) - {e}이다. 이를 Edge deletion이라 부른다.

간단히 말해 하나의 변만을 삭제하는 경우다. 이 경우 vertices는 없어지지 않기 때문에 G-e의 vertices set이나 G의 vertices set이 같다. 그러나 E(G-e)는 E(G)에서 e를 뺀 것이다. vertcies set은 여전히 같다는 점에서 G-e는 G의 spanning graph이다. 

 

1) 모든 e에 대해서 G-e는 spanning subgraph다. 

2) e1, ..., ek에 대해 G-e1, ... , G-ek는 G의 spanning subgraph다. 

3) 만약 H가 spanning subgraph of G라면, H = G- e1 -e2 -... -ek for some k>=1이다. 

따라서 spanning graph를 구하기 위한 단 하나의 방법은 edge deletion뿐이다. 

 

 

G가 graph일때, 

1) 만약 어떠한 서로 다른 두 vertices(in S)가 G에서 adjacent(근접)한다면 V(G)의 subset S는 clique라 불린다. 즉, clique subgraph는 complete subgraph다. 

2) clique number(=w(G))는 largest clique의 수다. 

 

{v4}, {v3,v6}, {v1,v2,v4}, {v3,v4,v5}는 clique다. 4개 이상의 clique가 없기 때문에 w(G) = 3

 

1) 만약 S의 어떠한 두 vertices가 not adjacent하다면 V(G)의 subset S는 independent set이라 불린다. 즉, S는 null graph다. 

2) independence number(=L(G))는 가장 큰 independent set의 size다.

 

예시1. {v4}, {v1,v4}, {v3,v1}, {v1,v4,v3} L(G)=3

 

complement graph of G는 G bar다. vertices set은 같지만, E(G)의 element가 정반대여야한다.

 

G bar의 특성은 다음과 같다.

1) G complement of complement = G

2) G U G bar = Kn

 

S: clique = complete subgraph , w(G) = size of largest S

S: independent set, L(G) = size of largest S

 

3) G에서의 clique는, G bar에서의 independent set이다.

 

prop1. w(G) = L(G bar), L(G) = w(G bar)

예시2. 그림을 잘 못그렸는데 v2,v3,v4가 G bar에서 clique가 된다. property3에 의해 G에서는 clique였던 {v1,v4,v5}가 G bar에서는 independent set이다. 

w(G) = L(G bar) = 3, w(G bar) = L(G) = 3

 

 

G가 최소 6개의 vertices를 갖춘 그래프라고 가정하자. 그럼 w(G)>=3 이거나 w(G bar) = L(G) >= 3이다. 

pf)

특정 v는 d(v)>=3 or d(v)<=2다.

1) 만약 d(v)>=3이라면 서로다른 x,y,z in N(v)가 있을테다. 만약 xy, yz, xz가 E(G)에 있다면 K3인 subgraph가 존재한다. 즉, W(G)>=3이다. 만약 없다면 {x,y,z}가 서로 independent set이기 때문에 L(G)>=3이다. 

 

2) d(v)<=2라면 G bar의 d(v)>=3다. G와 G bar의 union은 Kn이기 때문이다. 

특정 vertices v에 대해 adjacent한 x,y가 있다고 가정하자. 이 때 x~v라면 w(G)>=3이다. 아니라면 w(G bar)>=3이다. 

따라서 vertices 가 6개인 모든 graph에 대해 R(3,3)은 성립한다. 따라서 R(3,3) = 6이다. 

 

k,l이 정수집합에 속할 때, 우리는 R(k,l) = min{N| every graph G with N vertices satisfying either w(G)>=k or L(G)>= l}으로 ramsey number를 정의한다. 즉, Ramsey number는 w(G)>=k 혹은 L(G)>=l을 만족하는 N개의 vertices를 가진 모든 그래프의 N이다. 

 

R(3,3) <= 6 이고, R(3,3) >5 라서 R(3,3)=6이다.

5개의 vertices를 가진 G의 w(G)=2, L(G)=2다. 모든 5개의 vertices를 가진 graph에 대해 R(3,3)이 성립해야 Ramsey number가 될 수 있기 때문에 이렇게 반례를 들어 5보다 큼을 보인다. 

 

1) R(k,l)은 유한하다. 

2) R(k,l) = R(l,k)다.

3) R(3,) = 6, R(4,4) = 18이고 R(5,5)는 찾기 힘들다...