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: 58
Erstellt: Wed, 27 Mar 2024 23:22:12 +0100 in 0.0455 sec


May, Verena;
Die Hadwiger Vermutung. - 104 S. Ilmenau : Techn. Univ., Diplomarbeit, 2011

Hadwiger stellte 1943 eine Vermutung über die Beziehung zwischen der chromatischen Zahl und der Existenz von vollständigen Minoren in Graphen auf: Ein zusammenhängender Graph mit chromatischer Zahl k lässt sich auf einen vollständigen Graphen K_k kontrahieren. Für k kleiner als 7 ist die Vermutung bewiesen, für alle anderen Fälle ist sie noch offen. Die Vermutung ist im Rahmen von Beweisversuchen zum Vierfarbenproblem entstanden. Diese Diplomarbeit liefert einen Überblick über die bisher erzielten Teilergebnisse und Beweisversuche zur Hadwiger Vermutung.



Richter, Sebastian;
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.



Kulse, Katja;
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.



Sasse, Thomas;
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.



Hahnemann, Susanne;
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.



Aschenbach, Daniel;
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.



Bechmann, Marcel;
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.



Schäfer, Philipp Matthias;
Two topics in discrete convexity. - 25 S. Ilmenau : Techn. Univ., Diplomarbeit, 2009

Abstrakte Konvexität behandelt Mengensysteme, die einige Eigenschaften mit den klassischen konvexen Mengen des $\mathbb{R}^n$ gemeinsam haben. Diskrete Strukturen, wie Graphen und partiell geordnete Mengen, induzieren konvexe Räume und verwandte mathematische Strukturen auf deren Grundmengen auf verschiedenste Art und Weise. - Der erste Teil behandelt sogenannte Strict Betweenness Relationen. Zwei Relationen dieser Art werden von Graphen und partiell geordneten Mengen induziert. Es wird gezeigt für welche Strict Betweeneess Relationen sowohl Graphen als auch partiell geordnete Mengen existieren, die diese induzieren. Das Hauptresultat gibt an, dass die Komponenten bzw. schwachen Komponenten von Graphen und partiell geordneten Mengen eines solchen induzierenden Paares eine schichtartige Struktur haben müssen. Es wird weiter gezeigt, dass unter gewissen Minimalitätsforderungen das induzierende Graph-Poset-Paar einer Strict Betweenness Relation eindeutig ist. - Ein weiteres Konzept von Konvexität, $\Delta$-Konvexität auf Kantenmengen von Graphen, wird im zweiten Teil behandelt. Im Speziellen werden Graphklassen, deren minimale $\Delta$-Hüllenmengen ihre spannenden Bäume sind, betrachtet. Zunächst werden zwei Resultate von Jamison \cite{Jamison} präsentiert. Dann werden einige weitere Beispiele solcher Klassen aufgezeigt. Zum Schluss wird gezeigt, dass alle Graphen, deren minimale $\Delta$-Hüllenmengen ihre spannenden Bäume sind, eine bestimmte Eigenschaft haben, um damit zu zeigen, dass die Vermutung Jamisons, dass alle null-homotopischen Graphen zu dieser Klasse gehören, falsch ist.



Hartleb, Christopher;
Beiträge zu unteren Schranken für die Unabhängigkeitszahl eines Graphen in Termen von Knotenzahl und Kantenzahl. - 34 S. Ilmenau : Techn. Univ., Diplomarbeit, 2009

Der Autor konstruiert multilineare untere Schranken für die Unabhängigkeitszahl beliebiger Graphen, deren Werte auf der Hauptdiagonale des zulässigen Bereiches monoton wachsen. - Desweiteren berechnet er durch eine Verfeinerung MIN-Algorithmus untere Schranken in dreiecksfreien Graphen.



Mann, Sebastian;
Anwendung kryptographischer Verfahren für Privacy Enhancement in multimedialen Anwendungen. - 85 S. Ilmenau : Techn. Univ., Diplomarbeit, 2009

Zielsetzung der vorliegenden Arbeit ist, Sinn und Einsatzmöglichkeiten kryptographischer Verfahren für Privacy Enhancement in muldimedialen Anwendungen zu untersuchen und die Verfahren im Anwendungsbereich der Nutzerauthentifizierung weiter zu entwickeln. Zu diesem zweck wird in der Arbeit ein Protokoll entwickelt, welches eine Pseudonymisierung von Nutzern ermöglichen soll, ohne dabei Rückschlüsse auf die reale Identität des Nutzers zuzulassen. Dieses Protokoll wird mit mathematischen und kryptoanalytischen Verfahren und Methoden untersucht. Weiterhin wird eine Anwendung dieses Authentifizierungsprotokolls in Form eines speziellen Abstimmungsverfahrens beschrieben und konzeptionell umgesetzt, die zur Überprüfung der Funktionalität des Authentifizierungsprotokolls dient.