二部グラフ判定
Abstract
Explanation
判定には, 以下の定理を利用する:
Theorem (二部グラフの特徴づけ)
グラフ$ Gが二部グラフ$ \Longleftrightarrowグラフ$ Gは2-彩色可能.
Proof
TODO 書く.
グラフ$ Gのある頂点$ v \in V(G)からDFSやBFSを利用しながら各頂点を2色で彩色していき,
矛盾がなければ$ Gは二部グラフである
矛盾が生じれば$ Gは二部グラフでない
と判定すればよい.
Implementation
DFSを利用して実装した.
Input
グラフ (頂点は0-indexed, 連結とは限らない) の隣接リスト E
Output
二部グラフになっていれば, 各パートに含まれる頂点集合のリスト [U_1, U_2] のリスト
そうでなければ, None を返す.
Time complexity
$ O(|V| + |E|)time.
code:python
def bipartite(E):
'''
Input:
E: the adjacency list of the graph
Output:
If the graph is bipartite, return [U_1, U_2 (the parts of the bipartite graph) for each component]. Else, return None.
'''
N = len(E)
part = []
for x in range(N):
if colorx is not None: continue stack = (x, 0) # color x with 0 parts = ], [
while stack:
v, c = stack.pop()
if colorv is not None: # consistent continue
if coloru is None: # not visited yet stack.append((u, c^1)) # paint u with different color from v's one
elif coloru != c: # consistent continue
else: # inconsistent
return None
part.append(parts)
return part
Verification
特になし.
References
特になし