Der Ford-Fulkerson-Algorithmus findet einen maximalen Fluss in einem Graphen in der Zeit .

Wenn ein Graph mit mindestens zwei verschiedenen Knoten k-fach kantenzusammenhängend ist, dann gibt es für jedes Paar verschiedener Knoten k-fach kantendisjunkte Pfade zwischen ihnen.

For a network , and any valid flow , there is an -cut with .

Für ein Netzwerk , wenn ein beliebiger Fluss ist und ein beliebiger -Schnitt ist, dann .

Für ein Netzwerk gilt: Wenn ein nicht-maximaler Fluss ist, gibt es einen Pfad von nach in , sodass auf jeder Kante von gilt: .

Wir haben eine Menge von Objekten und färben sie zufällig, jedes unabhängig in eine von Farben (mit gleicher Wahrscheinlichkeit). Die Wahrscheinlichkeit, dass alle Objekte unterschiedliche Farben haben, beträgt mindestens für eine Konstante C (die nicht von abhängt).

Es gibt einen probabilistischen Algorithmus, der prüft, ob ein Graph in der Zeit einen einfachen Pfad der Länge von mindestens hat. Darüber hinaus gibt der Algorithmus immer „NEIN“ aus, wenn der Graph keinen solchen Pfad hat.

Sei ein probabilistischer Algorithmus, der eine Zahl im Bereich ausgibt, s.t. . Dann nehmen Sie eine Durchschnitt von unabhängigen Läufen von können wir eine Schätzung finden, die mit einer Wahrscheinlichkeit von mindestens erfüllt, dass .

Es gibt einen probabilistischen Algorithmus, der testet, ob eine Primzahl ist, und zwar in einer Zeit, die polynomisch in ist.

Wenn ein probabilistischer Algorithmus mit einer Wahrscheinlichkeit von mindestens eine korrekte JA/NEIN-Antwort liefert und wir ihn unabhängig -mal ausführen, ist die Wahrscheinlichkeit, dass er mehr als Mal eine falsche Antwort gibt, kleiner als .