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