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.
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.
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.
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.
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.
"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.
Ü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.
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.