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: Mon, 23 Oct 2017 07:05:44 +0200 in 0.1698 sec


Zeyda, Robert
Über eine Modifikation des Pólyaschen Urnenprozesses. - Ilmenau. - 42 Seiten
Technische Universität Ilmenau, Masterarbeit, 2017

Diese Arbeit beschäftigt sich mit einer möglichen Verallgemeinerung von Pólyas Urnenprozess aus dem Jahre 1923. Charakteristisch für das Ausgangsproblem ist die Vergrößerung der Wahrscheinlichkeit eines Ereignisses, je häufiger es in der Vergangenheit eingetreten ist. Dieser Effekt modelliert Zusammenhänge in sozialen Netzwerken, wie die Ausbreitung von Krankheiten. Das Grenzverhalten bezüglich der Häufigkeiten beider Kugelfarben wurde dazu beschrieben und weitere Variationen des Problems mit mehreren Urnen und Kugelfarben aus der Literatur analysiert. Das selbst gestellte Problem verallgemeinert Pólyas Modell derart, dass unter den Urnen $U_1,\dots,U_k$ unabhängig und gleichverteilt zwei Urnen $U_q$ und $U_e$ ausgewählt werden, wobei eine Kugel aus $U_q$ gezogen, zurückgelegt und eine gleichfarbige Kopie in $U_e$ gelegt wird. Dabei wurde die fast sichere Konvergenz der relativen Häufigkeiten von (farbunabhängiger) Kugelzahl einer Urne im Vergleich zum Gesamtbestand sowie der Anzahl der Kugeln einer bestimmten Farbe in einer Urne zur Gesamtzahl gleichfarbiger Kugeln gegen $1/k$ festgestellt. Damit konnte geschlussfolgert werden, dass für den Spezialfall des zweiurnigen Modells die Differenz der relativen Anteile für zwei Farben mit $n \to \infty$ fast sicher gegen 0 konvergiert. Weiter wurden Algorithmen zur Simulation von Realisierungen und der sukzessiven Berechnung der exakten Verteilung angegeben, die die Farbverteilungen der beiden Modelle vergleichen sollen.


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


http://www.gbv.de/dms/ilmenau/abs/1000474887fisch.txt
Schweser, Thomas
Graph partitions. - Ilmenau. - 52 Seiten
Technische Universität Ilmenau, Masterarbeit, 2017

Eine Partition eines Graphen $G$ ist eine Folge $(G_1,G_2,\ldots,G_p)$ paarweise disjunkter induzierter Teilgraphen von $G$ mit $V(G)=V(G_1) \cup V(G_2) \cup \ldots \cup V(G_p)$. Diese Arbeit beschäftigt sich mit Zerlegungen von (Multi-)Graphen unter bestimmten Gradbedingungen. So werden unter anderem eine Verallgemeinerung eines Satzes von Borodin, Kostochka und Toft bewiesen, welcher Zerlegungen von Graphen mit Anforderungen an die Degeneriertheit untersucht. Des Weiteren werden Sätze von Stiebitz, Kaneko, Bazgan, Tuza und Vanderpooten, als auch Liu und Xu verallgemeinert; diese handeln von Graphzerlegungen mit Mindestanforderungen an den Minimalgrad.


http://www.gbv.de/dms/ilmenau/abs/895549840schwe.txt
Möller, Florian
Das Max-k-Kantenfärbungsproblem. - Ilmenau. - 29 Seiten
Technische Universität Ilmenau, Bachelorarbeit, 2017

In dieser Arbeit beschäftigen wir uns mit den Max-k-Kantenfärbungsproblem. Dabei betrachten wir die Resultate von Farnik, Kowalik und Socała aus ihrer Arbeit "Beyond the Shannon Bound" und führen die Beweise schneller und verständlicher. Zum Abschluß beschäftigen wir uns noch mit Färbungsalgorithmen um einen Graphen mit den Konzept des Max-k-Kantenfärbungsproblem zu färben.


http://www.gbv.de/dms/ilmenau/abs/883765020moell.txt
Postel, Justus
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.


http://www.gbv.de/dms/ilmenau/abs/880795034poste.txt
Trautmann, Luca
Zwischen geordneten Pfadpartitionen und Schnyderwäldern. - Ilmenau. - 42 Seiten
Technische Universität Ilmenau, Bachelorarbeit, 2017

In dieser Bachelorarbeit werden Zusammenhänge zwischen Schnyderwäldern und geordneten Pfadpartitionen genutzt, um geordnete Pfadpartitionen mit bestimmten Eigenschaften zu finden. Eine geordnete Pfadpartition eines Graphen G ist eine geordnete Partition der Eckenmenge von G, sodass ihre Blöcke Wege induzieren und bestimmte Grad- und Zusammenhangsbedingungen erfüllt sind. Ein Schnyderwald orientiert jede Kante in eine oder zwei Richtungen und markiert jede Richtung mit einer von drei Markierungen. Außerdem hat jede Ecke Ausgangsgrad eins in jeder Markierung, kein Flächenrand enthält einen gerichteten Kreis in einer Markierung und es werden Bedingungen an die zyklische Reihenfolge der Kanten um jede Ecke gestellt. Jeder 3-zusammenhängende ebene Graph besitzt eine geordnete Pfadpartition und einen Schnyderwald, welche einfach auseinander berechnet werden können. Wir nehmen an, dass eine geordnete Pfadpartition gegeben ist und betrachten 3-zusammenhängende ebene Graphen, deren Außenfläche Grad 3 hat. Mit Hilfen von Schnyderwäldern können wir zwei weitere geordnete Pfadpartitionen bestimmen, die verschieden von sind und voneinander abhängen. Diese geordneten Pfadpartitionen werden konsistent zueinander genannt. Da diese drei Pfadpartitionen voneinander abhängen, ist es möglich unter ihnen eine geordnete Pfadpartition mit bestimmten Eigenschaften zu finden. Es ist möglich drei konsistente Pfadpartitionen in Linearzeit zu finden. Wir zeigen, dann eine von drei konsistenten Pfadpartitionen mindestens F/9 Singletons enthält, wenn G F Flächen besitzt und keine davon vom Grad 6 ist. Außerdem ist jede innere Ecke eines Blockes der geordneten Pfadpartition Singleton in einer der zu konsistenten geordneten Pfadpartitionen. Andere Eigenschaften wie die Höhe einer geordneten Pfadpartition konnten nicht verbessert werden.


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


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


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


http://www.gbv.de/dms/ilmenau/abs/87091314Xkulse.txt
Hippmann, Lisa
Färbungskritische signierte Graphen. - 37 Seiten
Technische Universität Ilmenau, Bachelorarbeit, 2016

Ein signierter Graph ist ein Graph, in dem jede Kante mit +1 oder -1 bewertet (signiert) ist. Die vorliegende Arbeit befasst sich mit kritischen signierten Graphen und ihren Färbungen. Kritische signierte Graphen sind besonders interessant, weil sich Färbungsprobleme signierter Graphen oft auf Färbungsprobleme kritischer signierter Graphen zurückführen lassen. So werden zunächst wichtige, bereits bekannte Ergebnisse der chromatischen Zahl signierter Graphen wiedergegeben und anschließend Färbungen kritischer signierter Graphen diskutiert. Den Hauptteil der Arbeit bildet dann der Vergleich gewöhnlicher kritischer Graphen mit kritischen signierten Graphen. Dabei wird sich zeigen, dass viele Eigenschaften kritischer Graphen auch für kritische signierte Graphen gelten. Den Abschluss bilden dann der Zusammenhang sowie die Hajós-Konstruktion kritischer signierter Graphen. Auch hier wird überprüft inwieweit sich Eigenschaften von kritischen Graphen auf kritische signierte Graphen übertragen lassen.


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


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


http://www.gbv.de/dms/ilmenau/abs/809004461heyde.txt
Storch, Patrick
k-kritische Hypergraphen deren Ordnung höchstens 2k-2 ist. - 34 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2014

Ein Hypergraph heißt k-kritisch, wenn seine chromatische Zahl den Wert k hat, jedoch jeder echte Unterhypergraph mit weniger als k Farben färbbar ist. 1963 bewies T. Gallai, dass jeder k-kritische Graph mit einer Ordnung größer als 2k-2 zerlegbar ist, d.h. sein Komplement ist unzusammenhängend. In dieser Arbeit wird ein analoges Resultat für Hypergraphen bewiesen, sowie einige Klassen k-kritischer Hypergraphen untersucht. Desweiteren enthält die Arbeit eine vollständige Liste (mit Beweis) aller 3-kritischen Hypergraphen der Ordnung 5.


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


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


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


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


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


Diegnitz, Sandro
Fast isometrische Einbettung von Graphmetriken in die euklidische Ebene. - 26 S.
Ilmenau : Techn. Univ., Masterarbeit, 2014

In der Arbeit wird gezeigt, dass es möglich ist einen unendlichen, schlichten, zusammenhängenden Graphen so in die Ebene abzubilden, dass er der Einbettungseigenschaft genügt. Der Graph bzw. die Abbildung, welche den Graphen in die Ebene einbettet muss dafür die epsilon-Netz Eigenschaft haben. Außerdem wird der Begriff der r-Kontraktion benutzt um die gewünschten Resultate zu erzielen. Zudem wird gezeigt, dass das Resultat für alle durch Normen induzierte Metriken gilt.


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


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


http://www.gbv.de/dms/ilmenau/abs/750678801haase.txt
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).


http://www.gbv.de/dms/ilmenau/abs/742471993sasse.txt
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}$?


Glock, Stefan
Gebrochene Kantenfärbungen gewichteter Graphen. - 32 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2012

Das f-Kantenfärbungsproblem besteht darin, die Kanten eines gewichteten Graphen mit so wenig wie möglich Farben zu färben, wobei an jedem Knoten v jede Farbe höchstens f(v)-mal vorkommen darf. Zhang, Yu und Liu charakterisierten das f-Matching-Polytop durch lineare Ungleichungen und konnten damit eine Formel für den gebrochenen f-chromatischen Index herleiten. Es wird festgestellt, dass die Beweise lückenhaft sind, und durch Angabe von Gegenbeispielen belegt, dass die Aussagen falsch sind. Auf den Zusammenhang mit der Vermutung von Nakano, Nishizeki und Saito wird ebenfalls eingegangen.


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.


http://www.gbv.de/dms/ilmenau/abs/726550167richt.txt
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"


Goertz, Mathias
Freundliche Eckenzerlegung von Graphen. - 42 S.
Ilmenau : Techn. Univ., Diplomarbeit, 2012

In meiner Diplomarbeit behandelten wir Probleme folgender Art. Eine Gruppe von n Reisenden muss in zwei Teilgruppen aufgeteilt werden, wobei jeder Reisende möchte, dass sich wenigstens so viele Freunde von ihm in seiner Teilgruppe befinden wie in der anderen und er somit keinen Grund hat die Teilgruppe zu wechseln. Dieses Problem lässt sich als Zerlegungsproblem für Graphen formulieren und ist in der Literatur unter dem Namen SATISFACTORY PARTITION bekannt. Wir untersuchten die Frage, ob es zu einem gegebenen Graphen G und zwei Funktionen a, b: V(G) &flech; N eine Zerlegung (A, B) der Eckenmenge von G gibt mit d_G[A] (x)≥a(x) für alle Ecken x A und d_G[B] (x)≥b(x) für alle Ecken x B. Eine solche Zerlegung (A, B) von V(G) heißt (a, b)- Zerlegung von G. Wir haben gezeigt, dass man unter bestimmten Gradbedingungen solche (a, b)- Zerlegungen findet. Eine (a, b)- Zerlegung von G mit a(x)=b(x)= (d_G (x)) 2 für alle x V(G) wird freundliche Zerlegung genannt. Aus unseren Untersuchungen folgt, dass jeder Graph mit Taillenweite mindestens 5 und Minimalgrad mindestens 3 eine freundliche Zerlegung besitzt. Im letzten Abschnitt der Arbeit betrachteten wir Zerlegungen unter bestimmten Färbungsbedingungen. Insbesondere beschäftigten wir uns mit einer bekannten Vermutung von Erd&dblac;os und Lovász aus dem Jahr 1968, welche bis heute ungelöst ist. Seien s, t ≥ 2 natürliche Zahlen und sei G ein Graph mit (G)<(G)=s+t-1, wobei (G) die Cliquenzahl von G ist und (G) die chromatische Zahl von G ist. Dann besitzt G zwei eckendisjunkte Teilgraphen G1 und G2 mit (G_1)≥s und (G_2)≥t.


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


http://www.gbv.de/dms/ilmenau/abs/715329472bosse.txt
Tischer, Mario
Struktur und Eigenschaften 5-chordaler Graphen. - 22 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2012

Bei den 5-chordalen Graphen handelt es sich um die Graphen, in denen jeder induzierte Kreis die Länge 5 hat. In dieser Bachelorarbeit wurden einige Eigenschaften solcher Graphen bewiesen, sowie zwei äquivalente Klassen zu den 5-chordalen Graphen gefungen.


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.


http://www.gbv.de/dms/ilmenau/abs/670361763pflug.txt
Gernandt, Hannes
Ein Zusammenhang zwischen Dominanz, Maximalgrad und Packungen. - 31 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2011

Henning, Löwenstein und Rautenbach zeigten, dass zwischen der Dominanzzahl $\gamma(G)$, der Packungszahl $\rho(G)$ und dem Maximalgrad $\Delta(G)$ eines Graphen $G$ die Beziehung $\gamma(G)\leq \Delta(G)\rho(G)$ besteht. Für $\Delta(G)\leq3$ können sie diese Ungleichung zu $\gamma(G)\leq 2\rho(G)$ verschärfen, sofern $G$ keinen $K_{1,3}$ als induzierten Teilgraphen hat. Wir zeigen, dass auch Graphen G mit $\Delta(G)\leq3$ und $\gamma(G)\in[\frac{n(G)}{4}, \frac{2}{7}n(G)]\cup[\frac{4}{9}n(G), \frac{n(G)}{2}]$ diese Verschärfung erfüllen. Ferner beweisen wir für $\Delta(G)=\Delta\in\N$, dass $\gamma(G)\leq f(\Delta)\rho(G)$ für Graphen $G$ mit $\gamma(G)\in [\frac{n(G)}{\Delta+1}, \frac{f(\Delta)}{f(\Delta)\Delta+1}n(G)]$ und einer Funktion $f:\N\rightarrow\N$, die $f(\Delta)<\Delta$ für alle $\Delta\in\N$ erfüllt, gilt.


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.


http://www.gbv.de/dms/ilmenau/abs/668517506may.txt
Diegnitz, Sandro
Hamiltonkreiserzwingende Mengen in planaren Graphen. - 29 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2011

In der Arbeit wird erklärt was man unter einer Hamiltonkreiserzwingenden Menge und der Hamiltonkreiserzwingenden Zahl versteht. Es werden einige Sätze angegeben, welche klären wie man Hamiltonkreiserzwingende Mengen in Graphen findet und die Hamiltonkreiserzwingende Zahl eines Graphen bestimmt. Desweiteren werden Beweise geführt welche die Hamiltonkreiserzwingenden Zahl in Polyedergraphen, Triangulationen und bestimmten Ringgraphen bestimmen.


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.


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


Heinemann, Katrin
Vergleich von Algorithmen zum Auffinden großer unabhängiger Mengen in Graphen. - 39 S.
Ilmenau : Techn. Univ., Diplomarbeit, 2010

Das Finden unabhängiger Mengen in Graphen lässt sich mit Hilfe verschiedener Algorithmen realisieren. Die Arbeit beschäftigt sich mit einer speziellen Gruppe der Algorithmen. Bei diesen wird sukzessiv, mit einer bestimmten Auswahlregel, ein Punkt ausgewählt und dessen komplette abgeschlossene Nachbarschaft gelöscht. Jene Punkte bilden am Ende eine unabhängige Menge.Die Auswahlregeln setzen sich aus einer Kombination dreier Grundbedingungen zusammen: Erstens die Minimalvalenz. Die zweite Bedingung ist, dass die Anzahl der Kanten, die gelöscht werden, maximal ist. Die dritte Bedingung bewirkt, dass nach dem Löschen der abgeschlossenen Nachbarschaft ein Graph entsteht, der einen Punkt hat, dessen Valenz möglichst gering ist. Dass heißt, es wird der Punkt gesucht, bei dem die Minimalvalenz im Folgegraphen minimal ist. Zum Vergleich dient ein C++ Programm, dass die verschiedenen Ergebnisse ausgibt. Am Ende zeigt sich, dass Auswahlregeln, die mit der ersten Bedingung beginnen, die besten Ergebnisse liefern.


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


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


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


http://www.gbv.de/dms/ilmenau/abs/609916173hartl.txt
Pflugradt, Steffi
Obere Schranken für die Summe der Quadrate der Knotengrade eines dreikreisfreien Graphen mit chromatischer Zahl k. - 18 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2009

In dieser Arbeit betrachten wir die obere Schranke m(n-f(k-2)) für die Summe der Quadrate der Knotengrade eines dreikreisfreien k-chromatischen Graphen mit n Knotenpunkten und m Kanten. Dabei sei f(l), für ein l aus den natürlichen Zahlen, die minimale Anzahl von Knotenpunkten eines Graphen, so dass dieser l-chromatisch ist. Weiterhin ziehen wir Schlußfolgerungen aus dieser Schranke und betrachten sie für Graphen mit chlomatischer Zahl von 2 bis 7 näher.


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.


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


http://www.gbv.de/dms/ilmenau/abs/597485100just.txt
Ribe-Baumann, Elizabeth
Dense graphs with large odd girth. - 45 S.
Ilmenau : Techn. Univ., Diplomarbeit, 2009

Ein Graph G mit ungerader Taillenweite (mindestens) 2k + 1 ist ein Graph, der keine Kreise von ungerader Länge kleiner als 2k + 1 besitzt. Diese Arbeit beschäftigt sich mit der Struktur von Graphen mit beliebiger ungerader Taillenweite 2k+1 und großem Minimalgrad. Frühere Arbeiten haben die Struktur von Graphen mit ungerader Taillenweite 5 und hohem Minimalgrad hinreichend charakterisiert. Als erstes wird eine Zusammenfassung der Kette dazu beitrageneder Ergebnisse gegeben. Einfach formuliert lautet das Hauptresultat: Jeder Graph von Ordnung n mit ungerader Taillenweite 5 und Minimalgrad > n/3 ist 4-färbbar und homomorph mit einem Graphen aus zwei unendlichen Folgen von Graphen. Weiterhin ist eine neue Charakterisierung einer bestimmten Klasse von Teilgraphen (die "generalized pentagons"), die in Graphen mit ungerader Taillenweite 5 und großem Minimalgrad enthalten sind, gegeben. Die wenigen Resultate für Graphen mit ungerader Taillenweite 7 und beliebiger ungerader Taillenweite 2k + 1 für k > 3 werden dann präsentiert. Im Anschluss folgt das Hauptergebnis dieser Arbeit, eine Bestätigung einer Vermutung von Albertson, Chan, and Haas, die besagt: jeder Graph von Ordnung n mit ungerader Taillenweite 2k + 1 und Minimalgrad mindestens 3n/4k ist entweder homomorph dem (2k + 1)-Kreis oder kann durch eine Reihe von Ecken-Duplikationen der Möbiusleiter mit 2k Sprossen erhalten werden. Ein maximaler Graph mit ungerader Taillenweite 2k + 1 ist ein Graph mit ungerader Taillenweite 2k + 1 zu dem keine Kante hinzugefügt werden kann ohne einen ungeraden Kreis von Länge kleiner als 2k + 1 zu erzeugen. Solche maximalen Graphen sind von zentraler Bedeutung im Beweis des Hauptergebnisses, da die wichtigsten mathematischen Werkzeuge in den nachfolgenden Beobachtungen einfache Eigenschaften von maximalen Graphen mit ungerader Taillenweite 2k + 1 sind.


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


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


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


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


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


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


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


http://www.gbv.de/dms/ilmenau/abs/543418138schei.txt
Groß, Olga
Eine untere Schranke für die Unabhängigkeitszahl eines Graphen. - 33 S.
Ilmenau : Techn. Univ., Diplomarbeit, 2006

Durch eine Untersuchung des bekannten Algorithmus' wird in dieser Arbeit eine neue untere Schranke für die Unabhängigkeitszahl eines Graphen bestimmt. Ebenso wird diese Schranke an verschiedenen Graphen getestet und mit bekannten Schranken für die Unabhängigkeitszahl verglichen.


http://www.gbv.de/dms/ilmenau/abs/509655769gross.txt