Metraipolis › archive › dc_240b3dc68bcb

Dreifarbenproblem — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Dreifarbenproblem
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T17:08:06.305Z
SHA-256 of the archived text
2ddb362b08c16ae1134dd2f03fbf5c65eaa2a604f3ed2fbc3c73283e0fa6bcbf
Stable URL of this page
https://metraipolis.com/documento/dc_240b3dc68bcb

How to cite

Dreifarbenproblem — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Dreifarbenproblem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_240b3dc68bcb (Metraipolis archive dc_240b3dc68bcb, sha256 2ddb362b08c16ae1134dd2f03fbf5c65eaa2a604f3ed2fbc3c73283e0fa6bcbf)
BibTeX
@misc{dc240b3dc68bcb,
  title = {Dreifarbenproblem — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Dreifarbenproblem},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_240b3dc68bcb; sha256 2ddb362b08c16ae1134dd2f03fbf5c65eaa2a604f3ed2fbc3c73283e0fa6bcbf},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Dreifarbenproblem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. Eine Verallgemeinerung ist das Färbungsproblem. Bekannt ist auch eine als Landkartenfärbungsproblem bekannte Variante.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «Graphentheorie»).
Fonte: Wikipedia in tedesco, voce «Dreifarbenproblem» — https://de.wikipedia.org/wiki/Dreifarbenproblem
Wikidata Q1257771 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1257771
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Dreifarbenproblem?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 233371648, consultata il 2026-10-07T16:38:12.915Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0c689ec6a45a9de1eb7cb9a5b5e392db69427f46b402e550223554a3f7c7318d