http://www.tu-ilmenau.de

Logo TU Ilmenau


Arbeitsgruppe
Diskrete Mathematik und Algebra


Foto des Ansprechpartners
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: Tue, 12 Dec 2017 23:06:55 +0100 in 0.0298 sec


Hahnemann, Susanne
Die minimale Kantenbelastung in Raupen. - 35 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2010

Diese Arbeit beschäftigt sich mit der minimalen Kantenbelastung in Raupen gleicher Ordnung. Dabei wird versucht die maximale Kantenbelastung von einer Raupe G in einer Raupe T zu minimieren, indem beide nach dem gleichen Schema nummeriert werden und anschließend die Knoten mit gleicher Nummer bijektiv aufeinander abgebildet werden. Zum Vergleich werden auch noch zwei weitere Schemata getestet und es werden Aussagen über diese getroffen. Außerdem werden Gesetzmäßigkeiten für Spezialfälle der Raupe gezeigt. Schließlich werden noch obere Schranken für die Kantenbelastung vorgestellt.


http://www.gbv.de/dms/ilmenau/abs/636740765hahne.txt
Aschenbach, Daniel
Zur Unabhängigkeitszahl in Graphen. - 37 S.
Ilmenau : Techn. Univ., Bachelor-Arbeit, 2010

Die Unabhängigkeitszahl eines Graphen zu berechnen ist, wie sich im Laufe der Zeit herausgestellt hat, eine äußerst schwierige Aufgabe. Gerade deshalb sind möglichst genaue Abschätzungen jener von großem Interesse. In dieser Arbeit wird zum einen untersucht, wie sich die Unabhängigkeitszahl in einem n-eckigen Graphen, in welchen der Maximalgrad auf drei beschränkt ist, durch sum(f(di , ti), i=1..n) abschätzen lässt, wobei di die Gradzahl und ti die Dreieckszahl der jeweiligen Ecke i wiederspiegeln. Dabei ist die Funktion f rekursiv durch f(0,0) = 1 sowie f(d,t) = 1/(d+1) für t >=binomial(d,2) und f(d,t) = (1+(d^2-d-2t)f(d-1,t))/(d^2+1-2t) für t <binomial(d,2) gegeben. Zum anderen wird untersucht, welche Probleme auftreten, wenn anstelle des Maximalgrades die Dreieckszahl, eines jeden Eckpunktes in G, auf zwei beschränkt wird. Es wird ausführlich auf die dabei aufgetretenen Schwierigkeiten eingegangen.


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.


http://www.gbv.de/dms/ilmenau/abs/635331888heine.txt
Bechmann, Marcel
Kantenfärbungen Gewichteter Multigraphen. - 51 S.
Ilmenau : Techn. Univ., Diplomarbeit, 2010

Kantenfärbungen ungerichteter Graphen sind ein vielbehandeltes Problem der Graphentheorie. Die vorliegende Arbeit verallgemeinert diese Problemstellung auf fraktionelle f Kantenfärbungen. Der f chromatische Index eines Graphen wird dabei als binäres lineares Optimierungsproblem angesehen welches reell relaxiert wird. Daraus ergeben sich in natürlicher Weise Begriffe und Sätze, die ähnlich sind zu denen der klassischen Kantenfärbungen. Einige zentrale Resultate werden auf gebrochene Kantenfärbungen übertragen und der gebrochene f chromatische Index als effizient realisierbare Schranke in Verbindung mit dem f chromatischen Index gebracht.


http://www.gbv.de/dms/ilmenau/abs/632181923bechm.txt
Schäfer, Philipp Matthias
Two topics in discrete convexity. - 25 S.
Ilmenau : Techn. Univ., Diplomarbeit, 2009

Abstrakte Konvexität behandelt Mengensysteme, die einige Eigenschaften mit den klassischen konvexen Mengen des $\mathbb{R}^n$ gemeinsam haben. Diskrete Strukturen, wie Graphen und partiell geordnete Mengen, induzieren konvexe Räume und verwandte mathematische Strukturen auf deren Grundmengen auf verschiedenste Art und Weise. - Der erste Teil behandelt sogenannte Strict Betweenness Relationen. Zwei Relationen dieser Art werden von Graphen und partiell geordneten Mengen induziert. Es wird gezeigt für welche Strict Betweeneess Relationen sowohl Graphen als auch partiell geordnete Mengen existieren, die diese induzieren. Das Hauptresultat gibt an, dass die Komponenten bzw. schwachen Komponenten von Graphen und partiell geordneten Mengen eines solchen induzierenden Paares eine schichtartige Struktur haben müssen. Es wird weiter gezeigt, dass unter gewissen Minimalitätsforderungen das induzierende Graph-Poset-Paar einer Strict Betweenness Relation eindeutig ist. - Ein weiteres Konzept von Konvexität, $\Delta$-Konvexität auf Kantenmengen von Graphen, wird im zweiten Teil behandelt. Im Speziellen werden Graphklassen, deren minimale $\Delta$-Hüllenmengen ihre spannenden Bäume sind, betrachtet. Zunächst werden zwei Resultate von Jamison \cite{Jamison} präsentiert. Dann werden einige weitere Beispiele solcher Klassen aufgezeigt. Zum Schluss wird gezeigt, dass alle Graphen, deren minimale $\Delta$-Hüllenmengen ihre spannenden Bäume sind, eine bestimmte Eigenschaft haben, um damit zu zeigen, dass die Vermutung Jamisons, dass alle null-homotopischen Graphen zu dieser Klasse gehören, falsch ist.


http://www.gbv.de/dms/ilmenau/abs/612915433schae.txt
Hartleb, Christopher
Beiträge zu unteren Schranken für die Unabhängigkeitszahl eines Graphen in Termen von Knotenzahl und Kantenzahl. - 34 S.
Ilmenau : Techn. Univ., Diplomarbeit, 2009

Der Autor konstruiert multilineare untere Schranken für die Unabhängigkeitszahl beliebiger Graphen, deren Werte auf der Hauptdiagonale des zulässigen Bereiches monoton wachsen. - Desweiteren berechnet er durch eine Verfeinerung MIN-Algorithmus untere Schranken in dreiecksfreien Graphen.


http://www.gbv.de/dms/ilmenau/abs/609916173hartl.txt
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.


Mann, Sebastian
Anwendung kryptographischer Verfahren für Privacy Enhancement in multimedialen Anwendungen. - 85 S.
Ilmenau : Techn. Univ., Diplomarbeit, 2009

Zielsetzung der vorliegenden Arbeit ist, Sinn und Einsatzmöglichkeiten kryptographischer Verfahren für Privacy Enhancement in muldimedialen Anwendungen zu untersuchen und die Verfahren im Anwendungsbereich der Nutzerauthentifizierung weiter zu entwickeln. Zu diesem zweck wird in der Arbeit ein Protokoll entwickelt, welches eine Pseudonymisierung von Nutzern ermöglichen soll, ohne dabei Rückschlüsse auf die reale Identität des Nutzers zuzulassen. Dieses Protokoll wird mit mathematischen und kryptoanalytischen Verfahren und Methoden untersucht. Weiterhin wird eine Anwendung dieses Authentifizierungsprotokolls in Form eines speziellen Abstimmungsverfahrens beschrieben und konzeptionell umgesetzt, die zur Überprüfung der Funktionalität des Authentifizierungsprotokolls dient.


http://www.gbv.de/dms/ilmenau/abs/608236292mann.txt
Just, Elke
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.


http://www.gbv.de/dms/ilmenau/abs/597485100just.txt
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.


http://www.gbv.de/dms/ilmenau/abs/594911753ribe.txt