Bipartite Graph
1. 이분그래프 정의
이분 그래프란 모든Edge(간선)이 U(위쪽의 Vertex)와 V(아래의 Vertex)사이를 잇는 형태의 그래프 이다.
위의 그림과같이 V->V , U->U 로 가는 Edge가 없는 그래프를 말한다.
위의 그림과 같이, 두가지 색만으로 그래프를 색칠 할려고 할때, 같은 Edge 를 사이에둔 Vertex 는 서로 다른색으로 색칠이 가능하다면 이분 그래프임을 알 수 있다.
2. 이분그래프 판별 알고리즘
앞선 정의를 이용해 이분그래프를 판별하는 알고리즘을 프로그래밍 해보았다.
방법은 간단하다. DFS(Depth First Search)를 이용해서 그래프를 탐색하면서 색을 칠해준다.(아래의 코드에서는 1,-1로 색을 칠하였다.)
색을 칠해야하는 Vertex의 Color 가 자신과 같은색깔로 칠해져있으면 false 를 반환한다.
만약 색이 칠해져 있지않다면, 반대색 (현재색을 c 로가졍하였을때 -c)를 칠해준다.
정상적으로 색이 다칠해지고 true 를 반환하면 이분그래프임을 확인할수 있다.
#define MAXV 20001
vector<int> Graph[MAXV];
int Color[MAXV];
bool DFS(int v, int c) {
Color[v] = c;
for (int i = 0; i < G[v].size(); i++){
if (Color[Graph[v][i]] == c){
return false;
}
if (Color[Graph[v][i]] == 0 && !DFS(Graph[v][i], (~c)+1)){
return false;
}
}
return true;
}
void isBipartiteGraph() {
int V, E;
bool isBipartite = true;
for (int i = 0; i < V; i++){
if (C[i] == 0){
if (!DFS(i, 1)){
isBipartite = false;
break;
}
}
}
if (isBipartite == true){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}
}
}
아래의 사이트는 이분그래프를 판별하는 문제이다.
Copyright (C) 2016 (DaeHyun, Hwang) all rights reserved.