Analyse von serien-parallelen Graphen und deren Entwicklung unter stochastischen Wachstumsregeln

Abstract

Historisch gesehen werden serien-parallele Graphen als abstrahierte elektrische Schaltungen betrachtet. So wie elektrische Bauteile lassen sich auch serien-parallele Graphen sowohl in Serie als auch parallel schalten. Wir gehen der Frage nach, wie viele ebene serien-parallele Graphen es gibt. Die Antwort liefern die Schröder-Hipparchus-Zahlen, die auch die Lösung vieler anderer kombinatorischer Probleme darstellen, zu denen wir Bijektionen finden. Nachher beschäftigen wir uns noch mit Eigenschaften ebener serien-paralleler Graphen, wie der Anzahl der Komponenten und der Anzahl der inneren Knoten in einem zufällig gewählten Graphen mit n Kanten. Über nichtebene serien-parallele Graphen existieren nur asymptotische Resultate. Eine Sonderform sind binäre serien-parallele Graphen, bei denen der Weggrad eines Knotens auf zwei beschränkt ist. Die Catalanzahlen zählen nicht nur deren Anzahl, sondern tauchen auch in anderen Resultaten auf. Danach gehen wir zum stochastischen Wachstum serien-paralleler Graphen über. Wir betrachten das uniforme Bernoulli-Wachstumsmodell und die Eigenschaften, die ein serien-paralleler Graph mit sich bringt, der durch dieses Wachstumsmodell entstanden ist. Darunter zählen die Anzahl innerer Knoten, der Knotengrad der Quelle, die Länge eines zufälligen Pfades, beziehungsweise die Größe eines zufälligen Schnittes und die Anzahl der Pfade von der Quelle bis zur Senke beziehungsweise die Anzahl der Schnitte. Um diese Berechnungen anzustellen, betrachten wir Bäume, bei denen jeder Baumknoten eine Kante im Graphen darstellt. Kurz wird das extrem schnell wachsende hierarchische Wachstumsmodell erwähnt. Ergebnisse haben wir für den Erwartungswert der Anzahl innerer Knoten, des Knotengrades der Quelle und der Länge des Pfades ganz links. Es wird auch ein Wachstumsmodell für die binären serien-parallelen Graphen diskutiert. Wir berechnen den Erwartungswert für die Länge eines zufälligen Pfades und für den Knotengrad der Senke. Dieses Wachstumsmodell wird auf das b-äre Wachstumsmodell, für eine natürliche Zahl b, erweitert. Der Erwartungswert der Länge eines zufälligen Pfades ist Teil unserer Studien.

From a historic point of view, series-parallel graphs were first seen as abstracted electrical circuits. Just as electrical components, series-parallel graphs can be connected in a parallel way as well as in series. We discuss, how many plane series-parallel graphs exist. The answer is given by the Schröder-Hipparchus-numbers, that also give a solution of many other combinatorial problems, so we introduce bijections. Afterwards we consider other properties of plane series-parallel graphs such as the number of components and the number of internal nodes in a randomly chosen series-parallel graph of n edges. Only asymptotic results exist about non-plane series-parallel graphs. A special type of series-parallel graphs are binary series-parallel graphs, where the outdegree of a node is limited to two. The catalan numbers don't only count them, but appear also in other results. Afterwards we turn to the stochastic growth of series-parallel graphs. We discuss the uniform Bernoulli growth model and the properties that come with a series-parallel graph, that was generated by this growth model. Those are the number of internal nodes, the degree of the source, the length of a random path, the size of a random cut, the number of paths from the source to the sink and the number of cuts. To carry out the calculations, we have a look at trees, where each node in the tree represents an edge in the graph. We shortly discuss the fast growing hierarchical growth model. We calculate the expected value of the number of internal nodes, the degree of the source and the length of the leftmost path. A growth model for binary series-parallel graphs is also introduced. We calculate the expected value for the length of a random path and for the degree of the sink. We extend the binary growth model to a b-ary growth model for a positive integer b. The expected value of the length of a random path are part of our studies.