112. Bipartite Graph

음이 아닌 정수 $k$에 대해 그래프가 다음 조건을 만족하면 그 그래프를 $k$분 그래프(${\color{#FF0000}k}$-partite Graph)라고 한다.

• 정점을 $k$개의 그룹으로 분리했을 때 간선으로 직접 연결된 두 정점이 항상 서로 다른 그룹에 속하게 할 수 있다.

이중 $k = 2$일 때 조건을 만족하는 그래프를 이분 그래프(Bipartite Graph)라고 한다. 이분 그래프에 존재하는 모든 사이클은 길이(사이클에 포함된 정점의 수)가 짝수이며, 그 역도 성립한다. 모든 트리는 이분 그래프이다.

 

어떤 그래프가 이분 그래프인지 확인하는 방법은 간단한데, 임의의 정점에서 DFS를 시작해서 인접한 정점을 탐색할 때마다 그 정점을 이전 정점과 다른 그룹에 추가한 다음 DFS가 끝났을 때 간선이 연결하는 두 정점이 항상 서로 다른 그룹에 포함되는지 확인하면 된다.

 

아래와 같은 그래프가 있을 때 정점 $\text{G}$에서 DFS를 시작해서 정점 $\text{B}$, $\text{F}$, $\text{D}$, $\text{E}$, $\text{C}$, $\text{I}$, $\text{H}$, $\text{A}$의 순서대로 방문했다고 하면,

정점을 파란색과 빨간색 그룹으로 나누었을 때 간선이 연결하는 정점은 항상 파란색 정점 $1$개와 빨간색 정점 $1$개이다. 따라서 이 그래프는 이분 그래프이다.

만약 정점 $\text{A}$와 정점 $\text{D}$를 연결하는 간선을 그래프에 추가한다면 이 간선이 같은 색의 정점을 연결하므로 그래프는 더이상 이분 그래프가 아니다.

이분 그래프 판별은 BFS로도 할 수 있으며 둘 중 편한 것을 사용하면 된다. 대체로는 DFS로 판별한다.

 

DFS로 그래프가 이분 그래프인지 판별하는 것은 다음과 같이 구현할 수 있다.

#import<bits/stdc++.h>
using namespace std;
int p = 1, group[100005];
vector<int>e[100005];
void dfs(int node, int c)
{
    if(group[node])
    {
        if(group[node] != c)p = 0;
        return;
    }
    group[node] = c;
    for(auto &p: e[node])dfs(p, 3 - c); // c는 1 또는 2이며 인접한 정점으로 넘어갈 때마다 바뀜
}
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!group[i])dfs(i, 1);
    }
}

DFS의 실행이 끝난 후 $p$가 $1$이면 그래프는 이분 그래프이고, $p$가 $0$이면 그래프는 이분 그래프가 아니다. 그래프가 연결 그래프가 아닐 경우 코드의 마지막 부분과 같이 각각의 컴포넌트를 확인해야 한다. 그래프가 연결 그래프라면 한 번의 DFS로도 충분하다.

---

어떤 $k$분 그래프는 완전 $k$분 그래프(Complete ${\color{#FF0000}k}$-partite Graph)라고 불리는데, 이런 그래프는 서로 다른 그룹에 속하는 정점들 사이에 항상 간선이 존재한다. 마찬가지로 $k = 2$일 경우 완전 이분 그래프(Complete Bipartite Graph)라고 한다.

 

이 그래프는 완전 이분 그래프이다.

여기서 두 그룹에 속하는 정점의 수가 각각 $3$, $4$이며 이런 그래프를 $K_{3, 4}$로 표기한다. 비슷하게 각 그룹에 속하는 정점의 수가 각각 $n_1, n_2, \ldots, n_k$인 완전 $k$분 그래프를 $K_{n_1, n_2, \ldots, n_k}$로 표기한다.

---

이분 그래프 외의 다른 $k$분 그래프는 흔히 다루는 주제는 아니다. $k = 0$인 $0$분 그래프는 정점과 간선이 모두 없는 그래프이며 이런 그래프를 공 그래프(Empty Graph)라고 한다. $k = 1$인 $1$분 그래프는 간선이 없는 그래프인데 이런 그래프를 무변 그래프(Edgeless Graph)라고 한다. 둘 다 접할 일이 별로 없을 것이다. 그밖에 $k = 3$인 삼분 그래프(Tripartite Graph)는 아주 가끔씩 등장하는데 이 그래프 역시 기본적인 단계에서는 크게 신경쓰지 않아도 된다.

 

[참고 링크]

 

이분 그래프

 

[연습문제]

 

BOJ 1707. 이분 그래프 (Gold IV)

그래프가 이분 그래프인지 판별하면 된다.

 

BOJ 11668. 파이프 청소 (Platinum IV)

파이프를 정점으로 간주하면 파이프끼리 수원지가 아닌 곳에서 교차할 경우 정점 사이에 간선이 있다고 할 수 있다. 이렇게 해서 만들어진 그래프가 이분 그래프라면 possible, 이분 그래프가 아니면 impossible이 답이다.

 

CF 1093D. Beautiful Graph (1700)

그래프가 이분 그래프가 아닌 경우 답은 $0$이다. 그래프가 이분 그래프인 경우 각각의 컴포넌트에서 두 그룹의 크기 $x$, $y$에 대해 $(2^x + 2^y)$를 모두 곱한 값이 답이 된다.

 

CF 1537F. Figure Fixing (2200)

$t_i - v_i = a_i$라고 하면, 입력되는 그래프가 이분 그래프인 경우 양쪽 컴포넌트에 속하는 정점들에 대해 $\sum a_i$의 값이 서로 같으면 YES, 다르면 NO가 답이고, 이분 그래프가 아닌 경우 $\sum a_i$가 짝수면 YES, 홀수면 NO가 답이다.

 

→ solved.ac tag: bipartite_graph