Алгоритми та структури даних · Middle · Запитання 61 з 75
Як перевірити, чи можна розфарбувати граф у два кольори так, щоб жодне ребро не з'єднувало однакові?
- ✓Правильна відповідь: BFS чи DFS, даючи сусідам протилежний колір
- 2Порахувати вершини: можна, якщо їхня кількість парна
- 3Перевірити, що кожна вершина має не більше двох сусідів
Пояснення
Такий граф двочастковий. Конфлікт означає непарний цикл, і тоді двох кольорів замало. Типова задача: розділити людей на дві команди так, щоб суперники опинилися в різних.