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