Färbung (Graphentheorie)
Zuordnung einer Farbe zu jedem Element eines Graphen / aus Wikipedia, der freien encyclopedia
Liebe Wikiwand-AI, fassen wir uns kurz, indem wir einfach diese Schlüsselfragen beantworten:
Können Sie die wichtigsten Fakten und Statistiken dazu auflisten Graphenfärbung?
Fass diesen Artikel für einen 10-Jährigen zusammen
Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. Eine Verallgemeinerung ist der Begriff der Listenfärbung, d. i. die Zuordnung von „Listen“ verfügbarer Farben, wobei der Graph nun eine gültige Färbung aus diesen Listen erhalten soll. Des Weiteren gibt es die Totalfärbung, die sowohl Kantenfärbung als auch Knotenfärbung umfasst.
In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder „gültigen“ Färbungen (siehe unten), und versucht, Algorithmen zu entwickeln, die für einen vorgegebenen Graphen eine gültige Färbung mit möglichst wenigen Farben finden. Probleme aus der diskreten Mathematik, aber auch außermathematische Fragestellungen lassen sich manchmal in ein Färbungsproblem übersetzen, daher ist die Existenz oder Nichtexistenz solcher Algorithmen auch außerhalb der Graphentheorie von Interesse.