Test bipartitnosti

O(V + E)

Graf je bipartitní, když jdou jeho vrcholy rozdělit do dvou množin tak, že každá hrana spojuje vrchol z jedné s vrcholem z druhé — nikdy v rámci jedné množiny. Ekvivalentně neobsahuje žádný cyklus liché délky. Otestuje se obarvením pomocí BFS: startu dej barvu A, každému sousedovi opačnou barvu a tak dál. Pokud někdy narazíš na hranu, jejíž oba konce už mají stejnou barvu, je to hrana v rámci množiny a graf bipartitní není. Průchod je O(V + E). Bipartitní struktura stojí za párováním, rozvrhováním i dvoustrannými trhy.

Klik do prázdna = vrchol · klik na 2 vrcholy = hrana · táhni = posuňStart: A
Vstupní graf
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Obarvi startovní vrchol barvou A.
  2. Každému nenobarvenému sousedovi dej opačnou barvu a zařaď ho.
  3. Pokud hrana spojí dva vrcholy stejné barvy, skonči — není bipartitní.
  4. Když se všechny vrcholy obarví bez konfliktu, graf je bipartitní.

Pseudokód

1isBipartite(graph):                  # O(V + E)2  for each uncoloured vertex s:3    colour[s] ← 0; queue ← [s]4    while queue not empty:5      u ← queue.dequeue()6      for v in neighbours(u):7        if v uncoloured:8          colour[v] ← 1 − colour[u]   # opposite side9          queue.enqueue(v)10        else if colour[v] = colour[u]:11          return false                # same-side edge → odd cycle12  return true