Graphenfärbung - Neue Knoten hinzufügen |
| 20.08.2008, 16:51 | Chris_gr | Auf diesen Beitrag antworten » | ||
| Graphenfärbung - Neue Knoten hinzufügen ich habe folgendes Problem: Ich habe einen gültig gefärbten Graphen (Knotenfärbung) und will einen weiteren Knoten hinzufügen. Ich schaue mir den Graphen an und ermittle eine Menge an Farben die möglich wären... Nach welchen Kriterien wähle ich die Farbe am besten aus? 1. Die Farbe die am seltensten verwendet wurde? 2. Die Farbe die am häufigsten verwendet wurde? 3. Eine zufällig Farbe 4. Andere Strategie? GIbt es für sowas evtl. irgendwelche statistischen Auswertungen in der Graphentheorie? Danke schonmal für eure Hilfe! Chris |
||||
| 21.08.2008, 07:31 | Mazze | Auf diesen Beitrag antworten » | ||
Eine Graphenfärbung ist dann gültig wenn für jeden Knoten v kein adjazenter Knoten w mit der selben Farbe existiert. Wenn ein neuer Knoten w hinzukommt, musst Du Dir also alle zu w adjazenten Knoten anschauen, und alle Farben streichen die bereits vergeben sind. Aus der Restmenge kannst Du dann auswählen. Falls mehrere Farben übrig bleiben würde ich zufällig wählen, es gibt aber vielleicht noch bessere Möglichkeiten. Fakt ist aber, das man zu jedem gefärbten Graphen, mit mehr Knoten als Farben, immer einen Knoten hinzufügen kann, so dass der Graph nicht mehr färbbar ist. Nämlich Du fügst einen Knoten hinzu mit mehr adjazenten Knoten als es Farben gibt. |
||||
| 21.08.2008, 08:48 | Chris_gr | Auf diesen Beitrag antworten » | ||
Hallo Mazze, wie man einen Graphen gültig färbt war mir klar 
Die Frage war nur, wenn ich mehrere Farben zur Auswahl habe, welche nehme ich dann.... Bei zufällig habe ich irgendwie ein schlechtes Gefühl, dass ich aber nicht beweisen kann. Meine überlegung war zwischenzeitlich so, dass ich vll. am besten eine Farbei nehme die in maximal zwei Knoten Abstand vorkommt um so die Menge der verwendeten Farben möglichst gering zu halten... |
||||
| 21.08.2008, 08:57 | AD | Auf diesen Beitrag antworten » | ||
Ich kann mir dieses "schlechte Gefühl" nur so erklären, dass du bei der Färbung dieses neuen Knotens mehr beabsichtigst als nur eine gültige Färbung des nunmehr erweiterten Graphen: Dass vielleicht die Chance auf weiter mögliche gültige Färbungen bei noch mehr angefügten Knoten möglichst hoch ist? Andernfalls ist es doch wirklich völlig egal, welche der noch möglichen Farben du nimmst! Das solltest du dann aber so klar und deutlich dazusagen. Und das nützt auch nur dann was, wenn man über die zukünftig angefügten Knoten genauere Infos hat: D.h., welche Kanten werden da genau hinzugefügt? |
||||
| 21.08.2008, 09:06 | Chris_gr | Auf diesen Beitrag antworten » | ||
Hi Artur, das mit den eventuellen weiteren gültigen Färbungen war mir bisher nicht so klar... aber genau das ist das was ich wohl unbewusst im Hinterkopf hatte. Über mögliche und unmögliche Kanten wird aber keine Aussage gemacht. Aber danke für deinen Einwurf. Jetzt sitze ich schon an einer verbesserten Version des Problems.. mal sehen ob sich daraus was ableiten lässt: 1. Gültige Färbung vorhanden 2. Es werden succesive neue Knoten hinzugefügt 3. Die Anzahl der verwendeten Farben soll sich möglichst lange nicht erhöhen 4. Wie wähle ich unter den o.g. Gesichtspunkten möglichst schlau eine Farbe aus dem Pool der möglichen Farben. Mal schauen ob ich damit weiterkomme oder evtl. Im Netz was finde... Ein Komilitone meinte vorher: Entferne einfach so lange Knoten bis das Ding planar ist... schöne Idee leider nicht umsetzbar! Danke für eure Anregungen! |
||||
| 01.09.2008, 16:04 | Tobias | Auf diesen Beitrag antworten » | ||
Was du suchst ist ein Online-Algorithmus. Online-Algorithmen haben stets nur lokales Wissen. Die Eingaben aus der Zukunft (hier: Knoten und Kanten) sind ihnen, im Gegensatz zu Offline-Algorithmen, die die gesamte Eingabe (gesamten Graph) zu Beginn erhalten, noch unbekannt. Die Güte eines solchen Algortihmus misst man über den Competitve-Faktor, der das Verhältnis zwischen den Kosten des Online-Algos und der optimalen Kosten auf einer Worst-Case-Eingabe beschreibt. Benutzt ein Online-Algo deterministische Heuristiken, d.h. er wählt z.B. stets die Farbe, die am seltensten vorkommt, so lässt sich meist eine Eingabesequenz erstellen, die einen schlechten Competitve-Faktor zur Folge hat. Aus diesem Grund haben nicht selten probabilistische Ansätze bessere erwartete Competitve-Faktoren als deterministische. Zusammengefasst: Aus meiner Erfahrung heraus würde ich, bei unbekannter Zukunft, stets das zufällige Auswählen als eine gute Strategie ansehen und hätte dabei kein ungutes Gefühl. Ansonsten kennst du bestimmt die Greedy-Färbung: http://www.imn.htwk-leipzig.de/~waldmann...aph/node22.html |
||||
| Anzeige | ||||
|
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
