Skip to content. | Skip to navigation

Personal tools

Sections

Terminologie

next up previous contents
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 tex2html_wrap_inline5254 ; 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ößegif, 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 tex2html_wrap_inline5272 , der 2-färbbar aber nicht 2-listenfärbbar ist, erkennt man, daß Ungleichheit vorliegen kann.

Zudem seien die folgenden Symbole vereinbart:
tex2html_wrap_inline5278 Knotenfärbbarkeitszahl
tex2html_wrap_inline5280 Kantenfärbbarkeitszahl
tex2html_wrap_inline5282 Knoten-Listenfärbbarkeitszahl
tex2html_wrap_inline5284 Kanten-Listenfärbbarkeitszahl
tex2html_wrap_inline5286 max. Knotengrad
tex2html_wrap_inline5288 max. Größe einer Clique

Def701

Die zusätzliche konstante Abweichung bewahrt an dieser Stelle u.a. vor Problemen mit OPT(I)=0.

Def707


next up previous contents
Next: Polynomiell lösbare Fälle Up: Komplexität des Problems Previous: Komplexität des Problems

(c) Martin Loehnertz 1999