Graphentheorie - Listenfärbung |
| 17.06.2007, 17:44 | Mattim | Auf diesen Beitrag antworten » | ||
Graphentheorie - Listenfärbung
brauche Hilfe bei der Definition der Listenfärbung eines Graphen. hier (seite 6) findet man eine definition von listenkantenfärbung (mir gehts eher um knotenfärbung, aber ist ja wurscht): http://www.fernuni-hagen.de/MATHEMATIK/D...rtebachelor.pdf das sieht ja eigentlich ganz einfahc aus.. aber irgendwie blick ich da nicht durch. also: jede ecke bekommt eine liste mit k elementen (farben). und das kleinste k für das g k-listenfärbbar ist ist die chromatische zahl. aber warum kann ich dann nicht einfach jeder ecke eine liste mit verschiedenen farben geben? dann wäre die listenchromatische zahl immer 1. das dass falsch ist, ist klar... aber.... warum 
hier ist auch noch an anschauliches bsp: http://www.rsiegfried.de/downloads/fhw/2...phen_Slides.pdf danke schon mal matti |
||||
| 19.06.2007, 12:58 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Graphentheorie - Listenfärbung
Das Problem ist der Begriff "k-listenkantenfärbbar". Die Bedingung, die dazu gestellt wird, sagt aus, dass für alle Familien von Listen eine Kantenfärbung existieren muss (so verstehe ich es). Bei nur einer Farbe kann ich die Listen so wählen, dass jede Liste eben nur genau dieselbe Farbe enthält, und dann geht es nicht. Grüße Abakus 
|
||||
| 19.06.2007, 16:10 | Mazze | Auf diesen Beitrag antworten » | ||
Kennst Du vielleicht den dazu äquivalenten Begriff der k-Kantenkonsistenz? Dieses wird in der KI verwendet um bei NP-vollständigen Problemen schon frühzeitig große Teile des Suchraums abzuschneiden. Zunächst hast Du einen fixen Satz Farben jetzt wählst Du Teilmengen dieser Farben aus, ein Graph ist k-kantenfärbar wenn Du jetzt jeder Kante eine Teilmenge zuordnen kannst so das für alle Elemente dieser Teilmenge für alle Nachbarkanten eine Farbe existiert so das die Färbungsbedingung nicht verletztt wird. Wie die Listen aussehen hängt im wesentlichen von der Struktur des Graphen ab. Aber Du kannst nur dann disjunkte Listen für jede Kante wählen wenn und dann wird das ganze trivial. |
||||
| 28.06.2007, 14:51 | Mattim | Auf diesen Beitrag antworten » | ||
Ach klar! 
dat muss für jede Liste färbbar sein. Das klingt nur logisch. K-kantenkonsitenz kommt mir nicht bekannt vor. Ich bleibe erst mal bei der Eckenfärbung :-) Aber die NP-completeness wartet auch noch auf mich... Da werd ich bestimmt noch mal Hilfe brauchen.Danke euch! Matti |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
