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.
Several algorithms have been proposed for the testing of series-parallel graphs in linear time. We give our alternate algorithms for testing series-parallel graphs, their tree decompositions, and the independence number when the input is undirected biconnected series-parallel graphs, which run (approximately) linearly in polynomial time.
A classical topic in the theory of random graphs is the probability of at least one isolated vertex in a given random graph. An isolated node has a huge impact on social networks which can be given by a random graph. We present a distribution on the number of isolated vertex using the probability generating function. We discuss the relationship between isolated edges and extended cut polynomials, extended matching polynomials using the principle of inclusion exclusion. We introduce an algorithm based on colored graphs for general graphs. We apply this to the components of a graph as well. Finally, we implement the idea on a special class of graphs like cycle, bipartite graph, path, and others. We discuss recursive procedure based on the analogous coloring rules for ladder and fan graphs.
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.
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.
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.