二部グラフ

二部グラフ

定義

頂点集合を二つに分割して、その中には辺がないようにできるグラフ

性質

1. 二色に塗り分けることができる
2. 奇閉路が存在しない（逆も言える）
3. 木は二部グラフ

判定

bfsなどで色を塗っていき矛盾が起きなければ、二部グラフ

def is_bipartite(G):
    n = len(G)
    color = [-1]*n
    que = deque([0])
    color[0] = 0
    while que:
        v = que.pop()
        c = color[v]
        for nv in G[v]:
            if color[nv]<0:
                color[nv] = 1-c
                que.append(nv)
            elif color[nv] == c:
                return False
    return color

問題

頂点集合を二つに分けるパターンと距離の偶奇に関するパターンの二つがあるっぽい 例題1 「頂点集合を二つに分ける」という設定から二部グラフを想起したい。補グラフを考えると、二部グラフに帰着する

例題2 長さ奇数の道があるような2頂点間には必ず辺が惹かれることに築けば二部グラフ