Terminologie
Next: Polynomiell lösbare Fälle Up: Komplexität des Problems Previous: Komplexität des Problems
Terminologie
Da überwiegend Reduktionen auf graphentheoretische Probleme vorgenommen werden, bedient sich dieser Abschnitt in verstärktem Maße dem zugehörigen Begriffsapparat. Die hier definierten Ausdrücke werden auch in Kapitel 4 und in Abschnitt 6 verwandt, weshalb die Beschreibung etwas umfangreicher ausfällt, als eigentlich notwendig. Die hier eingeführte Terminologie folgt im wesentlichen der von DIESTEL [Die96], wobei im folgenden kurz auf einige weniger geläufige Begriffe eingegangen wird.
- Linegraph:
- Zu einem Graphen (Hypergraphen) G ist L(G)=(E,K) mit E=E(V) und ; d.h. die Ecken von L(G) repräsentieren die Kanten von G, und zwei Ecken von L(G) sind genau dann verbunden, wenn die entsprechenden Kanten einen Knoten gemeinsam haben.
- Cliquengraph:
- Gegeben ein Graph («Hypergraph) G repräsentiert der Cliquengraph CL(G) jede Clique von G durch einen Knoten, und zwei Cliquen sind genau dann miteinander verbunden, wenn sie einen Knoten in G gemeinsam haben.
- Listenfärbung:
- Zu jedem zu färbenden Objekt wird eine Liste von k Farben assoziiert, die für die
Färbung verwendet werden dürfen. Die minimale Listengröße, die unabhängig von der Wahl der Farben in den Listen
eine Färbung zuläßt, wird als Listenfärbbarkeitszahl bezeichnet. Diese ist größer-gleich der Färbbarkeitszahl
und im Fall des , der 2-färbbar aber nicht 2-listenfärbbar ist, erkennt man, daß Ungleichheit vorliegen kann.
Knotenfärbbarkeitszahl | |
Kantenfärbbarkeitszahl | |
Knoten-Listenfärbbarkeitszahl | |
Kanten-Listenfärbbarkeitszahl | |
max. Knotengrad | |
max. Größe einer Clique |
Die zusätzliche konstante Abweichung bewahrt an dieser Stelle u.a. vor Problemen mit OPT(I)=0.
Next: Polynomiell lösbare Fälle Up: Komplexität des Problems Previous: Komplexität des Problems (c) Martin Loehnertz 1999