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.
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.
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.
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).
Ü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}$?
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.
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"
Ü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.
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.
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.