Bachelor Theses and Master Theses

In dieser Diplomarbeit betrachten wir ein Problem, welches von Golumbic, Peled und Rotics aufgeworfen wurde. Es behandelt das Verhältnis zwischen einem Komplexitätsmaß für Boolesche Funktionen und einer Problematik der Graphenüberdeckung. Genauer gesagt, setzt das Problem die sogenannte Readability von monotonen Booleschen Funktionen in Verbindung mit Kantenüberdeckungen von Graphen, die solchen Funktionen zugeordnet werden, durch Kantenmengen vollständiger bipartiter Teilgraphen. - Eine monotone Boolesche Funktion hat eine Readability von höchstens k, wenn sie durch eine Formel dargestellt werden kann, in welcher jede Variable höchstens k mal vorkommt. Wir ordnen einer monotonen Booleschen Funktion F einen Graph G zu, dessen Knotenmenge die Menge von Variablen von F ist und die Minimalterme von F genau den maximalen Cliquen von G entsprechen. - Golumbic et al. stellten die Frage, ob jede monotone Boolesche Funktion F, deren zugehöriger Graph G dreiecksfrei ist, durch eine hinsichtlich der Readability optimale Formel p dargestellt werden kann, so dass p einer Kantenüberdeckung c von G durch Kantenmengen vollständiger bipartiter Teilgraphen entspricht. Hierbei ist die Anzahl, wie oft eine bestimmte Variable x in p vorkommt, gleich der Anzahl von vollständigen bipartiten Teilgraphen, welche von c benutzt werden und den Knoten x enthalten. - In Ihrem Manuskript bewiesen Golumbic et al. die Beziehung zwischen der Readability und der Problematik der Graphenüberdeckung für eine spezielle Folge von Graphen. In Abschnitt 2 beweisen wir als unser erstes Hauptresultat, dass die Argumente von Golumbic et al. noch für eine andere Folge von Graphen funktionieren. Darüber hinaus bearbeiten wir in Abschnitt 3 einen Spezialfall dieser Problematik, welcher Formeln einer eingeschränkten Struktur behandelt, dessen zugehörige Graphen dreiecksfrei sind.

Zielstellung dieser Arbeit ist es, die Frage zu klären, welches von 2 Verfahren für die Belieferung und Abrechnung von Strom für Kleinkunden aus Sicht eines Verteilnetzbetreibers besser geeignet ist. Durch die Erläuterung des Netznutzungsmodells in der Einleitung werden zunächst wichtige Zusammenhänge am Strommarkt deutlich. Im Anschluss werden die einzelnen Verfahren vorgestellt und mit Daten eines speziellen Geschäftsjahres in Excel durchgerechnet. Im 3. Kapitel wurden verschiedene Situationen und die Auswirkungen auf beide Verfahren betrachtet. Dabei ist deutlich geworden, dass im synthetischen Verfahren das Risiko besteht, dass Kosten, die durch Prognoseungenauigkeiten entstehen, nicht genau auf die Verursacher umgewälzt werden. Dieses Risiko tritt im analytischen Verfahren nicht ein. Durch verschiedene Fallbetrachtungen sind die Fälle herausgearbeitet worden, in denen für den Verteilnetzbetreiber Gewinne oder Verluste eintreten. Die Größenordnung der Verluste und Gewinne war letztendlich ausschlaggebend, dass sich das analytische Verfahren aus Sicht des Verteilnetzbetreibers als das bessere herausgestellt hat.

Erstes Kapitel ist allgemeine Einleitung. Darauf folgt ein Kapitel mit Grundlagen der Codierungstheorie. Das Kapitel 3 beschäftigt sich mit Codes und Tippsystemen, worauf in Kapitel 4 eine Verallgemeinerung dessen und eine Betrachtung mit Hilfe der Graphentheorie folgt. Insbesondere geht es um die Einführung des "football pool problem" als Dominanzproblem. Es folgt die Einführung einer eigenen minimalen Tippmenge und dem Aufstellen unterer und oberer Schranken. Kapitel 5 gibt einen Überblick über die bis dato vorliegenden Verbesserungen der in der Literatur betrachteten Systeme und damit den minimalen Tippmengen. Abschließend erfolgt in Kapitel 6 eine Betrachtung des Problems als lineares ganzzahliges Optimierungsproblem.

Die Dominanzzahl eines Graphen ist die minimale Anzahl von Knoten in einer Menge D, für die jeder Knoten des Graphen entweder selber in der Menge D liegt oder einen Nachbarn in D besitzt. - In dieser Arbeit werden reguläre Graphen mit großer Taillenweite betrachtet, das heißt, jeder Knoten des Graphen hat die gleiche Anzahl von Nachbarn und ein kürzester Kreis im Graphen hat eine hinreichend große Länge. - Es wird eine neue Strategie entwickelt, durch die neue obere Schranken für die Dominanzzahl dieser Graphenklasse bewiesen werden können.

Das Kantenfärbungsproblem für Graphen ist ein NP-schweres Problem. Für einen Multigraphen G ist der chromatische Index c(G) - die minimale Anzahl an benötigten Farben - nach unten beschränkt durch den Maximalgrad D(G) und nach oben durch die Summe D(G)+m(G) aus dem Maximalgrad und der maximalen Kantenvielfachheit von G. Aus der Literatur ist eine Vielzahl weiterer oberer Schranken für den chromatischen Index bekannt, für die sich mittels effizienter Färbungsalgorithmen entsprechende Färbungen konstruieren lassen. - Auf der Basis der klassischen Umfärbungsmethoden an sogenannten Fächern wird im ersten Teil dieser Arbeit eine neue obere Schranke - die Fächerzahl - eingeführt, welche gleichzeitig eine Vielzahl der bekannten Schranken verbessert. Ein entsprechender Färbungsalgorithmuss, der diese Fächerzahl effizient realisiert, wird ebenfalls angegeben. - Im zweiten Teil der Arbeit wird die Güte der bereits erwähnten klassischen Schranke D(G)+m(G) von Vizing in Abhängigkeit der beiden benötigten Parameter D(G) und m(G) untersucht. Dabei werden Bereiche charakterisiert, für die Graphen G mit c(G)=D(G)+m(G) konstruiert werden können. Diese Charakterisierung ist zudem vollständig, falls die Goldbergvermutung stimmt. Für weitere Bereiche kann auch ohne Goldberg gezeigt werden, dass die Vizing-Schranke nicht erreichbar und sogar beliebig schlecht wird.