Eigenschaften chromatischer Polynome

Die Berechnung des 1912 von Birkhoff eingeführten chromatischen Polynoms eines Graphen stellt bekanntlich ein NP-vollständiges Problem dar. Dieses gilt somit erst recht für die Verallgemeinerung des chromatischen Polynoms zum bivariaten chromatischen Polynom nach Dohmen, Pönitz und Tittmann aus dem Jahre 2003. Eine von Averbouch, Godlin und Makowsky 2008 vorgestellte Rekursionsformel verursacht durch wiederholte Anwendung im Allgemeinen einen exponentiellen Rechenaufwand. Daher war das Ziel der vorliegenden Dissertation, Vereinfachungen zur Berechnung des bivariaten chromatischen Polynoms spezieller Graphentypen zu finden. Hierbei wurden folgende Resultate erzielt: Für Vereinigungen von Sternen, für vollständige Graphen, aus welchen die Kanten von Sternen mit paarweise voneinander verschiedenen Ecken gelöscht wurden, für spezielle Splitgraphen und für vollständig partite Graphen konnten rekursionsfreie Gleichungen zur Berechnung des bivariaten chromatischen Polynoms mit jeweils linear beschränkter Rechenzeit gefunden werden. Weiterhin werden Möglichkeiten der Reduktion allgemeiner Splitgraphen, bestimmter bipartiter Graphen sowie vollständig partiter Graphen vorgestellt. Bei letzteren erweist sich eine hierbei gefundene Rekursionsformel durch eine polynomiell beschränkte Laufzeit als effektive Methode. Ferner konnte in einem Abschnitt zu Trennern in Graphen gezeigt werden, dass der Spezialfall der trennenden Cliquen, welcher im univariaten Fall sehr einfach ist, im bivariaten Fall sehr komplexe Methoden erfordert. Ein Zusammenhang zwischen dem bivariaten chromatischen Polynom und dem Matchingpolynom wurde für vollständige Graphen, welchen die Kanten von Sternen mit paarweise voneinander verschiedenen Ecken entnommen wurden, sowie für Bicliquen hergestellt. Die vorliegende Dissertation liefert darüber hinaus auch einige Untersuchungen zum trivariaten chromatischen Polynom, welches auf White (2011) zurückgeht und eine weitere Verallgemeinerung des bivariaten chromatischen Polynoms darstellt. Hierbei konnte gezeigt werden, dass dessen Berechnung selbst für einfache Graphentypen schon recht kompliziert ist. Dieses trifft sogar dann noch zu, wenn man die einzelnen Koeffizienten als bivariate Polynome abspaltet und einzeln berechnet. Abschließend stellt die Arbeit zu vielen Resultaten Implementierungen mit dem Computeralgebrasystem Mathematica bereit, welche zahlreiche Möglichkeiten zu eigenständigen Versuchen bieten.

Experimentelle Untersuchung des Optimierungspotenzials in der kurzkohärenten Interferenzmikroskopie

Die vorliegende Arbeit befasst sich mit dem lateralen Auflösungsvermögen in der kurzkohärenten Interferenzmikroskopie. Das 3D-Auflösungsvermögen von Phasenobjekten ist im Gegensatz zu dem von Intensitätsobjekten stark nichtlinear und vom spezifischen Messverfahren abhängig. In diesem Zusammenhang sind systematische Messfehler von entscheidender Bedeutung. Für die kurzkohärente Interferenzmikroskopie ist das Überschwingen an Kanten von besonderem Belang, da sich der Effekt bei der Messung vieler technischer Oberflächen negativ auswirkt. Er entsteht durch die Überlagerung von Interferenzsignalen lateral benachbarter Objektpunkte von unterschiedlichen Höhenniveaus. Es wird an speziell für diesen Zweck entwickelten Messsystemen untersucht in wie weit dieser Effekt physikalisch reduziert werden kann und wie sich dies auf die laterale Auflösung auswirkt. An einem für den Einsatz in einer Nanomessmaschine optimierten Linnik-Interferometer wird die Justage eines solchen Systems erläutert. Der Sensor verfügt über die Option mit NUV-Licht betrieben zu werden, um die laterale Auflösung zu verbessern. Aufgrund des Einsatzzweckes ist der Arbeitsabstand relativ groß, was die laterale Auflösung einschränkt. Mit einem zweiten auf die Untersuchungen in dieser Arbeit optimierten Versuchsaufbau können die physikalischen Grenzen der kurzkohärenten Interferenzmikroskopie praktisch untersucht werden. Zu diesem Zweck ist der Aufbau mit einem Mikrospiegelarray ausgestattet, um hierüber variable konfokale Blenden zu schaffen. Mit diesem System wird erstmalig konfokale Mikroskopie mit Weißlichtinterferometrie kombiniert. Durch die optische Selektion der konfokalen Mikroskopie soll die Ursache für die Überschwinger an Kanten reduziert werden. Eine weitere Möglichkeit der Einflussnahme stellt die optionale Beleuchtung mit polarisiertem Licht dar, wodurch die laterale Auflösung weiter gesteigert werden kann. Zusätzlich kann auch dieser Aufbau mit kurzwelligem blauem Licht betrieben werden, um die laterale Auflösung zu optimieren. Die Messergebnisse, die mit diesen Versuchsaufbauten gemacht wurden, zeigen, dass im Gegensatz zu den in der derzeitigen Normung genutzten Modellen das Übertragungsverhalten in der Weißlichtinterferometrie bei der Messung von Phasenobjekten stark nichtlinear ist. Das laterale Auflösungsvermögen deckt sich je nach Auswerteverfahren recht gut mit dem von klassischen Mikroskopen bei der Wiedergabe von Intensitätsobjekten. Für die Untersuchungen wurde überwiegend ein Auflösungsnormal mit neun unterschiedlichen eindimensionalen Rechteckstrukturen verwendet, die eine Nominalhöhe im kritischen Bereich kleiner der Kohärenzlänge der verwendeten Lichtquelle aufweisen. Die Ergebnisse bestätigen sich aber auch an technischen Messobjekten aus der Praxis wie beispielsweise einer „digital video disc“.