http://www.tu-ilmenau.de

Logo TU Ilmenau


Arbeitsgruppe
Diskrete Mathematik und Algebra


Ansprechpartner

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

Fachgebietsleiter

Telefon +49 3677 69-3633

E-Mail senden


Ihre Position

INHALTE

Studienabschlussarbeiten

Anzahl der Treffer: 68
Erstellt: Thu, 19 Oct 2017 23:07:16 +0200 in 0.0251 sec


Otte, Katrin
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.


http://www.gbv.de/dms/ilmenau/abs/85975037Xotte.txt
Fanselow, Niklas
Die verallgemeinerte Goldberg-Vermutung. - 52 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2015

In dieser Arbeit wurde der f-chromatische Index, d.h., die Kantenfärbungszahl eines gewichteten Graphen auf obere und untere Schranken untersucht. Die verallgemeinerte Goldberg-Vermutung ist eine solche obere Schranke. Die Parametrisierung der verallgemeinerten Goldberg-Vermutung wurde bisher nur für m=9 bewiesen. In dieser Arbeit wird Parametrisierung mittels einer neuen Methode von Tashkinov für m=11 gezeigt und ein neuer Beweis für m=9 geliefert.


http://www.gbv.de/dms/ilmenau/abs/843958456fanse.txt
Steinacker, Alex
Zur Struktur kritischer Hypergraphen. - 41 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2015

In dieser Arbeit werden kritische Hypergraphen betrachtet. Dabei werden bekannte Sätze von Graphen auf Hypergraphen erweitert und bewiesen, speziell über den Zusammenhang.


http://www.gbv.de/dms/ilmenau/abs/843519304stein.txt
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.


http://www.gbv.de/dms/ilmenau/abs/843511893roth.txt
Krumbholz, Michaela
Kontrahierbare Kanten in Spannbäumen 3-zusammenhängender Graphen und die Konstruktion von Füchsen. - 43 S.
Ilmenau : Techn. Univ., Masterarbeit, 2015

Es wurde das Hauptresultat aus der Arbeit "Every DFS-tree of a 3-connected graph contains a contractible edge" von Elmasry, Mehlhorn und Schmidt einfacher bewiesen. Weiterhin wurden sechs Konstruktionen für unendliche Klassen von Füchsen mit der Eigenschaft |m-2n| wächst mit n angegeben. Damit konnte sogar eine erste Antwort auf die Frage gefunden werden, wieviele Ecken vom Grad 3 ein Fuchs, im Verhaltnis zu seiner Eckenzahl, maximal enthalten kann.


http://www.gbv.de/dms/ilmenau/abs/834613018krumb.txt
Schweser, Thomas
Zur listenchromatischen Zahl signierter Graphen. - 39 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2015

Signierte Graphen sind Graphen, in denen jede Kante mit +1 oder -1 beschriftet (signiert) ist. Die vorliegende Arbeit gibt zunächst bereits bekannte Ergebnisse wieder, insbesondere zur signierten chromatischen Zahl, und beschäftigt sich danach intensiv mit Listenfärbungen signierter Graphen. Insbesondere wird eine Listenversion des Satzes von Brooks für signierte Graphen bewiesen. Den Abschluss der Arbeit bildet ein Kapitel über kritische und listenkritische signierte Graphen. In diesem liegt der Schwerpunkt darauf, eine Schranke für die minimale Anzahl von Kanten in schlichten k-listenkritischen signierten Graphen nachzuweisen. Ein kurzer Exkurs zu toroidalen Graphen schließlich zeigt den Nutzen dieser Schranke auf und motiviert dazu, sich weiter mit der Thematik der signierten Graphen zu beschäftigen.


http://www.gbv.de/dms/ilmenau/abs/83403879Xschwe.txt
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.


http://www.gbv.de/dms/ilmenau/abs/829195467schac.txt
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.


http://www.gbv.de/dms/ilmenau/abs/824068041zeune.txt
Zeyda, Robert
Algorithmen zur Berechnung des Volumens beschränkter nicht notwendig konvexer Polyeder im R 3. - 41 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2015

Die effiziente Volumenberechnung allgemeiner beschränkter Polyeder hat große Bedeutung in geometrischen und computergrafischen Bereichen. In dieser Arbeit wird dazu unter Benutzung geeigneter Datenstrukturen eine Methode aus der Literatur zur Berechnung von Geradenschnittpunkten aufgegriffen. Mithilfe dieser wird eine Struktur verwaltet, die das Problem zerlegt und sukzessive Teilvolumen aufaddiert. Damit ergibt sich für einen gegebenen Polyeder mit n berandenden Polygonen und höchstens m Ecken für jedes Polygon eine Laufzeit von O((nm + s) log(nm) + n 2 m 2 log n) mit s <= n 2 m 2. Die Schranke, insbesondere der Wert s, bietet Verbesserungsmöglichkeiten in der Abschätzung. Nach Konstruktion sind Verallgemeinerungen des gegeben Algorithmus für Polyederschnitte möglich. Dem gegenüber wird eine Methode mit Laufzeit O(nm) beschrieben, die eine konsistente Orientierung der Polygone fordert.


http://www.gbv.de/dms/ilmenau/abs/815298323zeyda.txt
Mendez, Thomas
Baumweite endlicher Graphen und Separatortheoreme. - 21 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014

Die Ergebnisse dieser Bachelorarbeit sind Aussagen über den Zusammenhang zwischen Baumweite und Zerlegbarkeit eines Graphen.


http://www.gbv.de/dms/ilmenau/abs/81356283Xmende.txt