Einfluß der Anzahl großer vollständiger Teilgraphen auf die Unabhängigkeitszahl von Graphen . - 34 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2011
Thomas Hofmeister und Hanno Lefmann haben gezeigt, dass für einen Graphen G ein Algorithmus existiert, der eine unabhängige Menge findet, die mindestens die Mächtigkeit c(n/d)ln(\beta*d) hat. Dabei ist \beta=min{1,\sqrt(n/s)}, c eine positive Konstante und s die Anzahl der Dreiecke, die G enthält. Dieser Algorithmus wird aufgegriffen und auf Graphen, welche vollständige Teilgraphen der Ordnung k, k>=3, enthalten, erweitert. Im zweiten Teil beschäftigen wir uns mit der Arbeit "On the Independence number of sparse graphs" von James B. Shearer und arbeiten diese Stück für Stück durch.
Lokale optimale Färbungen. - 20 S. Ilmenau : Techn. Univ., Bachlor-Arbeit, 2011
Sucht man zu einer Färbung eines Graphen eine alternative Färbung die weniger Farben verwendet, so steht man oft vor algorithmisch schwierigen Problemen. Vorallem über die Menge der umzufärbenden Ecken hat man keine Kontrolle. Um dies zu umgehen, besteht die Möglichkeit sich auf alternative Färbungen einzuschränken, die durch Anwendung lokaler Operationen hervorgehen. Diese Arbeit beschäftigt sich mit solchen Operationen und ihren Färbungsparametern.
Modellierung der Boltzmanngleichung auf diskreten Geschwindigkeitsgittern, numerische Umsetzung und Parallelisierung mithilfe von CUDA. - 116 S. Ilmenau : Techn. Univ., Masterarbeit, 2010
Im ersten Teil dieser Arbeit wurden die wichtigsten Eigenschaften der Boltzmanngleichung zusammengetragen. Daraufhin wurde die Boltzmanngleichung auf einem diskreten Geschwindigkeitsgitter modelliert und gezeigt, dass die modellierte Gleichung die gleichen Eigenschaften besitzt wie die originale Gleichung. In der zweiten Hälfte entwickelten wir einfache Algorithmen um die modellierte (diskrete) Boltzmanngleichung numerisch zu lösen. Diese Algorithmen wurden in C++ zur Berechnung auf einem CPU und parallelisiert in CUDA zur Berechnung auf einem GPU umgesetzt. Abschließend wurden einige Modellprobleme numerisch mithilfe der beiden Implementierungen gelöst und überprüft, ob eine parallelisierte Implementierung dieses Problems auf einem GPU sinnvoll ist.
Cycle lengths in cubic Hamiltonian graphs. - 39 S. : Ilmenau, Techn. Univ., Bachelor-Arbeit, 2010
We prove that the number of cycles of die rent length is at least linear in n, for S_ {1, a, b}-free, cubic Hamiltonian graphs of order n. Furthermore we prove linear, lower bounds for K_ {1, 3}, S_ {1, 1, 2}, or S_ {1, 2, 2}-free, cubic Hamiltonian graphs, that are best possible. These results corm a conjecture by Rautenbach in some special cases.
Die minimale Kantenbelastung in Raupen. - 35 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2010
Diese Arbeit beschäftigt sich mit der minimalen Kantenbelastung in Raupen gleicher Ordnung. Dabei wird versucht die maximale Kantenbelastung von einer Raupe G in einer Raupe T zu minimieren, indem beide nach dem gleichen Schema nummeriert werden und anschließend die Knoten mit gleicher Nummer bijektiv aufeinander abgebildet werden. Zum Vergleich werden auch noch zwei weitere Schemata getestet und es werden Aussagen über diese getroffen. Außerdem werden Gesetzmäßigkeiten für Spezialfälle der Raupe gezeigt. Schließlich werden noch obere Schranken für die Kantenbelastung vorgestellt.
Zur Unabhängigkeitszahl in Graphen. - 37 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2010
Die Unabhängigkeitszahl eines Graphen zu berechnen ist, wie sich im Laufe der Zeit herausgestellt hat, eine äußerst schwierige Aufgabe. Gerade deshalb sind möglichst genaue Abschätzungen jener von großem Interesse. In dieser Arbeit wird zum einen untersucht, wie sich die Unabhängigkeitszahl in einem n-eckigen Graphen, in welchen der Maximalgrad auf drei beschränkt ist, durch sum(f(di , ti), i=1..n) abschätzen lässt, wobei di die Gradzahl und ti die Dreieckszahl der jeweiligen Ecke i wiederspiegeln. Dabei ist die Funktion f rekursiv durch f(0,0) = 1 sowie f(d,t) = 1/(d+1) für t >=binomial(d,2) und f(d,t) = (1+(d^2-d-2t)f(d-1,t))/(d^2+1-2t) für t <binomial(d,2) gegeben. Zum anderen wird untersucht, welche Probleme auftreten, wenn anstelle des Maximalgrades die Dreieckszahl, eines jeden Eckpunktes in G, auf zwei beschränkt wird. Es wird ausführlich auf die dabei aufgetretenen Schwierigkeiten eingegangen.
Vergleich von Algorithmen zum Auffinden großer unabhängiger Mengen in Graphen. - 39 S. Ilmenau : Techn. Univ., Diplomarbeit, 2010
Das Finden unabhängiger Mengen in Graphen lässt sich mit Hilfe verschiedener Algorithmen realisieren. Die Arbeit beschäftigt sich mit einer speziellen Gruppe der Algorithmen. Bei diesen wird sukzessiv, mit einer bestimmten Auswahlregel, ein Punkt ausgewählt und dessen komplette abgeschlossene Nachbarschaft gelöscht. Jene Punkte bilden am Ende eine unabhängige Menge.Die Auswahlregeln setzen sich aus einer Kombination dreier Grundbedingungen zusammen: Erstens die Minimalvalenz. Die zweite Bedingung ist, dass die Anzahl der Kanten, die gelöscht werden, maximal ist. Die dritte Bedingung bewirkt, dass nach dem Löschen der abgeschlossenen Nachbarschaft ein Graph entsteht, der einen Punkt hat, dessen Valenz möglichst gering ist. Dass heißt, es wird der Punkt gesucht, bei dem die Minimalvalenz im Folgegraphen minimal ist. Zum Vergleich dient ein C++ Programm, dass die verschiedenen Ergebnisse ausgibt. Am Ende zeigt sich, dass Auswahlregeln, die mit der ersten Bedingung beginnen, die besten Ergebnisse liefern.
Dichtefunktionsbestimmung zur Korngrößenverteilung im Zement. - 86 S. Ilmenau : Techn. Univ., Diplomarbeit, 2010
Diese Arbeit dient der Unterstützung des DFG-geförderten Forschungsprojekts "Dynamische Korngrößenmessungen zur Verfolgung des Hydratationsverlaufs von Zementen im frühen Stadium". Schwerpunkt der Arbeit ist die Ermittlung einer Dichtefunktion, welche die gegebenen Messdaten hinreichend genau wiedergibt. Hierbei werden bereits bekannte Methoden aus der Verfahrenstechnik (Potenzverteilung, RRSB-Verteilung und Logarithmische Normalverteilung) untersucht und auch andere bisher nicht getestete Verteilungen (Weibullverteilung, gestutzte Verteilung, Mischverteilung) auf ihre Eignung geprüft. Für den Zeitpunkt t=0 Minuten ergibt sich keine zufriedenstellende Approximation der Messwerte. Für Zeiten größer t=0 Minuten können jedoch die Messwerte mittels einer vierkomponentigen Mischverteilung aus logarithmischen Normalverteilungen hinreichend genau angenähert werden.
Kantenfärbungen Gewichteter Multigraphen. - 51 S. Ilmenau : Techn. Univ., Diplomarbeit, 2010
Kantenfärbungen ungerichteter Graphen sind ein vielbehandeltes Problem der Graphentheorie. Die vorliegende Arbeit verallgemeinert diese Problemstellung auf fraktionelle f Kantenfärbungen. Der f chromatische Index eines Graphen wird dabei als binäres lineares Optimierungsproblem angesehen welches reell relaxiert wird. Daraus ergeben sich in natürlicher Weise Begriffe und Sätze, die ähnlich sind zu denen der klassischen Kantenfärbungen. Einige zentrale Resultate werden auf gebrochene Kantenfärbungen übertragen und der gebrochene f chromatische Index als effizient realisierbare Schranke in Verbindung mit dem f chromatischen Index gebracht.
Nonreversible homoclinic snaking in R 3. - 77 S. Ilmenau : Techn. Univ., Diplomarbeit, 2010
Im Kontext gewöhnlicher Differentialgleichungen bezeichnet "Homoclinic Snaking" ein bestimmtes Fortsetzungsszenario homokliner Orbits in einer Umgebung eines heteroklinen Zykel zwischen einem Gleichgewicht und einem periodischen Orbit. Die betrachteten Differentialgleichungen beschreiben häufig Gleichgewichte partieller Differentialgleichungen und sind oftmals reversibel und Hamiltonisch - besitzen also eine spezielle aufgeprägte Struktur. - In der vorliegenden Diplomarbeit werden zweiparametrige Familien gewöhnlicher Differentialgleichungen im R 3 betrachtet, die weder reversibel noch Hamiltonisch sind. Es wird angenommen, dass ein heterokliner Zykel zwischen einem hyperbolischen Gleichgewicht E und einem hyperbolischen periodischen Orbit [gamma] existiert. Weiter werden Voraussetzungen über das Schnittverhalten der stabilen und instabilen Mannigfaltigkeit von E und [gamma] gemacht. Unter diesen Annahmen wird das Fortsetzungsverhalten von 1-homoklinen Orbits zu E (das sind Orbits, die einmal entlang des originalen Zykels laufen) analytisch untersucht. Für solche Orbits wird "Homoclinic Snaking" nachgewiesen. Dabei wird gezeigt, dass das "Snakingverhalten" durch die Bifurkationen der heteroklinen Verbindungen zwischen E und [gamma] bestimmt wird.