Dreifarbenproblem

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
  1. Dorothea Wagner: Theoretische Grundlagen der Informatik. (PDF; 874 kB) Vorlaufiges Skript zur Vorlesung. S. 65, abgerufen am 18. Februar 2012.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.