http://www.tu-ilmenau.de

Logo TU Ilmenau


Arbeitsgruppe
Diskrete Mathematik und Algebra


Ansprechpartner

Univ.-Prof. Dr. rer. nat. habil. Matthias Kriesell

Fachgebietsleiter

Telefon +49 3677 69-3633

E-Mail senden


Ihre Position

INHALTE

Studienabschlussarbeiten

Anzahl der Treffer: 68
Erstellt: Mon, 23 Oct 2017 07:05:44 +0200 in 0.0270 sec


Mohr, Samuel
Quadratic forms on graphs and maximum weighted induced subgraphs. - 35, 29 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014

Gegeben sei ein einfacher, endlicher, ungerichteter Graph G = (V, E) mit Eckenmenge V (G) und Kantenmenge E(G). Eine unabhängige Menge von G ist eine Teilmenge von V (G), in der je zwei Ecken nicht adjazent in G sind. Ein oft untersuchtes kombinatorisches Optimierungsproblem ist die Frage nach einer unabhängigen Menge maximaler Kardinalität. Angenommen, den Ecken sind Gewichte zugewiesen, dann ist ein weiteres Problem, eine unabhängige Menge maximalen Gewichtes zu finden. Es ist bekannt, dass die Entscheidungsversion dieser Probleme NP-vollständig ist, wodurch Untersuchungen von Schranken für das maximale Gewicht unabhängiger Mengen gerechtfertigt sind. Eine bekannte Schranke, auf dem diese Arbeit aufbaut, ist eine Veröffentlichung von Gibbons, Hearn, Pardalos und Ramana [1]. Diese Bachelorarbeit untersucht quadratische Formen auf Graphen, welche durch eine Arbeit von Motzkin und Straus [2] motiviert sind. Mit den Ergebnissen kann die Schranke von Gibbons und andere verbessert werden. Des Weiteren wird eine Verallgemeinerung der gewichteten Unabhängigkeit zu maximal gewichteten induzierten Untergraphen untersucht.


http://www.gbv.de/dms/ilmenau/abs/812867572mohr.txt
Heyder, Stefan
Chromatische Zahl und Spektrum von Graphen. - 51 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014

In dieser Bachelorarbeit wird der Zusammenhang zwischen den Eigenwerten und der chromatischen Zahl eines Graphen erarbeitet. Außerdem wird ein Zusammenhang zwischen den Eigenwerten eines Graphen und der Erdös-Faber Lovasz Vermutung hergestellt und eine stärkere Vermutung über die Eigenwerte und seine chromatische Zahl formuliert.


http://www.gbv.de/dms/ilmenau/abs/809004461heyde.txt
Storch, Patrick
k-kritische Hypergraphen deren Ordnung höchstens 2k-2 ist. - 34 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014

Ein Hypergraph heißt k-kritisch, wenn seine chromatische Zahl den Wert k hat, jedoch jeder echte Unterhypergraph mit weniger als k Farben färbbar ist. 1963 bewies T. Gallai, dass jeder k-kritische Graph mit einer Ordnung größer als 2k-2 zerlegbar ist, d.h. sein Komplement ist unzusammenhängend. In dieser Arbeit wird ein analoges Resultat für Hypergraphen bewiesen, sowie einige Klassen k-kritischer Hypergraphen untersucht. Desweiteren enthält die Arbeit eine vollständige Liste (mit Beweis) aller 3-kritischen Hypergraphen der Ordnung 5.


http://www.gbv.de/dms/ilmenau/abs/799260754storc.txt
Buchholz, Jens
Zur Struktur kritischer Graphen. - 34 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014

In dieser Arbeit wird eine Klasse von Graphen, nämlich die Klasse Cri*(k) charakterisiert. Sie umfasst alle k-kritischen Graphen, deren Nebenpunktegraph zusammenhängend ist und deren Hauptpunktegraph eine Färbung mit k-2 Farben besitzt. Weil die Charakterisierung bereits durch Sachs und Stiebitz erfolgt ist, wurden in dieser Arbeit neue und einfachere Beweise für die Charakterisierungssätze gefunden. Dazu wurde auf das Listenfärbungskonzept zurückgegriffen, welches eine Verallgemeinerung des Färbungskonzeptes darstellt, indem jeder Ecke v eine Farbe aus der zugehörigen Farbliste L(v) zugeordnet wird.


http://www.gbv.de/dms/ilmenau/abs/798699973buchh.txt
Dumke, Mandy
Über Geschlecht und längste Kreise von 3-fach zusammenhängenden, kubischen, bipartiten, nicht-hamiltonschen Graphen. - 35 S.
Ilmenau : Techn. Univ., Masterarbeit, 2014

Über Geschlecht und längste Kreise von 3-fach zusammenhängenden, kubischen, bipartiten, nicht-hamiltonschen Graphen.


http://www.gbv.de/dms/ilmenau/abs/79812105Xdumke.txt
Glock, Stefan
Edge-connectivity and Steiner tree packings in graphs. - 85 S.
Ilmenau : Techn. Univ., Masterarbeit, 2014

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.


http://www.gbv.de/dms/ilmenau/abs/797704620glock.txt
Langner, Kerstin
Chromatische Zahl, Ordnung und Maximalgrad von Graphen. - 73 S.
Ilmenau : Techn. Univ., Masterarbeit, 2014

Die Arbeit beschäftigt sich einerseits mit Graphen, deren chromatische Zahl nahe ihrer Ordnung liegt und zum anderen mit solchen, deren chromatische Zahl nahe ihres Maximalgrades liegt.


http://www.gbv.de/dms/ilmenau/abs/79742167Xlangn.txt
Fischer, Steffen
Färbungskritische Graphen mit vollständigem Hauptpunktegraph. - 35 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014

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.


Diegnitz, Sandro
Fast isometrische Einbettung von Graphmetriken in die euklidische Ebene. - 26 S.
Ilmenau : Techn. Univ., Masterarbeit, 2014

In der Arbeit wird gezeigt, dass es möglich ist einen unendlichen, schlichten, zusammenhängenden Graphen so in die Ebene abzubilden, dass er der Einbettungseigenschaft genügt. Der Graph bzw. die Abbildung, welche den Graphen in die Ebene einbettet muss dafür die epsilon-Netz Eigenschaft haben. Außerdem wird der Begriff der r-Kontraktion benutzt um die gewünschten Resultate zu erzielen. Zudem wird gezeigt, dass das Resultat für alle durch Normen induzierte Metriken gilt.


http://www.gbv.de/dms/ilmenau/abs/783127529diegn.txt
Schierwagen, Thomas
Stochastische Stabilität am Beispiel eines zellulären Automaten. - 55 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2013

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.


http://www.gbv.de/dms/ilmenau/abs/777347032schie.txt