Studienabschlussarbeiten

Anzahl der Treffer: 21
Erstellt: Thu, 28 Mar 2024 23:09:08 +0100 in 0.1220 sec


Friedrich, Timon;
Über drei Arbeiten aus der Spieltheorie. - Ilmenau. - 53 Seiten
Technische Universität Ilmenau, Masterarbeit 2021

Das Ziel dieser Masterarbeit ist es, ausgewählte Arbeiten aus der Spieltheorie, neu darzustellen, weiter zu untersuchen und neue Erkenntnisse zu generieren. Dazu wird folgende Forschungsfrage gestellt: Welche neuen Aussagen können ergänzend zur vorgestellten Literatur bewiesen werden? Um die Frage zu beantworten, werden verschiedene wissenschaftliche Publikationen ausgewertet und ergänzendes Hintergrundwissen zusammengetragen. In Abschnitt 3 sehen wir, dass eine abzählbar unendliche Spielermenge nötig ist, damit ein sogenanntes Wasserfallspiel existiert. Dem Autor ist es gelungen zu beweisen, dass dies für eine beliebige abzählbar unendliche Menge erfüllt ist. Wenn wir beim Austausch der i-ten Aktion durch H bzw. S Gleichheit der Auszahlungsfunktion zulassen, dann können wir zeigen, dass dieses Spiel leicht für eine beliebige abzählbar unendliche Menge konstruierbar ist. Anhand des Untreue-Ehemänner-Problems untersuchen wir in Abschnitt 4 die Auswirkungen der Kommunikationsform. Hierbei stellen wir fest, dass untreue Ehemänner frühestens nach drei Nächten hingerichtet werden können, wenn sich die Frauen nicht über die Treue ihrer Männer unterhalten dürfen. Insgesamt erkennen wir, dass die Anzahl der untreuen Ehemänner für die Argumentation entscheidend ist. Aus diesem Kommunikationsdilemma lernen wir, dass die Wirkung einer Aussage maßgeblich von der Beschaffenheit des Informationskanals abhängt. Dabei nimmt der derzeitige Allgemeinwissensstand eine zentrale Rolle ein. Abschließend können wir mithilfe der evolutionären Spieltheorie feststellen, wie stabil Strategien sind. Dabei erkennen wir, dass das Nash-Gleichgewicht im Urlauberdilemma instabil ist, wenn es zulässig ist, dass sehr große Zahlen notiert werden. Daher ist es, entgegen der klassischen Spieltheorie, sinnvoll von Nash-Gleichgewichten abzuweichen.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.



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.