Lehre

Lehrveranstaltungen im Wintersemester 2021/2022
  • Diskrete Mathematik
  • Graphen und Algorithmen
  • Grundlagen und Diskrete Strukturen
  • Höhere Algebra
Studentinnen und Studenten hören eine Vorlesung im Hörsaal, zwei Laptops sind zu sehenTU Ilmenau / Michael Reichel (ari)

Weitere Informationen

Moodle


Sprechzeiten:

Studienabschlussarbeiten

Anzahl der Treffer: 58
Erstellt: Tue, 23 Apr 2024 23:08:08 +0200 in 0.0512 sec


Orlob, Tilman;
Charakterisierung der Baumweite eines Graphen durch Graphsuche. - Ilmenau. - 21 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2023

Das Konzept der Baumweite ist eines der weniger intuitiven Konzepte in der Graphentheorie. Deswegen ist es durchaus nützlich, sich alternative Charakterisierungen dieser Größe anzusehen. Zu diesem Zweck soll das Suchen auf Graphen mit bestimmten Voraussetzungen dienen. Ziel dieser Arbeit ist es, einen kurzen Überblick über die Geschichte der Graphsuche zu geben, die Voraussetzungen für die Graphsuche zu definieren, so dass ein Zusammenhang zur Baumweite hergestellt wird, und einen Beweis für diesen Zusammenhang darzustellen.



Dahlke, Jonathan Christoph;
On the Hamiltonicity of 5-regular Line Graphs with Additional Properties. - Ilmenau. - 26 Seiten
Technische Universität Ilmenau, Masterarbeit 2023

In der vorliegenden Masterarbeit wird eine Abschwächung einer Vermutung von Thomassen gezeigt. Thomassen hatte vermutet, dass 4-zusammenhängende Kantengraphen hamiltonsch sind - das ist, sie besitzen einen aufspannenden Kreis. Hier zeigen wir, dass, mit einer wesentlich einschränkenden Bedingung an Ecken des Grades 3 im Urbild des Kantengraphen, 5-reguläre, 4-zusammenhängende Kantengraphen hamiltonsch sind. Weiterhin gibt es eine Vermutung, die von L. Lovász im Jahr 1969 aufgestellt wurde. Diese besagt, dass - bis auf wenige Ausnahmen - alle vertex-transitiven Graphen hamiltonsch sind, wobei man einen Graphen vertex-transitiv nennt, wenn seine Automorphismengruppe transitiv auf den Ecken des Graphen wirkt. Durch Ausnutzen des obigen Resultates und nach Klassifikation der 5-regulären vertex-transitiven Kantengraphen können wir dann zeigen, dass vertex-transitive, 5-reguläre Kantengraphen, in deren Urbild Kreise der Länge 4 enthalten sind, hamiltonsch sind.Abschließend fokussieren wir uns auf ein Resultat von Jaeger, der 1979 eine sehr nützliche Äquivalenz zeigte, in der er die Kantenmengen, die innerhalbe eines gegebenen Graphen zu einem eulerschen Teilgraphen erweitert werden können, klassifizierte. Dies nutzen wir, um Resultate, die bereits nützlich dafür waren, Abschwächungen von Thomassens Vermutung zu zeigen, zu verschärfen.



Junghans, Elisa;
Minimalgradzerlegungen von Kreispotenzen. - Ilmenau. - 35 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2022

Das Ziel dieser Arbeit ist es, herauszufinden für welche s und t es unendlich viele (s+t)-zusammenhängende Graphen gibt, die keine (s,t)-Zerlegung besitzen. Zu diesem Zweck wurden Potenzen von Kreisen auf Existenz solcher Zerlegungen untersucht. Dabei ist eine Zerlegung hier ein Tupel induzierter, disjunkter Teilgraphen, sodass jede Ecke des Graphen in einem der beiden Teile enthalten ist und eine (s,t)-Zerlegung eine solche Zerlegung, sodass der eine Teil Minimalgrad s und der andere Minimalgrad t hat. Dabei wurden die Fälle s = t, s = 1, s = 2 sowie s = 3 vollständig analysiert. Für allgemeine s und t konnten hinreichende Kriterien für die Existenz von (s,t)-Zerlegungen von Kreispotenzen hergeleitet werden, welche nicht immer erfüllt seien können. Dadurch wurden unendlich viele (s+t)-zusammenhängende Graphen ohne eine (s,t)-Zerlegung gefunden. Zusätzlich wurden auch notwendige Kriterien gefunden.



Dahlke, Jonathan Christoph;
Verbundene perfekte Matchings in Graphen mit spezieller Kempe-Färbung. - Ilmenau. - 21 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2022

In dieser Arbeit wird eine Verschärfung eines Spezialfalls der Hadwiger-Vermutung gelöst. Es werden Graphen mit einer Kempe-Färbung, das ist eine Färbung, in der der von je zwei Farbklassen induzierte Teilgraph zusammenhängend ist, betrachtet und unter diesen solche, in denen alle Farbklassen die Größe zwei haben. Unter dieser Voraussetzung konnte gezeigt werden, dass, wenn der Graph nicht allzu viele nicht verbundene Kanten besitzt, er ein perfektes Matching, in dem die Kanten paarweise verbunden sind, haben muss. Dieses verbundene perfekte Matching stellt dann einen vollständigen Minor dar, der so viele Taschen hat, wie die Färbung Farbklassen.



Schulz, Nicolas;
Zur Zerlegung von Ordnungen mit totalen Ordnungserweiterungen. - Ilmenau. - 51 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2021

Mit der Ordnungsdimension haben Dushnik und Miller 1941 ein Konzept entwickelt, das es ermöglicht, die Komplexität endlicher partieller Ordnungen abzuschätzen. In dieser Arbeit entwickeln wir eine alternative Methode zur Darstellung derartiger Ordnungen durch totale Ordnungserweiterungen, die - im Unterschied zum vorherigen Ansatz - zusätzliche Informationen über die Minima beliebiger Teilmengen erhalten. Wir beschäftigen uns dabei zunächst mit der Frage, wie groß derartige Zerlegungen wenigstens sein müssen und leiten anschließend konstruktive Zerlegungsalgorithmen her, die wir an geeigneten Beispielen testen.



Krone, Maximilian;
Erzeugung von Mengensystemen mit Durchschnitten und Vereinigungen. - Ilmenau. - 28 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2021

Die Arbeit untersucht unter anderem folgende Darstellungs- und Konstruktionsprobleme: Gegeben sind Mengensysteme X und A über einer gemeinsamen Grundmenge. Ist es möglich, die Mengen aus X mit beliebigen Durchschnitten und Vereinigungen aus den Mengen aus A als Ausdruck darzustellen bzw. in Form einer Konstruktionsvorschrift zu konstruieren? Dieses Problem ist in polynomieller Zeit entscheidbar. Für eine Modifikation des Problems sei weiter eine Familie von n [Element von] N Mengenoperationen gegeben, welche in der Darstellung bzw. Konstruktion zusätzlich zu Durchschnitten und Vereinigungen (einmalig) verwendet werden dürfen. Auch dieses Problem ist für eine Klasse von Mengenoperationen, zu der insbesondere alle zweistelligen sowie die Komplementbildung gehören, in polynomieller Zeit entscheidbar. Für n = 3 viele hinreichend komplexe, aber feste Mengenoperationen ist das Problem dagegen NP-vollständig. Dies bleibt bestehen, wenn wir statt der Verwendung von drei Mengenoperationen drei frei wählbare Mengen zulassen. Die zugehörige Entscheidungsfrage ist allgemein: Gibt es ein Mengensystem S aus n Mengen so, dass die Mengen aus X mit beliebigen Durchschnitten und Vereinigungen aus den Mengen aus A [Vereinigungsmenge] S konstruierbar bzw. als Ausdruck darstellbar sind? Eine Verallgemeinerung dieses Problems ist äquivalent zum folgenden Entscheidungsproblem für einen gegebenen Digraphen D = (V, E) und n [Element von] N: Gibt es n Teilmengen von V (Schnitte in D) so, dass für jede Kante xy [Element von] E eine der Mengen die Ecke x, jedoch nicht die Ecke y enthält? Dies wiederum ist äquivalent zu einer Zerlegung der Kantenmenge E in n Mengen, welche nicht zugleich Kanten xy und yz für irgendwelche Ecken x, y, z enthalten. Auch diese Probleme sind NP-vollständig, insbesondere für azyklische Digraphen und n = 3.



Möller, Florian;
Analyse eines den 4-Zusammenhang zertifizierenden Algorithmus. - Ilmenau : Universitätsbibliothek. - 1 Online-Ressource (42 Seiten)
Technische Universität Ilmenau, Masterarbeit 2020

Zertifikate sind in der Graphentheorie hilfreich um Eigenschaften von Graphen schnell nachweisen zu können. Elmasry, Mehlhorn und Schmidt setzten sich mit 3-Zusammenhang in Hamiltongraphen auseinander und entwickelten ein Zertifikat, welches mittels eines Algorithmus in Laufzeit O(m + n) verifiziert, ob ein Hamiltongraph 3-zusammenhängend ist. Schmidt hat dies 2010 auf allgemeine Graphen mithilfe der Barnett-Grünbaum-Pfade erweitert. Somit gibt es ein Zertifikat für 3-Zusammenhang in Graphen. In dieser Arbeit beschäftigt uns die Frage: Kann man auch ein Zertifikat für 4-Zusammenhang aufstellen? Dabei stützen wir uns auf die Resultate der Arbeiten von Martinov und von Mader bezüglich 4-zusammenhängender Graphen. Ziel ist es, einen vorgegebenen Graphen G aus einem kontraktionskritischen, 4-zusammenhängenden Ausgangsgraphen mittels einer Sequenz den 4-Zusammenhang erhaltenden Kantenexpansionen zu rekonstruieren.



https://doi.org/10.22032/dbt.45610
Eckenpartitionszahlen. - Ilmenau. - 46 Seiten
Technische Universität Ilmenau, Masterarbeit 2020

Ein wichtiger Teil der Graphentheorie sind bis heute Färbungsprobleme. Das klassische Färbungsproblem ist ein kombinatorisches Optimierungsproblem. Im Mittelpunkt steht dabei die Untersuchung der chromatische Zahl. Erweitern wir dieses Konzept und fordern, dass jede Farbklasse streng-t-degeneriert ist, so nennen wir die minimale Anzahl benötigter Farben die Eckenpartitionszahl. Wir zeigen grundlegende Eigenschaften kritischer Graphen bezüglich der Eckenpartitionszahl und untersuchen, wann ein Graph in zwei disjunkte Teilgraphen zerlegt werden kann, wobei jede Ecke des ersten Teilgraphen mit jeder Ecke des zweiten Teilgraphen durch genau t Kanten verbunden wird. Des Weiteren untersuchen wir die minimale Anzahl Kanten eines kritischen Graphen bezüglich der Eckenpartitionszahl. Außerdem erweitern wir das Strong Perfect Graph Theorem auf die Eckenpartitionszahl mit t=2.



Fanselow, Niklas;
Paths in a ball. - Ilmenau. - 40 Seiten
Technische Universität Ilmenau, Masterarbeit 2019

Die vorliegende Abschlussarbeit befasst sich mit einem Problem, welches durch einen Vortrag von P. Braun über die wissenschaftliche Arbeit "Unsafe Point Avoidance in Linear State Feedback". Um die Nichtexistenz einer stetigen Zustandsrückführung als Lösung eines linearen, zeitinvarianten, stabilisierbaren Systems mit der Eigenschaft, dass eine vorgegebene Menge von nicht sicheren Punkten durch die Lösungen des Systems vermieden wird, zu erklären, wurde im genannten Vortrag die folgende Behauptung aufgestellt. Betrachten wir eine Familie von Wegen im Einheitsball, welche stetig von ihrem Anfangspunkt auf der Einheitssphäre abhängen und in den Ursprung laufen, so gibt es für jeden Punkt des Einheitsballs einen Weg, der diesen Punkt in seinem Bild enthält. Diese Fragestellung, formuliert für den endlich-dimensionalen euklidischen Raum, wird in vorliegender Abschlussarbeit untersucht. Zunächst wird eine Funktion F konstruiert, welche ermöglicht, alle diese Wege zugleich zu betrachten. Unter der zusätzlichen Voraussetzung der Injektivität von F, stellt das Bild von F für einen festgehaltenen Zeitparameter topologische Sphären da. Basierend auf dem Jordan-Brouwer Separationssatz und der Gebietsinvarianz von Brouwer wird für diese Voraussetzungen ein Beweis der Surjektivität von F geführt. Allerdings konnte die zugrundeliegende Fragestellung in vorliegender Arbeit nicht beantwortet werden. Ein weiteres Hauptresultat dieser Arbeit stellt eine äquivalente Beziehung zwischen der Sujektivität von F und der Separationseigenschaft dar. Abschließend wird gezeigt, dass die Homöomorphie-Eigenschaft der Innen- und Außengebiete der durch F erhaltenen topologischen Sphären in diesem Spezialfall erhalten bleibt, während der Satz von Jordan-Schoenflies nicht auf höhere Dimensionen verallgemeinert werden kann, wie beispielsweise Alexander mittels der Konstruktion der Alexanderschen gehörnten Sphären bewies.



Erweitertes Online GNSS-Matching - Verbesserung der Abgleichsmechanismen zwischen digitalen Karten und per GNSS erfassten Positionsdaten. - Ilmenau. - 95 Seiten
Technische Universität Ilmenau, Masterarbeit 2018

In dieser Arbeit wird ein kurzer Überblick über die Funktionsweise von globalen Navigationssystemen (GNSS) und den verwendeten Positionsangaben gegeben. Mittels der GNSS kann ein GNSS-Empfänger seinen Standort in Relation zur Erde bestimmen. Ein Map Matching Verfahren bringt diese fehlerbehafteten Standortdaten in Relation zu einem gegebenen Straßennetz (Straßenkarte) und versucht die korrekte Position des Empfängers darauf zu ermitteln. Map Matching Algorithmen, welche sofort die aktuelle Position bestimmen ohne zukünftige GNSS-Werte zu haben, werden als online Map Matching Algorithmen bezeichnet. In dieser Arbeit wurde gezeigt, inwiefern sich Hidden Markov Modelle als Basis für ein solchen online Map Matching Algorithmus eignen. Hierfür wurde ein einfaches Straßenmodell erstellt, auf welches fehlerbehaftete Standortdaten simuliert wurden. Für dieses Modell wurde ein einfacher Map Matching Algorithmus erstellt. Dieser hat den Viterbi-Algorithmus als Grundlage. Anhand von eigenen Simulationen erfolgte eine Beurteilung, inwiefern sich das Hidden Markov Modell tatsächlich für einen Map Matching Algorithmus eignet.