Zur Berechnung der Verteilung graphentheoretischer Zufallsvariablen

Zusammenfassung Für die in der praktischen Anwendung gebräuchlichsten graphentheoretischen Variablen (minimale Wege, Bäume, Kostenflüsse; maximale Wege, maximale Flüsse) werden in speziellen Fällen diskreter Wahrscheinlichkeitsverteilungen auf der Pfeilmenge (z. B. Ausfallwahrscheinlichkeiten) die zugehörigen (bedingten) Wahrscheinlichkeitsverteilungen berechnet. Dazu werden Nachbarschaftsalgorithmen entwickelt und ein allgemeines Reduktionsverfahren der Zustandsmenge auf wesentliche Zustände hergeleitet.

---

Summary In this paper the (conditional) probability distributions of the most important graph-theoretical variables (minimal path, tree, cost flow; maximal path, maximal flow) are determined in special cases of discrete distributions of the arcs from a graph G. For this purpose some neighbourhood-algorithms are developed and a general method to reduce the set of states to essential states is given.

---

---

Vorgel. v.:J. Nitsche.