이분그래프 와 완전이분 그래프

이분그래프란

그래프 G=(V,E)에서 꼭짓점 집합 V가 V=V1 U V2 이고 V1 ∩ V2 = ∅ 을 만족하는 두 집합 V1과 V2로 분리되며 그래프의 모든 모서리가 V1의 한 꼭짓점에서 V2의 어떤 꼭짓점으로 연결되는 그래프

 꼭짓점 집합 V = {a,b,c,d,e,f} 를 두개의 집합 V1 = {a,c,e},V2={b,d,f} 로 분할 되며 V=V1 U V2 이고 V1 ∩ V2 = ∅ 을 만족하므로 이분 그래프이다.

이러한 이분 그래프를 찾는 방법은 두개의 색을 이용해서 색칠해 나가는 방법이 있다.

왼쪽부터 빨간점을 하나 찍고 그다음 연결되는 정점에 파란점을 찍고 파란점에 연결되는 다른 정점에 빨간점을 찍는식으로 분리한다.

 

완전이분그래프란

그래프 G=(V,E)에서 꼭짓점 집합 V가  V=V1 U V2 이고 V1 ∩ V2 = ∅을 만족하는 두 집합 V1과 V2로 분리되고, 그래프의 모든 모서리가 V1의 한 꼭짓점에서 V2의 모든 꼭짓점으로 연결되는 그래프이다.

위의 그래프에서 V1={a,c,e}, V2={b,d,f} 로 분리되는 이분그래프이면서

V1의 원소 a,c,e는 V2의 원소 b,d,f 에 모두 연결되는 그래프이다.

즉 완전 이분 그래프이다.

 

※ V는 Vertex(정점)을 의미하며 E는 Edge(엣지,모서리)를 의미하고 G는 Graph(그래프)를 의미하는 약자로 사용된다.

 

 

문제) 다음 그래프에서 이분그래프인지 이분그래프라면 완전이분 그래프인지 판별 하시오.

문제풀이)

위와 같이 a 의 위치에 빨간점을 찍고 d,f,b 에 파란점을 찍었는데 d와 f가 연결이 되고 있어서 이것은 분할을 할 수가 없기 때문에 이분그래프가 아니다.