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.2290 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.



Storch, Patrick;
Proxy games. - Ilmenau. - 48 Seiten
Technische Universität Ilmenau, Masterarbeit 2018

Obgleich Nashgleichgewichte das wohl bekannteste Lösungskonzept der Spieltheorie darstellen, sind sie doch eher theoretischer Natur. Damit ist gemeint, dass sich Personen in tatsächlichen Spielsituationen gar nicht, oder nur selten nach dem Nachgleichgewicht richten. Um diese Diskrepanz zwischen mathematischer Vorhersage und tatsächlichem Spielverhalten zu überbrücken, führen wir Stellvertreterspiele als eine weitere Ebene in Normalformspielen ein. Die Hauptidee hierbei ist es, zwischen der Auszahlung die ein Spieler erhält, und seinem/ihrem tatsächlichen Nutzen zu unterscheiden. In dieser Masterarbeit, welche auf den Ergebnissen von Stefan Zeuner und dessen Masterarbeit aufbaut, konnten wir zeigen, dass N-Personen-Spiele mit reinem Nashgleichgewicht stets auch ein reines Stellvertretergleichgewicht haben. Dies stellt eine Verallgemeinerung von Zeuners Resultat über 2-Personen-Spiele dar. Ebenfalls wird eine vollständige Charakterisierung von 2x2-Normalformspielen angegeben und gezeigt, dass diese stets ein reines Stellvertretergleichgewicht besitzen (unter der Voraussetzung, dass die Auswahlfunktion Phi pareto-optimale Ausgänge bevorzugt). Ebenso konnte gezeigt werden, dass die Auszahlungsfunktion des Stellvertreterspiels niemals stetig sein kann, was unsere Möglichkeiten bestehende Resultate bezüglich der Existenz von Nashgleichgewichten zu nutzen, erheblich einschränkt; Und wir konnten zeigen, dass das Konzept von Vertreterspielen (unter gewissen Voraussetzungen) einige grundlegende Probleme mit sich bringt, welche dem Satz von Gibbard-Satterthwaite, sowie Arrows Unmöglichkeitstheorem zuzuschreiben sind. Trotz dieser beiden vorhergehenden Ergebnisse konnte ein reines Stellvertretergleichgewicht (mit Beweis) für ein Spiel angegeben werden, welches mit keiner der vorher bekannten Methoden behandelt werden konnte. Ein möglicher Grund warum diese Art Lösung funktioniert und wie man sie gegebenenfalls auch auf andere Spiele ausweiten kann, wird ebenfalls angedeutet.



Kanzler, Kai;
Konvexe Einbettung und k-Zusammenhang. - Ilmenau. - 19 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2018

In der Arbeit habe ich auf Basis der Arbeit "Rubber bands, convex embeddings and graph connectivity" den Zusammenhang zwischen der konvexen X-Einbettung eines Graphen (Graphentheorie) und dessen k-Zusammenhang aufgezeigt, eine kurze algorithmische Betrachtung durchgeführt und auf den Nutzen eines solchen Algorithmus hingewiesen.



Fischer, Steffen;
A new separator theorem, metric properties and crossing numbers. - Ilmenau. - 34 Seiten
Technische Universität Ilmenau, Masterarbeit 2017

Gegeben sei ein einfacher, endlicher, ungerichteter Graph G = (V,E) mit Eckenmenge V (G) und Kantenmenge E(G). Die Kreuzungszahl eines Graphen G, die mit cr(G) bezeichnet wird, ist das Minimum aller Kantenkreuzungen über alle Zeichnungen von G in der Ebene. Diese ist eine wichtige Messgröße für die Charakterisierung der Nichtplanarität eines Graphen. Aufgrund der schweren Berechenbarkeit des dazugehörigen Entscheidungsproblems ist es gerechtfertigt, sich mit Schranken zu beschäftigen. Diese Masterarbeit liefert einen Beweis für eine obere Schranke für Graphen, die mit beschränkter Verzerrung eingebettet werden können. Unabhängig davon wird ein neues Separator-Theorem angegeben, das ein konstantes Größenverhältnis bei den Komponenten eines Graphen G erzeugt, die durch den Trenner S entstehen. Trenner von Graphen sind mächtige Werkzeuge, die durch den Teile-und-herrsche-Algorithmus motiviert sind.



Postel, Justus; von
Hadwigers Vermutung : eine Auswahl der bisherigen Ergebnisse. - Ilmenau. - 38 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2017

Ein wichtiges Thema der Graphentheorie ist das Färben von Graphen und in diesem Zusammenhang die chromatische Zahl. Der wohl bekannteste Satz zu diesem Thema ist der 4-Farben-Satz, der sich ursprünglich mit dem Färben von Landkarten bschäftigte. Mit einer Verallgemeinerung dieses Themas und einer Verbindung der Färbungszahl mit gewissen Unterstruktren beschäftigte sich der Schweizer Hugo Hadwiger und stellte eine sehr weitreichende Vermutung auf.



Fabel, Marc;
Ein alternatives Lösungskonzept für 2-Personen Normalformspiele. - 60 Seiten
Technische Universität Ilmenau, Masterarbeit 2016

In der nicht kooperativen Spieltheorie existiert kein komplett zufriedenstellendes Lösungskonzept. Selbst das häufig verwendete Nash-Gleichgewicht liefert nicht immer plausible Ergebnisse, sodass in der aktuellen Forschung nach neuen besseren Lösungskonzepten gesucht wird. In dieser Arbeit wird ein neues Lösungsverfahren für 2-Personen Normalformspiele vorgestellt, welches iterativ vorgeht. Nach der Definition werden erste Eigenschaften gezeigt, bevor es auf verschiedene bekannte Beispiele der Spieltheorie angewendet wird. Anhand dieser Spiele wird untersucht, ob das Verfahren plausible Lösungen liefert. Des Weiteren dienen die Beispiele um Vergleiche zu anderen bekannten Lösungskonzepten der Spieltheorie durchzuführen.



Mohr, Samuel;
Über untere Schranken zur Unabhängigkeit in Graphen. - 57 Seiten
Technische Universität Ilmenau, Masterarbeit 2016

Gegeben sei ein einfacher, endlicher, ungerichteter Graph G = (V, E) mit Eckenmenge V(G) und Kantenmenge E(G). Eine unabhängige Menge in G ist eine Teilmenge der Eckenmenge 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. Aufgrund der schweren Berechenbarkeit des dazugehörigen Entscheidungsproblems ist es gerechtfertigt, sich mit Schranken, überwiegend unteren Schranken, zu beschäftigen. Der Beitrag dieser Masterarbeit ist eine neue untere Schranke, die als Verbesserung der bekannten Caro-Wei-Schranke aufgefasst werden kann. Hierbei sind insbesondere Spezialisierungen von Interesse, die zu einfachen und leicht berechenbaren Schranken führen. Neben Vergleichen mit klassischen unteren Schranken von O. Murphy und S. M. Selkow wird das Resultat genutzt, um eine Schranke zu entwickeln, die einer Vermutung von E. Bertram und P. Horak nahe kommt.



Kulse, Katja;
Caro-Wei-ähnliche untere Schranken für Unabhängigkeit in Graphen. - 18 Seiten
Technische Universität Ilmenau, Masterarbeit 2016

In der vorliegenden Arbeit wird für zusammenhängende und nicht vollständige Graphen die Caro-Wei-Schranke CW(G) betrachtet. Auf dessen Grundlage wird eine Klassifizierung von Caro-Wei-ähnlichen unteren Schranken für die Unabhängigkeitszahl in Graphen vorgenommen. Außerdem wird eine neue untere Schranke, $\alpha(G) \geq CW(G) + \sum\limits_{v \in V(G)} \sum\limits_{(A,B) \in \pi(v)} \sum\limits_{[A,B,v,\sigma,\tau]\in F(A,B,v)}\frac{1}{c_1\cdots c_{|A|}d_1\cdots d_{|B|}(d(v)+1-|B|)}$, bewiesen. Im Beweis wird der Spezialfall $|A|=|B|=1$ betrachtet und somit die Schranke $\alpha(G) \geq CW(G) + \sum\limits_{v \in V(G)} \sum\limits_{(v,w,u) \in W^2(v)} \frac{1}{|N[v,w,u]| (|N[v,w]|-1) d(v)}$ für induzierte Wege der Länge 2 formuliert. Das daraus entstandene schwächere Theorem wurde vollständig bewiesen.



Otte, Katrin; von
Deterministische Irrfahrten auf Graphen. - 31 Seiten
Technische Universität Ilmenau, Diplomarbeit 2016

Die Arbeit behandelt die deterministische Irrfahrt I in der Eckenversion und die deterministische Irrfahrt I' in der Kantenversion.



Roth, Carolin;
Über die Existenz von gewissen induzierten Untergraphen eines Graphen. - 15 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2015

Die vorliegende Arbeit beschäftigt sich mit einem Optimierungsproblem auf Graphen. Hierbei werden den n Knoten des Graphen G und den zwischen ihnen verlaufenden Kanten positive Zahlenwerte zugeordnet und mit diesen wird eine quadratische Funktion betrachtet. Ziel dieser Arbeit ist es, das Maximum dieser Funktion über dem n-dimensionalen Einheitswürfel zu ermitteln. Die Lösung dieses Problems, die Funktion zu maximieren, ist nicht einfach, da das untersuchte Problem NP-vollständige Unterprobleme enthält. Es wird deutlich, dass im Allgemeinen das Maximum der Funktion durch einen induzierten Untergraphen H von G realisiert wird. Dieser hat je nach Wahl der den Knoten und Kanten zugeordneten Zahlenwerte bestimmte Eigenschaften. Da die explizite Maximierung der Funktion NP-vollständige Probleme als Unterprobleme enthält, wird der Maximalwert in dieser Arbeit als gegeben angenommen. Es wird festgestellt, dass das Maximum in einer Ecke des Einheitswürfels angenommen wird. Mithilfe dieses Resultats wird ein gewisser Untergraph H von G betrachtet, welcher durch bestimmte Knoten des Graphen G induziert werden kann. Wird der Untergraph H zusätzlich minimal gewählt, können weitere Aussagen über den Maximalwert getroffen werden. Durch die verschiedene Wahl der Zahlenwerte an Knoten und Kanten, können gewisse Eigenschaften des Untergraphen H erzwungen werden. Somit werden Resultate erhalten, welche die Existenz von induzierten Untergraphen eines gegebenen Graphen G sichern. Die in den letzten Kapiteln der Arbeit beschriebenen Sätze sagen aus, dass unter gewisser spezieller Wahl der Zahlenwerte an Knoten und Kanten ein induzierter Untergraph H von G mit einem gewissen Maximum existiert, welcher eine gewisse zusätzliche Eigenschaft besitzt. Zum Beispiel ist in bestimmten Fällen die Knotenmenge unabhängig oder die Maximalvalenz beschränkt.



Schacht, Johanna Eleonore;
Notwendige und hinreichende Bedingungen für Nachbarschaftshypergraphen. - 28 S. Ilmenau : Techn. Univ., Masterarbeit, 2015

Ein Nachbarschaftshypergraph ist ein Hypergraph H, der aus einem schlichten Graphen G entsteht, indem die Nachbarschaft jeder Ecke von G einen Block von H bildet. Der Graph G wird dabei Ursprungsgraph von H genannt. Wir betrachten in dieser Arbeit, unter welchen Bedingungen ein Hypergraph ein Nachbarschaftshypergraph ist. In Kapitel 2 zeigen wir notwendige Bedingungen, die alle Nachbarschaftshypergraphen erfüllen. Insbesondere beweisen wir mit Satz 2.7, dass sie selbstdual sind. Außerdem stellen wir mit Satz 2.10 den Zusammenhang zwischen einer Adjazenzmatrix eines Graphen und der Inzidenzmatrix des zugehörigen Nachbarschaftshypergraphen vor. In Kapitel 3 beschäftigen wir uns mit der Klasse der 2-Designs. Dabei zeigen wir mit Lemma 3.3, welche Eigenschaften die Ursprungsgraphen von 2-Designs haben und darauf aufbauend beweisen wir mit algebraischen Methoden in Satz 3.4 notwendige Bedingungen für die Parameter der 2-Designs, die Nachbarschaftshypergraphen sind. Auswirkungen der Eigenschaften Bipartitheit und Zusammenhang der Ursprungsgraphen auf ihre Nachbarschaftshypergraphen betrachten wir in Kapitel 4. Die Sätze 4.5 und 4.6 zeigen, welche Beziehungen zwischen den Zusammenhangskomponenten eines Hypergraphen genau dann bestehen, wenn es einen bipartiten Ursprungsgraphen gibt. Beispiel 4.9 beweist, dass ein Hypergraph verschiedene, nicht bipartite Ursprungsgraphen haben kann. Dahingegen ist ein bipartiter Ursprungsgraph immer bis auf Isomorphie eindeutig, was aus Satz 4.8 folgt. Für die Hypergraphen in Kapitel 5 setzen wir Kreisfreiheit voraus. Daraus folgt, dass gegebenenfalls Ursprungsgraphen Wälder sind, wo durch wir auf den Ergebnissen aus Kapitel 4 aufbauen können. Wir greifen einen Algorithmus zur Überprüfung, ob Bäume isomorph sind, auf, der von Hochstättler in dem Buch Algorithmische Mathematik vorgestellt wird. Diesen nutzen wir, um einen Algorithmus anzugeben, mit dem getestet werden kann, ob die Zusammenhangskomponenten eines Hyperwaldes die notwendigen und hinreichenden Bedingungen für die Existenz eines bipartiten Ursprungsgraphen erfüllen. Dieser Algorithmus arbeitet in Polynomialzeit.



Zeuner, Stefan;
Stellvertreterspiele. - 35 S. Ilmenau : Techn. Univ., Masterarbeit, 2015

In der vorliegenden Arbeit werden 2-Personen Normalformspiele untersucht. Jedem solchen Spiel kann ein so genanntes Stellvertreterspiel zugeordnet werden. Die Idee dabei ist, dass die Spieler ihre Aktionen nicht selbst auswählen, sondern Stellvertreter benennen, welche das Spiel in ihrem Auftrag spielen. Die Nutzenfunktionen der Stellvertreter stimmen nicht notwendig mit denen der Spieler überein. Es wird angenommen, dass die Stellvertreter rational im Sinne der Spieltheorie sind und sowohl die eigene Nutzenfunktion als auch die Nutzenfunktion des jeweils anderen Stellvertreters kennen. Rationalität impliziert, dass die Stellvertreter ein Nash Equilibrium in dem durch ihre Nutzenfunktionen induzierten Spiel spielen. Die Spieler erhalten die Auszahlung, welche sich aus diesem Nash Equilibrium ergibt. Da das sich ergebende Spiel mehr als ein Nash Equilibrium haben kann, muss eine Auswahlfunktion Phi fixiert werden, welche das Nash Equilibrium auswählt. Damit wird ein neues Spiel definiert, in welchem die Strategien der Spieler die Stellvertreter sind und die Auszahlungen die Auszahlungen in den durch Phi ausgewählten Nash Equilibria in dem durch die Nutzenfunktionen der Stellvertreter induzierten Spiel sind. Das Studium der Nash Equilibria dieses neuen Spiels bildet den Inhalt der vorliegenden Arbeit.



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.



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.



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.



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.



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.



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.



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.



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.



Krumbholz, Michaela;
Kritische Hypergraphen kleiner Ordnung. - 34 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2013

Es wurden Regeln zum Erhalten der k-kritischen Hypergraphen mit k, k+1 oder k+2 Ecken, sowie aller 2-kritischen Hypergraphen aufgestellt. Weiterhin wurden vollständige Listen der 1-kritischen Hypergraphen, 3-kritischen Hypergraphen mit fünf Ecken und 4-kritischen Hypergraphen mit sechs Ecken erstellt.



Thomann, Jana;
Eckenfärbungskonzepte für verschiedene Graphenklassen. - 39 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2013

Für einen Graph G mit der Eckenmenge V und der Kantenmenge E wird das klassische Eckenfärbungskonzept verallgemeinert. Hierbei weist man zunächst jeder Ecke v des Graphen eine Menge S(v) zu, welche lediglich eine Teilmenge von V \cup E sein muss. Des Weiteren wählt man eine Gewichtsfunktion w : V \cup E -> {1,2,..,k}, wobei k eine natürliche Zahl ist. Nun wird für jede Ecke v mittels c(v) = sum_{x \in S(v)} w(x) eine Farbe definiert. Die so entstandene Färbung soll zulässig sein, d.h. benachbarte Ecken sollen stets verschieden gefärbt sein. Unter dieser Bedingung soll die Zahl k minimiert werden. Wie obere Schranken für dieses minimale k aussehen können, wird für verschiedene Färbungskonzepte, also verschiedene Mengen S(v), angewendet auf einige Graphenklassen untersucht. Genauer werden die Färbungskonzepte S(v) = N(v) = {x \in V | xv \in E} und S(v) = N[v] = N(v) \cup {v} für Kreise, Bäume, bipartite und vollständige r-partite Graphen betrachtet. Zusätzlich werden die Färbungskonzepte S(v) = N_E(v) = {uv \in E | u \in V} , S(v) = N[v] \cup N_E(v) und S(v) = N(v) \cup N_E(v) für Bäume betrachtet.



Haase, Jens;
Ein Netzwerkfärbungsalgorithmus mit Listenfärbungen. - 38 S. Ilmenau : Techn. Univ., Diplomarbeit, 2013

Kernpunkt dieser Arbeit ist die verteilte Färbung von Netzwerken. Als allgemeine Form von Färbungen werden Listenfärbungen verwendet, die von verteilten Algorithmen vorgenommen werden. Bei verteilten Algorithmen besteht das Problem des "symmetry breaking", welches beispielsweise durch probabilistische Algorithmen gelöst werden kann. Kommunikation geschieht nur durch Erkennen der Farben der Nachbarn. Zunächst wird mit Hilfe eines Greedy-Algorithmus mit probabilistischer Farbauswahl bei vorgegebener Mindestwahrscheinlichkeit 1-d einer zulässigen Färbung die obere Schranke O(log(n/d)) für Listenfärbungen mit Mindestlistenlänge d(u)+1 für jede Ecke u bewiesen. Im Anschluss wird ein Algorithmus vorgestellt, der ein einfaches zentralisiertes Färbungsverfahren, welches die Färbungszahl col(G) zu Hilfe nimmt, auf verteilte Färbungen überträgt. Mit diesem Algorithmus wird bei vorgegebener Mindestwahrscheinlichkeit 1-d einer zulässigen Färbung die obere Schranke O(n log(n/d)) für Listenfärbungen mit Mindestlistenlänge col(G) für jede Ecke gezeigt. Abschließend wird bewiesen, dass jeder beliebige verteilte Algorithmus mindestens Omega(n) Runden benötigt, um jeden beliebigen Graphen mit mindestens col(G) Farben zulässig zu färben.



Holzlehner, Saskia;
Flächenberechnung polygonalberandeter Objekte. - 62 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2013

Im Katasteramt ist es nötig, verschiedene Grundstücksgrenzen zu markieren. Vor allem spielt die Unterteilung dieser Flächen in Nutz- und Grundstücksflächen eine zentrale Rolle. In dieser Arbeit wird ein Algorithmus entwickelt, welcher die Flächen von ebenen polygonalberandeten Objekten und deren Schnitten berechnet. Um mit zweidimensionalen Objekten handhaben zu können, besteht die Möglichkeit deren Ränder durch einfach geschlossene Polygonzüge zu approximieren. Zunächst wird die Flächenberechnung affiner Funktionen auf endlichen Intervallen betrachtet. Anschließend steigert man sich mittels Vereinigungen von Trapezflächen auf die Berechnung der Flächeninhalte polygonalberandeter Objekte. Hierbei werden diese Objekte in endlich viele Trapeze mittels Schnittgeraden zerlegt. Dafür müssen die Schnittpunkte zwischen den verschiedenen einfach geschlossenen Polygonzügen ausfindig gemacht werden. Am Schluss wurde dieser Algorithmus zur Flächenberechnung in einem C++-Programm umgesetzt.



Sasse, Thomas;
An improvement on the Erdös-Pósa property for long circuits. - 43 S. : Ilmenau, Techn. Univ., Masterarbeit, 2013

Zu jeder natürlichen Zahl $\ell \geq 3$ und jedem beliebigen Graphen $G$ derart, dass $G$ keine zwei eckendisjunkte Kreise der Länge mindestens $\ell$ enthält, exisitert eine Eckenmenge $X$ von höchstens $\frac{5}{3}\ell+\frac{13}{3}$ Elementen derart, dass $G - X$ keinen Kreis der Länge mindestens $\ell$ mehr enthält. Dies ist eine Verbesserung der oberen Schranke $2\ell+3$ von Birmelé, Bondy und Reed (The Erdös-Pósa property for long circuits, {Combinatorica} {27} (2007), 135-145).



Langner, Kerstin;
Über Unterteilungen des $K_{3,3}$ in Graphen. - 30 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2012

Diese Arbeit beschäftigt sich mit den Fragen: 1. Unter welchen Voraussetzungen enthält ein nichtplanarer Graph eine Unterteilung des $K_{3,3}$? 2. Unter welchen Voraussetzungen enthält ein paarer Graph sogar eine saubere Unterteilung des $K_{3,3}$?



Richter, Sebastian;
Packungen von isomorphen induzierten unabhängigen Untergraphen. - 38 S. Ilmenau : Techn. Univ., Masterarbeit, 2012

Zu einem gegebenen Graphen $G$ nennt man zwei eckendisjunkte induzierte Untergraphen $H$ und $H'$ von $G$ unabhängig in $G$, wenn in $G$ keine Kante zwischen $H$ und $H'$ existiert. Mit $\alpha(G,H)$ bezeichnen wir die maximale Anzahl von eckendisjunkten Kopien von $H$, die in $G$ als induzierte und paarweise unabhängige Untergraphen enthalten sind. Damit ist $\alpha(G,K_1)$ äquivalent zur Unabhängigkeitszahl von $G$. In der Arbeit werden obere Schranken für $\alpha(G,H)$ gezeigt. Dabei wird die Ungleichung $\alpha(G,K_1)\le \frac{-\lambda_0 }{r-\lambda_0 } |V(G)|$ von A.J. Hoffman für einen $r$ - regulären Graphen $G$ mit kleinstem Eigenwert $\lambda_0$ verallgemeinert. Für einen beliebigen Graphen $G$ mit größtem Eigenwert $\ambda^0$ und Minimalgrad $\delta$ hat W.H. Haemers die Ungleichung von Hoffman erweitert zu $\alpha(G,K_1)\le \frac{-\lambda_0\lambda^0}{\delta^2-\lambda_0\lambda^0} |V(G)|$. Unsere Resultate sind nicht mit dem Ergebnis von W.H. Haemers vergleichbar.



Dumke, Mandy;
Unabhängigkeit und Potentiale in ungerichteten Graphen. - 45 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2012

Abschlussarbeit zur Approximation der Unabhängigkeitszahl mit Hilfe von Potentialen, eine Verbesserung der Caro-Wei-Schranke, unterstützt durch das Programm "Graphen"



Boßecker, Anett;
Über die Güte der Potentialschranke für die Unabhängigkeitszahl in k-degenerierten Graphen. - 47 S. Ilmenau : Techn. Univ., Masterarbeit, 2012

Die Caro-Wei-Schranke d(G) ist eine berühmte untere Schranke für die Unabhängigkeitszahl alpha(G) in einem Graphen. In einer Arbeit von Borowiecki und anderen wurden Parameter gleicher Art untersucht, die ebenso von einem Eckenpotential abhängen. Dabei wird eine Klasse von Potentialen definiert, die zu einer Verbesserung der Caro-Wei-Schranke führt. Die Aufgabenstellung war nun, die Güte dieser neuen Schranke p(G) für Bäume zu untersuchen: Gibt es für Bäume eine Konstante C > 0, sodass der Quotient p(G) / d(G) durch C beschränkt bleibt? Für k-degenerierte Graphen konnte in einem einfachen Beweis C(k) = (2k + 1) / 2 gezeigt und dies in einem aufwändigeren Beweis zu C(k) = (k^2 + 5k + 6) / (4k + 6) verbessert werden. Darüber hinaus wurde ein bestmögliches Resultat für Bäume, 1-degenerierte Graphen, bewiesen.



Zeuner, Stefan;
Mechanismendesign am Beispiel der Berechnung von Ersatzzahlungen bei ungewissen Schäden. - 25 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2011

Diese Bachelorarbeit beschäftigt sich mit kollektiven Entscheidungsproblemen und deren Lösung über sogenannte anreizeffiziente Wahlmechanismen. Hierzu wird ein von Roger B. Myerson vorgestelltes Verfahren näher erläutert und anschließend ein von ihm gewähltes Beispiel überprüft und erweitert. Des Weiteren wird in Abschnitt 3 das dem Traveler's Dilemma zugrunde liegende Entscheidungsproblem betrachtet und umgeformt zur Berechnung von Ersatzzahlungen.



Pflugradt, Steffi;
Obere Schranken für die Summe der p-ten Potenzen der Knotengrade dreikreisfreier, schlichter Graphen. - 40 S. Ilmenau : Techn. Univ., Masterarbeit, 2011

Um obere Schranken für die Summe der p-ten Potenzen der Knotengrade zu finden werden in der Arbeit, neben der Dreikreisfreiheit, weitere Voraussetzungen an die Graphen gestellt. Dadurch konnten obere Schranken für die Summe der p-ten Potenzen der Knotengrade für dreikreisfreie Graphen mit bekannter chromatischer Zahl, dreikreisfreie Graphen mit bekanntem Minimal- und Maximalgrad und dreikreisfreie Graphen mit verschiedenen Planaritätseigenschaften gewonnen werden. Im Zusammenhang mit der Suche nach oberen Schranken für die Summe der p-ten Potenzen der Knotengrade für Graphen mit verschiedenen Planaritätseigenschaften wurde für 1-planare, dreikreisfreie Graphen eine neue obere Schranke für die Kantenanzahl bewiesen. Der letzte Teil der Arbeit zeigt lediglich eine Anwendungsmöglichkeit für die oberen Schranken der Summe der p-ten Potenzen der Knotengrade auf. Indem die Jensensche Ungleichung auf die Ungleichung von Caro und Wei angewendet wird, können wir mit Hilfe der gewonnenen oberen Schranken für die Summe der p-ten Potenzen der Knotengrade untere Schranken für die Unabhängigkeitszahl gewinnen.



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.



Just, Elke;
Nash-Gleichgewichte des Pagerankspiels. - 49 S. Ilmenau : Techn. Univ., Diplomarbeit, 2009

Betrachtet wird jenes Normalformspiel, das die Webseiten des World Wide Web als Spieler enthält, welche in beliebigerweise Links setzen können und als Auszahlung den von Google verwendeten PageRank erhalten. Ziel der Arbeit ist es, die Struktur der Nash-Gleichgewichte dieses Spiels zu bestimmen. Mit Hilfe des Modells des nachtragenden Websurfers werden notwendige und hinreichende Bedingungen für das Vorliegen eines Nash-Gleichgewichtes angegeben. Desweiteren wird ein Algorithmus zur automatischen Berechnung von Nashgleichgewichten vorgestellt.



Zeiße, Tina;
Experimentelle Überprüfung einer Vermutung zu Delay-optimalen Bäumen. - 68 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2009

In dieser Arbeit werden Delay-optimale Bäume betrachtet, die durch einen Algorithmus von Bartoschek, Held, Rautenbach und Vygen erzeugt werden. Diese Bäume dienen zur Realisierung von Schaltungen auf einem Computer-Chip. Durch Bartoschek, Held, Rautenbach und Vygen wurde bereits eine untere Schranke für die Zielfunktion des Algorithmus angegeben. Ziel der Arbeit ist es, durch eine experimentelle Überprüfung in Maple festzustellen, wie stark die resultierenden Delay-optimalen Bäume bei Veränderung der Ausgangsbedingungen (Eingabe von unsortierten Ausgangswerten an Stelle von fallend sortierten Werten) voneinander abweichen. Dazu wurde der Algorithmus in Maple 10 implementiert und etwa 250000 Berechnungen durchgeführt. Dabei wurden die Veränderungen der Delay-optmalen Bäume miteinander verglichen. Durch diese Überprüfung war es möglich für die berechneten Beispiele eine neue obere Schranke für die Zielfunktion anzugeben.



Bauermann, Patrick;
Initialisierung einer Kommunikation. - 53 S. Ilmenau : Techn. Univ., Diplomarbeit, 2008

Bei der Betrachtung von Lernverfahren für wiederholte Normalformspiele ergibt sich die Frage nach solchen Verfahren, die in einem beliebigen, fest vorgegebenen Spiel fast sicher gegen ein vorhandenes Nash-Gleichgewicht konvergieren. - In der Arbeit wird gezeigt, welche Voraussetzungen dafür erfüllt sein müssen und wie ein solches Lernverfahren konstruiert werden kann. Darüber hinaus wird bewiesen, dass die ermittelten Voraussetzungen notwendig sind für die Existenz eines Lernverfahrens. Zu diesem Zweck wird die Problemstellung in eine Begriffswelt überführt, welche die Diskussion der Lernverfahren als Algorithmus veranschaulicht.



Boßecker, Anett;
Die Unabhängigkeitszahl in Graphen mit wenigen Dreiecken. - 41 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2008

James B. Shearer zeigt, dass die Unabhängigkeitszahl [alpha](G) eines dreiecksfreien, n-eckigen Graphen G mindestens so groß wie n i = 1 f(d i) ist, wobei d i dem Grad der Ecke i entspricht. Die Funktion f ist hierbei rekursiv gegeben durch f(0) = 1 und f(d) = (1 + (d 2 - d)f(d - 1))/(d 2 + 1) für d 1 (A Note on the Independence Number of Triangle-Free Graphs, Discrete Mathematics, 46:83-87, 1983). - Dieser Satz und der dazugehörende Beweis bilden die Basis für die Betrachtungen der Unabhängigkeitszahl in Graphen ohne Dreiecke. In dieser Arbeit wird nun untersucht, wie sich die Funktion f ändert, wenn man einige Dreiecke in Graphen, insbesondere in Graphen mit Maximalgrad [delta](G) 3, zulässt. Mit der neuen Funktion f, gegeben durch f(0, 0) = 1 und f (d, t) = (1 + (d 2 d - 2t)f(d - 1, t))/(d 2 - 2t + 1) für t (d 2) und f(d, t) = 0 sonst, genügt die Unabhängigkeitszahl der Abschätzung [alpha](G) n i = 1 f(d i, t i). Dabei bezeichnet d i wiederum den Grad der Ecke i und t i ihre Dreieckszahl, die für jede Ecke die Anzahl der Dreiecke angibt, die die jeweilige Ecke enthalten.



Siegfried, Nadine;
Die Readability monotoner boolescher Funktionen. - 38 S. Ilmenau : Techn. Univ., Diplomarbeit, 2008

In dieser Diplomarbeit betrachten wir ein Problem, welches von Golumbic, Peled und Rotics aufgeworfen wurde. Es behandelt das Verhältnis zwischen einem Komplexitätsmaß für Boolesche Funktionen und einer Problematik der Graphenüberdeckung. Genauer gesagt, setzt das Problem die sogenannte Readability von monotonen Booleschen Funktionen in Verbindung mit Kantenüberdeckungen von Graphen, die solchen Funktionen zugeordnet werden, durch Kantenmengen vollständiger bipartiter Teilgraphen. - Eine monotone Boolesche Funktion hat eine Readability von höchstens k, wenn sie durch eine Formel dargestellt werden kann, in welcher jede Variable höchstens k mal vorkommt. Wir ordnen einer monotonen Booleschen Funktion F einen Graph G zu, dessen Knotenmenge die Menge von Variablen von F ist und die Minimalterme von F genau den maximalen Cliquen von G entsprechen. - Golumbic et al. stellten die Frage, ob jede monotone Boolesche Funktion F, deren zugehöriger Graph G dreiecksfrei ist, durch eine hinsichtlich der Readability optimale Formel p dargestellt werden kann, so dass p einer Kantenüberdeckung c von G durch Kantenmengen vollständiger bipartiter Teilgraphen entspricht. Hierbei ist die Anzahl, wie oft eine bestimmte Variable x in p vorkommt, gleich der Anzahl von vollständigen bipartiten Teilgraphen, welche von c benutzt werden und den Knoten x enthalten. - In Ihrem Manuskript bewiesen Golumbic et al. die Beziehung zwischen der Readability und der Problematik der Graphenüberdeckung für eine spezielle Folge von Graphen. In Abschnitt 2 beweisen wir als unser erstes Hauptresultat, dass die Argumente von Golumbic et al. noch für eine andere Folge von Graphen funktionieren. Darüber hinaus bearbeiten wir in Abschnitt 3 einen Spezialfall dieser Problematik, welcher Formeln einer eingeschränkten Struktur behandelt, dessen zugehörige Graphen dreiecksfrei sind.



Schmidt, Michael;
"Football pools" mit höchstens 13 Spielen. - 67 S. Ilmenau : Techn. Univ., Diplomarbeit, 2008

Erstes Kapitel ist allgemeine Einleitung. Darauf folgt ein Kapitel mit Grundlagen der Codierungstheorie. Das Kapitel 3 beschäftigt sich mit Codes und Tippsystemen, worauf in Kapitel 4 eine Verallgemeinerung dessen und eine Betrachtung mit Hilfe der Graphentheorie folgt. Insbesondere geht es um die Einführung des "football pool problem" als Dominanzproblem. Es folgt die Einführung einer eigenen minimalen Tippmenge und dem Aufstellen unterer und oberer Schranken. Kapitel 5 gibt einen Überblick über die bis dato vorliegenden Verbesserungen der in der Literatur betrachteten Systeme und damit den minimalen Tippmengen. Abschließend erfolgt in Kapitel 6 eine Betrachtung des Problems als lineares ganzzahliges Optimierungsproblem.



Artmann, Sarah;
Über die Dominanzzahl regulärer Graphen unter Nutzung multilinearer Funktionen. - 34 S. Ilmenau : Techn. Univ., Diplomarbeit, 2007

Die Dominanzzahl eines Graphen ist die minimale Anzahl von Knoten in einer Menge D, für die jeder Knoten des Graphen entweder selber in der Menge D liegt oder einen Nachbarn in D besitzt. - In dieser Arbeit werden reguläre Graphen mit großer Taillenweite betrachtet, das heißt, jeder Knoten des Graphen hat die gleiche Anzahl von Nachbarn und ein kürzester Kreis im Graphen hat eine hinreichend große Länge. - Es wird eine neue Strategie entwickelt, durch die neue obere Schranken für die Dominanzzahl dieser Graphenklasse bewiesen werden können.



Scheide, Diego;
Kantenfärbungen von Multigraphen. - 34 S. Ilmenau : Techn. Univ., Diplomarbeit, 2007

Das Kantenfärbungsproblem für Graphen ist ein NP-schweres Problem. Für einen Multigraphen G ist der chromatische Index c(G) - die minimale Anzahl an benötigten Farben - nach unten beschränkt durch den Maximalgrad D(G) und nach oben durch die Summe D(G)+m(G) aus dem Maximalgrad und der maximalen Kantenvielfachheit von G. Aus der Literatur ist eine Vielzahl weiterer oberer Schranken für den chromatischen Index bekannt, für die sich mittels effizienter Färbungsalgorithmen entsprechende Färbungen konstruieren lassen. - Auf der Basis der klassischen Umfärbungsmethoden an sogenannten Fächern wird im ersten Teil dieser Arbeit eine neue obere Schranke - die Fächerzahl - eingeführt, welche gleichzeitig eine Vielzahl der bekannten Schranken verbessert. Ein entsprechender Färbungsalgorithmuss, der diese Fächerzahl effizient realisiert, wird ebenfalls angegeben. - Im zweiten Teil der Arbeit wird die Güte der bereits erwähnten klassischen Schranke D(G)+m(G) von Vizing in Abhängigkeit der beiden benötigten Parameter D(G) und m(G) untersucht. Dabei werden Bereiche charakterisiert, für die Graphen G mit c(G)=D(G)+m(G) konstruiert werden können. Diese Charakterisierung ist zudem vollständig, falls die Goldbergvermutung stimmt. Für weitere Bereiche kann auch ohne Goldberg gezeigt werden, dass die Vizing-Schranke nicht erreichbar und sogar beliebig schlecht wird.