Algorytmy i struktury danych · Middle · Pytanie 61 z 75
Jak sprawdzić, czy graf da się pokolorować dwoma kolorami tak, by żadna krawędź nie łączyła tych samych?
- ✓Poprawna odpowiedź: BFS lub DFS, nadając sąsiadom przeciwny kolor
- 2Policzyć wierzchołki: da się, gdy ich liczba jest parzysta
- 3Sprawdzić, czy każdy wierzchołek ma najwyżej dwóch sąsiadów
Wyjaśnienie
Taki graf jest dwudzielny. Konflikt oznacza cykl nieparzysty i wtedy dwa kolory nie wystarczą. Typowe zadanie: podzielić ludzi na dwie drużyny tak, by rywale trafili do różnych.