Teaching

Courses in winter semester 2021/2022
  • Discrete Mathematics
  • Graphs and Algorithms
  • Foundations and Discrete Structures
  • Higher Algebra
Studentinnen und Studenten hören eine Vorlesung im Hörsaal, zwei Laptops sind zu sehenTU Ilmenau / Michael Reichel (ari)

Further information

Moodle

Office hours:

Bachelor and Master Theses

Anzahl der Treffer: 59
Erstellt: Sun, 26 May 2024 17:27:03 +0200 in 0.0487 sec


Krone, Maximilian;
The cut cover problem in acyclic digraphs. - Ilmenau. - 27 Seiten
Technische Universität Ilmenau, Masterarbeit 2024

Die Arbeit untersucht Überdeckungen der Kantenmenge eines Digraphen mit k Schnitten (im Folgenden als k-Cut Cover bezeichnet). Eine äquivalente Eigenschaft ist die k-Färbbarkeit der Kanten so, dass keine zwei aufeinanderfolgenden Kanten uv, vw dieselbe Farbe erhalten. Eine Eckenfärbung mit höchstens M(k) Farben ist hinreichend für die Existenz eines k-Cut Covers, wobei M(k) der zentrale Binomialkoeffizient „k über [k/2]“ ist. Für symmetrische Digraphen erweisen sich diese beiden Eigenschaften als äquivalent. Hieraus folgt, dass das Problem zu entscheiden, ob ein (symmetrischer) Digraph ein k-Cut Cover besitzt, für k ≥ 3 NP-vollständig ist. Insbesondere untersucht diese Arbeit minimale Cut Covers in azyklischen Digraphen. Jeder azyklische Digraph mit maximalem Eingrad M(k)-1 hat ein k-Cut Cover, da er eine Eckenfärbung mit M(k) Farben besitzt. Es wird gezeigt, dass diese Schranke bestmögliche ist, und dies löst ein von Alon, Bollobás, Gyárfás, Lehel und Scott gestelltes Problem. Für die abgeänderte Bedingung, dass für jeden Knoten entweder sein Eingrad oder Ausgrad nach oben beschränkt ist, wird das minimale k, welches ein k-Cut Cover im Allgemeinen garantiert, bis auf höchstens zwei mögliche Werte bestimmt. Außerdem werden Cut Covers in Potenzen von gerichteten Pfaden betrachtet. Es wird gezeigt, dass ein k-Cut Cover in der d-ten Potenz beliebig langer gerichteter Pfade genau dann existiert, wenn d ≤ (c-o(1)) 2^k, für eine Konstante c ∈ [1/e, 1/2]. Ein Cut Cover in einem Digraphen kann auf alle Digraphen übertragen werden, die homomorph zu ihm sind. Die Existenz eines Homomorphismus zu einer Potenz eines gerichteten Pfades ist in polynomialer Zeit überprüfbar und äquivalent zu einer Gleichgewichtsbedingung für die Anzahl der Vorwärts- und Rückwärtskanten von ungerichteten Kantenzügen. Das Problem, zu entscheiden, ob ein azyklischer Digraph ein 3-Cut Cover besitzt, ist NP-vollständig, sogar für planare Digraphen mit maximalem Ein- und Ausgrad 3, die einen Homomorphismus zur dritten Potenz des gerichteten Pfades auf 12 Ecken besitzen.



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.