Algorithmen und Datenstrukturen · Middle · Frage 61 von 75
Wie prüft man, ob sich ein Graph mit zwei Farben so färben lässt, dass keine Kante gleiche Farben verbindet?
- 1BFS oder DFS, Nachbarn bekommen die Gegenfarbe
- 2Knoten zählen: es geht, wenn die Zahl gerade ist
- 3Prüfen, dass jeder Knoten höchstens zwei Nachbarn hat
Antwort zeigen
Richtige Antwort: BFS oder DFS, Nachbarn bekommen die Gegenfarbe
Erklärung
Ein solcher Graph ist bipartit. Ein Konflikt bedeutet einen ungeraden Zyklus, und dann reichen zwei Farben nicht. Typische Aufgabe: Menschen in zwei Teams aufteilen, sodass Rivalen in verschiedenen Teams landen.