Theses

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


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.