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.0320 sec


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.