Top-Fragen
Zeitleiste
Chat
Kontext

Dreifarbenproblem

Aus Wikipedia, der freien Enzyklopädie

Remove ads

Das Dreifarbenproblem ist ein Entscheidungsproblem aus der Graphentheorie. Gefragt ist, ob die Knoten eines einfachen Graphen so mit drei Farben einfärbbar sind, dass zueinander benachbarte Knoten unterschiedliche Farben haben. Das Problem ist NP-vollständig.[1]

Eine Verallgemeinerung ist das Färbungsproblem. Bekannt ist auch eine als Landkartenfärbungsproblem bekannte Variante.

Einzelnachweise

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads