https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Dreifarbenproblem 2026-05-28T23:45:40Z Versionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale Kopie MediaWiki 1.43.8 https://wiki-de.moshellshocker.dns64.de/index.php?title=Dreifarbenproblem&diff=105763&oldid=prev 2023-05-02T11:45:26Z

<p></p> <p><b>Neue Seite</b></p><div>Das &#039;&#039;&#039;Dreifarbenproblem&#039;&#039;&#039; ist ein [[Entscheidbar|Entscheidungsproblem]] aus der [[Graphentheorie]]. Gefragt ist, ob die [[Knoten (Graphentheorie)|Knoten]] eines [[einfacher Graph|einfachen Graphen]] so mit drei Farben einfärbbar sind, dass zueinander [[Adjazenz (Graphentheorie)|benachbarte]] Knoten unterschiedliche Farben haben. Das Problem ist [[NP-vollständig]].&lt;ref&gt;{{Internetquelle | url=https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf | titel=Theoretische Grundlagen der Informatik | titelerg=Vorlaufiges Skript zur Vorlesung | autor=[[Dorothea Wagner]] | seiten=65 | datum= | zugriff=2012-02-18 | format=PDF; 874&amp;nbsp;kB }}&lt;/ref&gt;<br /> <br /> Eine Verallgemeinerung ist das [[Färbungsproblem]]. Bekannt ist auch eine als [[Landkartenfärbungsproblem]] bekannte Variante.<br /> <br /> == Einzelnachweise ==<br /> &lt;references/&gt;<br /> <br /> <br /> [[Kategorie:Problem (Graphentheorie)]]<br /> [[Kategorie:Komplexitätstheorie]]</div>

imported>Qwertzu111111