Regensburg 2000 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe
DY: Dynamik und Statistische Physik
DY 46: POSTER II
DY 46.60: Poster
Donnerstag, 30. März 2000, 15:00–18:00, D
Wieviele Museumswächter braucht man? — •Alexander Hartmann und Martin Weigt — Institut für theor. Physik, Bunsenstr. 9, 37073 Göttingen
Das ist das sog. Knoten-Überdeckungs-Problem von Graphen, eines der fundamentalen NP-vollständigen Probleme aus dem Bereich der theoretischen Informatik. Man überdeckt einige Knoten eines Graphen, so dass jede Kante mindestens einen überdeckten Knoten berührt.
Im Falle von Zufallsgraphen mit N Knoten und cN Kanten finden wir einen kritischen Wert xc(c)N für die Größe der kleinsten Überdeckungsmenge: Im thermodynamischen Limes existieren für 1 > x > xc(c) mit Wahrscheinlichkeit Eins exponentiell viele Überdeckungen der Größe xN, während die Wahrscheinlichkeit der Existenz einer Überdeckung aus weniger als xc(c)N Knoten im thermodynamischen Limes gegen Null strebt. Am selben Punkt xc(c) finden wir einen Übergang in der typischen algorithmischen Komplexität des Problems, die von in N linearen zu exponentiellen Lösungszeiten springt. Neben numerischen Simulationen des Modells beschreiben wir die Lösungen analytisch im Rahmen eines variationellen Replikazugangs. Die Ergebnisse beider Methoden liegen in guter Übereinstimmung.