Refine
Document Type
- Bachelor Thesis (2)
- Master's Thesis (1)
Year of publication
- 2012 (3) (remove)
Language
- German (3)
Keywords
- Graphentheorie (3) (remove)
Institute
Diese Arbeit beschäftigt sich mit verschiedenen Zuverlässigkeitsproblemen in gerichteten Netzwerken. Dabei wird speziell die s,t-Zuverlässigkeit und die s,T-Zuverlässigkeit betrachtet. Dazu werden verschiedene Berechnungs- und Reduktionsmöglichkeiten vorgestellt und anhand von Testrechnungen miteinander verglichen. Außerdem werden für spezielle Graphenklassen explizite und rekursive Formeln angegeben.
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.