2färgbarhet

2färgbarhet är ett begrepp inom grafteori som beskriver om en graf går att färga med två färger så att närliggande hörn får olika färger. En graf som uppfyller detta villkor kallas tvåfärgbar eller bipartit. Egenskapen gäller per kopplad komponent, så varje komponent kan färgas separat utan att färgerna behöver vara konsekventa mellan komponenterna.

En graf är 2färgbar om och endast om den är bipartit. En praktisk karaktärisering är att grafen inte innehåller någon udda cykel; det vill säga alla cykler har jämn längd. Om grafen innehåller en udda cykel kan den inte färgas med endast två färger. Omvänt är varje cykel som består av jämna antal hörn färgbara i två färger.

Algoritmiskt kan man avgöra 2färgbarhet med en bredde-först-sökning (BFS) eller djupet-först-sökning (DFS). Man tilldelar startnoden färg 0 och färgar dess grannar med färg 1, och så vidare. Om man stöter på en granne som redan har samma färg som noden där man kom från uppstår en konflikt och grafen är inte 2färgbar. Lösningen körs i tidskomplexitet O(V+E), där V är antal hörn och E antal kanter.

Exempel på 2färgbara grafer är träd, vägar och till och medkantade cykler med jämn längd (till exempel C4). Exempel som inte är 2färgbara är C3 och andra cykler med udda längd.

Andra relaterade begrepp är kromatiska talet: en graf är 2färgbar om och endast om dess kromatiska tal är at most 2. Bipartita grafer används ofta i matchningsproblem och i modellering av tvåtillståndsproblem.