Studienabschlussarbeiten am Institut

Der zentrale Gegenstand dieser Masterarbeit ist Kriesells Vermutung. Es sei G ein Graph und A eine Menge von Ecken, den sogenannten Terminalen. Ein A-Steinerbaum ist ein Teilgraph von G, welcher ein Baum ist und alle Terminale enthält. Das Packen von Steinerbäumen in Graphen ist ein kompliziertes Problem mit vielen Anwendungen, zum Beispiel im VLSI-Design und Broadcasting. Aus theoretischer Sicht ist es von Interesse, hinreichende Bedingungen für die Existenz einer bestimmten Anzahl kantendisjunkter Steinerbäume zu kennen. Kriesell vermutete, wenn jeder Schnitt in G, der zwei Ecken aus A trennt, mindestens 2k Kanten enthält, dann existieren k kantendisjunkte A-Steinerbäume. Im Blickpunkt dieser Arbeit steht der aktuellste Forschungsbeitrag zu dieser noch offenen Vermutung. Außerdem wird ein neues Resultat über den Fall weniger Nichtterminale bewiesen. Insbesondere ist Kriesells Vermutung wahr, wenn es höchstens fünf Nichtterminale gibt.

Ziel dieser Arbeit ist die Analyse des Einflusses diverser Parameter auf die makroskopischen Lasergleichungen. Hierzu bedarf es einer numerischen Beschreibung und einer programmiertechnischen Umsetzung, welche ebenfalls durchgeführt werden sollen. Um ein Verständnis sowohl der physikalischen als auch der mathematisch-numerischen Grundlagen zu gewährleisten, werden beide detailliert vorgestellt. Zunächst soll hierbei die semiklassische Theorie des Laserlichts wiedergegeben werden, welche die Maxwellsche Theorie des Elektromagnetismus mit einem quantenmechanischen Zweiniveausystem verbindet. Dies führt letztlich auf drei gekoppelte Differentialgleichungen, welche die physikalischen Größen elektrische Feldstärke, Polarisation und Besetzungsinversion miteinander verknüpfen. Direkt anschließend wird die numerische Theorie der gewöhnlichen und partiellen Differentialgleichungen ausgearbeitet. Hierbei werden im Rahmen der gewöhnlichen Differentialgleichungen zunächst verschiedene Einschrittverfahren und darauf folgend explizite und implizite Mehrschrittverfahren vorgestellt. Die numerische Theorie der partiellen Differentialgleichungen beschränkt sich auf die Methode der finiten Differenzen, wobei explizite, implizite und gemischte Verfahren an den Beispielen der Wellen- und der Diffusionsgleichung vorgestellt werden. Zudem werden die theoretischen Konzepte der Stabilitätsuntersuchung sowie verschiedene Stabilitätskriterien angegeben. Darauf aufbauend wird die numerische Umsetzung der Lasergleichungen beschrieben. Es wird darauf Wert gelegt, die Herangehens- und Arbeitsweise des Autors aufzuzeigen, um somit ein einfacheres Nachvollziehen der Gedankengänge zu ermöglichen. Aus diesem Grund wird zunächst die physikalische Vorbereitung - das Reskalieren der Gleichungen behandelt. Dies ermöglicht eine einheitenlose und somit mathematisch-numerisch stark vereinfachte Handhabung der Gleichung. Anschließend folgt die numerische Stabilitätsuntersuchung verschiedener Verfahren, angewandt auf die zunächst noch entkoppelt partielle Lasergleichung. Diese Untersuchung soll ebenfalls die Arbeitsweise des Autors in den Vordergrund rücken und wird deshalb nicht in der strengen mathematischen Beweisstruktur wiedergegeben. Vielmehr werden die Stabilitätsbedingungen - der formalen Beweisrichtung entgegengesetzt - hergeleitet, wodurch die Nachvollziehbarkeit und der Lesefluss erhöht werden. Nach der physikalischen Interpretation der Werte der entkoppelten Gleichung werden abschließend die drei gekoppelten Gleichungen computertechnisch umgesetzt. Von den mannigfaltigen untersuchenswerten Phänomenen werden einerseits ein assymetrisches Auftreten der Besetzungsinversion und andererseits die Abhängigkeit des Laserprozesses von Dämpfungstermen untersucht.

Das Ziel der Bachelorarbeit ist die Entwicklung eines Kopositivitätstestes mit der [alpha] bb-Methode. Das Testen einer Matrix auf Kopositivität ist zu einem wichtigen Forschungsgebiet geworden, weil sich viele Optimierungsprobleme gerade aus der gemischt-ganzzahligen und quadratischen Optimierung auf lineare Optimierungsprobleme über dem Kegel der kopositiven Matrizen umformulieren lassen. Die [alpha] bb-Methode ist ein Verfahren aus der globalen Optimierung, das sich auf eine sehr große Klasse von Funktionen anwenden lässt. In der Arbeit wird die [alpha] bb-Methode allgemein vorgestellt, auf dieser Basis ein Kopositivitätstest erstellt und die Ergebnisse mit denen anderer Verfahren verglichen.

Die Arbeit ist in drei Kapitel unterteilt. Zu Beginn erfolgt die Erläuterung, der für die Arbeit wichtigen Begriffe und Bezeichnungen für Graphen. Unter anderem werden Färbung und auch die für die Beweise wichtige Listenfärbung erklärt. Der letzte Abschnitt dieses Kapitels beschäftigt sich dann mit der Klasse der kritischen Graphen. Daran anschließend befasst sich das zweite Kapitel mit den im Mittelpunkt dieser Arbeit liegenden Sätzen 2.2 und 2.4 sowie ihren neuen Beweisen. Diesbezüglich behandelt das Kapitel zwei Konstruktionsmöglichkeiten, welche aus gegebenen Haupt- und Nebenpunktegraphen einen k-kritischen Graphen konstruieren. Am Ende fügt sich noch ein kurzes Fazit an.

Die vorliegende Arbeit beschäftigt sich mit der Stabilität von Zuständen unter stochastischen Störungen am Beispiel eines zellulären Automaten auf einem periodischen Gitter mit dem Ising-Modell ähnlichen Übergangsregeln. Als Modell für diesen Automaten dienen Markowketten und deren Darstellung als Übergangsgraphen. Unter der Verwendung eines Satzes von Peyton Young kann gezeigt werden, dass sich als stochastisch stabile Zustände Streifen auf dem Gitter ergeben, was in Übereinstimmung mit der Ausbildung langlebiger Streifenzustände in entsprechenden Computersimulationen ist.