無向グラフ - 二部グラフ判定

概要

与えられた無向グラフが二部グラフであるかどうか判定する.

参考

• 二部グラフ判定をUnionFindTreeで行う - noshi91のメモ

アルゴリズムの詳細

参考に書いてあるとおりにやる.

すなわち, 頂点 \(u\) がグループ \(1,2\) にあることを表す述語 \(P^1(u), P^2(u)\) を用意して, エッジ \(e = (u, v)\) を \((P^1(u) \land P^2(v)) \lor (P^2(u) \land P^1(v))\) と解釈して論理グラフを組み立てて（頂点が命題で連結なときには同時に成り立つ）, 最後に矛盾 (\(P^1(u) \land P^2(u)\)) が無いことを確認する.

実装

論理グラフは同じグラフに所属するかだけが問題なので, これを UnionFind で実装する.

/// Graph - Undirected - is Bipartite Graph?
use crate::set::union_find::*;

pub fn is_bigraph(neigh: &[Vec<usize>]) -> bool {
    let n = neigh.len();
    let mut uf = UnionFind::new(n * 2);
    for u in 0..n {
        for &v in neigh[u].iter() {
            uf.merge(u * 2, v * 2 + 1);
            uf.merge(u * 2 + 1, v * 2);
        }
    }
    for u in 0..n {
        if uf.is_same(u * 2, u * 2 + 1) {
            return false;
        }
    }
    true
}

#[cfg(test)]
mod test_is_bipartite_graph {
    use crate::graph::undirected::is_bigraph::*;

    #[test]
    fn it_works() {
        assert!(is_bigraph(&vec![vec![]]));
        assert!(is_bigraph(&[vec![1], vec![0]]));
        assert!(is_bigraph(&[vec![1], vec![2], vec![]]));
        assert!(is_bigraph(&[vec![1], vec![2], vec![3], vec![]]));
        assert!(is_bigraph(&[vec![1], vec![2], vec![3], vec![0]]));
        assert!(!is_bigraph(&[vec![1], vec![2], vec![0]]));
        assert!(!is_bigraph(&[vec![1], vec![2], vec![3], vec![4], vec![0]]));
    }
}