Refine
Document Type
- Master's Thesis (6)
- Bachelor Thesis (5)
- Diploma Thesis (2)
- Final Report (1)
Keywords
- Graphentheorie (14) (remove)
The Tutte polynomial is an important tool in graph theory. This paper provides an introduction to the two-variable polynomial using the spanning subgraph and rank-generating polynomials. The equivalency of definitions is shown in detail, as well as evaluations and derivatives. The properties and examples of the polynomial, i.e. the universality, coefficient relations, closed forms and recurrence relations are mentioned. Moreover, the thesis contains the connection between the dichromate and other significant polynomials.
Die Diplomarbeit beschäftigt sich mit aktuell gängigen mathematischen Methoden und Verfahren numerischer Löser zur Bearbeitung groÿer Optimierungsprobleme der Energieversorgung, welche überwiegend zur Klasse der gemischt-ganzzahligen nichtlinearen Optimierungsprobleme gehören. Es wird ein Beispiel für solch ein Problem modelliert und dessen Ergebnisse ausgewertet. Die Grundlage liefert ein umfangreiches Projekt des DFG-Forschungszentrums Matheon, welches sich mit der Neugestaltung des deutschen Gasnetzes bezüglich der zukünftigen Bedarfs- und Rechtslage beschäftigt
In dieser Arbeit wird die Klasse der Chordalen Graphen vorgestellt. Dafür werden zunächst einige Grundlagen zu den Chordalen Graphen vorgestellt wie wichtige Definitionen, Eigenschaften, einige Sätze zu dieser Graphenklasse und ein Überblick über wichtige Literatur. Anschließend wird beschrieben, wie man Chordale Graphen erkennen kann und mit welchen anderen Graphenklassen sie im Zusammenhang stehen. Abschließend wird noch auf zwei der bekanntesten Algorithmen für Chordale Graphen eingegangen.
Es ist möglich, Graphen und Netzwerke durch Bewertung der Kanten mit Hilfe des Zentralitätsindizes Betweenness in Cluster zu zerlegen. Die Berechnung der Betweennesswerte für jede Kante eines betrachteten Graphen benötigt eine Zeit von O(n2m) für m >> n. In dieser Arbeit wird eine schnellere Methode mit einer Zeitkomplexität von O(nm) für die Berechnung eines Betweenness Rankings nach Newman und unabhängig nach Brandes vorgestellt und implementiert. Es wird ein Clusteralgorithmus nach Newman und Girvan auf Basis des Index Kanten-Betweenness und mit einer Laufzeit von O(nm2) vorgestellt und es werden verschiedene Graphen damit geclustert. Die Arbeit ist restringiert auf schlichte, ungerichtete Graphen.
Für die Analyse hochkomplexer CID-Spektren und die Aufklärung von Zusammensetzungen verschiedener Einzelverbindungen aus Gemischen in nicht CID-Spektren einer FT-ICR-Massenspektrometrie, können Graphen für die Analyse genutzt werden. Die vorliegende Masterarbeit beschäftigt sich mit der Etablierung einer Methode die hochkomplexen MS-Daten ohne die Notwendigkeit von Expertenwissen automatisiert zu Analysieren. Für die Darstellung werden weiterhin Visualisierungsmöglichkeiten der Graphen und das Alignment der Graphen mit einem selbst implementierten Java-Programm vorgestellt.
In this master thesis, we define a new bivariate polynomial which we call the defensive alliance polynomial and denote it by da(G; x; y). It is a generalization of the alliance polynomial and the strong alliance polynomial. We show the relation between da(G; x; y) and the alliance, the strong alliance, the induced connected subgraph polynomials as well as the cut vertex sets polynomial. We investigate information encoded about G in da(G; x; y). We discuss the defensive alliance polynomial for the path graphs, the cycle graphs, the star graphs, the double star graphs, the complete graphs, the complete bipartite graphs, the regular graphs, the wheel graphs, the open wheel graphs, the friendship graphs, the triangular book graphs and the quadrilateral book graphs. Also, we prove that the above classes of graphs are characterized by its defensive alliance polynomial. We present the defensive alliance polynomial of the graph formed of attaching a vertex to a complete graph. We show two pairs of graphs which are not characterized by the alliance polynomial but characterized by the defensive alliance polynomial.
Also, we present three notes on results in the literature. The first one is improving a bound and the other two are counterexamples.
Diese Arbeit befasst sich mit der Entwicklung eines epochenübergreifenden Aufgaben- und Objektmanagementsystems zur prozeduralen Generierung von Narrativen. Dabei wurde ein Questsystem als Managementinstanz für Aufgaben und Objekte entwickelt sowie ein auf L-Systemen und der Graphentheorie basierender Algorithmus zur prozeduralen Generierung Narrativen entwickelt.
Social media platforms play an increasing role in marketing, politics and police affairs, because they can strongly influence opinions. So called “opinion leaders” exert their influence in a given network and shape the opinions of other users. Identifying central nodes in a social graph has been of interest for decades. However, not all centrality measures were developed for social media platforms. They were built for social graphs, which did not include additional metrics (e.g. “likes”, “shares”). Nevertheless, these metrics play a crucial role on modern platforms. Hence, outdated measures need to be adjusted and additional metrics need to be integrated to ensure the best possible results.