Peer-to-Peer-Netzwerke: Algorithmen und Methoden

der ausgehenden Kanten eines Knotens; der Eingrad ist die Anzahl der eingehenden Kanten eines Knotens. Spricht man nur vom Grad eines gerichteten Graphen, so ist zumeist der Ausgrad gemeint.

    In Abbildung A.2 ist der Graph mit der Kantenmenge E = {(1, 3), (2, 1), (2, 3), (2, 5), (3, 1), (3, 2), (3, 5), (4, 5)} dargestelit.
    Abb. A.2. Ein gerichteter Graph.
    Gerichtete Graphen sind besonders geeignete Zeigerstrukturen zu beschreiben, wie sie zum Beispiel im Internet bei Verbindungen mit UDP vorkommen. Auch Datenstrukturen mit Zeigern lassen sich dadurch darstellen.
    • Der gerichtete Multigraph verfugt als Kantenmenge uber eine Multimenge, in der Kanten mehrfach vorkommen konnen. Zusatzlich sind Selbstkanten, wie (u, u) (Schleifen) erlaubt. Abbildung A.3 zeigt den Graph mit der Kantenmenge E _ {(1, 3), (1, 3), (1, 3), (2, 1), (2, 1), (2, 2), (2, 2), (2, 3), (2, 3), (3, 2), (3, 4)}.
    Abb. A.3. Ein gerichteter Multi graph.
    Gerichtete Multigraphen entstehen zum Beispiel, wenn man mehrere Verbindungen zu Knoten (z.B. TCP-Verbindungen) unterhalt. Die Selbstkanten spielen eine groBe Rolle bei Zustandsubergangsgraphen.

    • Gewichtete Graphen: Jeder dieser Graphtypen kann auch als gewichteter Graph betrachtet werden. Hierzu wird jeder Kante e eine Zahl w(e) zugewiesen. In Abbildung A.4 werden die Gewichte gemaB Tabelle A.1 verwendet.

    Zumeist beschreibt das Gewicht einer Kante den Abstand zweier Knoten. Es kann sich aber auch um eine Kapazitat, das Nachrichtenaufkommen, u.v.a. handeln.
    Abb. A.4. Ein gewichteter gerichteter Graph.
Pfade and Zusammenhang
    Ein ungerichteter Pfad in einern ungerichteten Graphen ist eine Folge von Kanten, in deco jeder Kante eine Richtung so zugewiesen wird, dass der Endknoten and der Anfangsknoten zweier aufeinanderfolgender Kanten gleich sind. Ungerichtete Pfade kommen zum Beispiel in der Paketweiterleitung im Internet vor. Ein ungerichteter Graph ist zusammenhangend, wenn es zwischen alien Knoten einen ungerichteten Pfad gibt. Die Ldnge eines Pfades ist die Anzahl der Kanten. Die Lange des minimalen Pfades zweier Knoten ist der Abstand der Knoten. Das Gewicht eines Pfades ist das Gewicht der einzelnen Kanten. Der Durchmesser eines Graphen ist der maximale Abstand zweier Knoten.
    Ein gerichteter Pfad in einem gerichteten Graphen oder einem Multigraphen ist eine Folge von Kanten, in der Endknoten einer Kante mit dem Startknoten der darauf folgenden Kante ubereinstimmt. Ein gerichteter Graph oder ein Multigraph ist stark zusammenhangend, wenn es zwischen alien Knoten einen gerichteten Pfad gibt. Mit Hilfe der gerichteten Pfade wird der Abstand and Durchmesser von gerichteten Graphen and Multigraphen analog wie im ungerichteten Graph definiert.

    Ein ungerichteter Pfad in solchen Graphen ist ein gerichteter Pfad, in dem neben den Kanten des Graphen zusatzlich auch die entsprechenden (evtl. nicht im Graphen vorhandenen) Ruckwartskanten gewahlt werden konnen. Ein Graph ist schwach zusammenhangend, wenn es zwischen alien Knoten einen ungerichteten Pfad gibt.
Metrik
    Die Metrik wird durch gewichtete gerichtete oder ungerichtete Graphen mit Oder ohne Selbstkanten beschrieben. Oft werden hierzu vollstandige Graphen betrachtet, in denen Kante and Selbstkante vorhanden sind. Diese unterscheiden sich nur durch die Gewichtung. Folgende vier Eigenschaften mussen fur die Gewichtung gelten, damit sie als Metrik bezeichnet werden kann. Zur Vereinfachung schreiben wir statt w((u, v)) nur w(u, v):
    1. Selbstkanten, soweit vorhanden, haben Gewicht 0: w(u, u) = 0 fur alle Knoten uEV
    2. Fur alle Kanten gilt w(u, v) > 0 fur u v
    3. Symmetrie: w(u, v) = w(v, u) fur alle u, v E V
    4. Die Dreiecksungleichung: w(u, v) < w(u, z) + w(z, v) fur alle u, v, w E V, siehe auch Abbildung A.5
    Abb. A.5. Die Dreiecksungleichung.

A.3 Wahrscheinlichkeitstheorie
    Ein Zufallsexperiment beschreibt einen Vorgang, der ein nicht vorhersagbares Ergebnis zur Folge hat. Ein Wahrscheinlichkeitsraum besteht aus einer Ergebnismenge S7, einer Ereignisalgebra (zum Beispiel der Potenzmenge der Ergebnismenge S7) and einem WahrscheinlichkeitsmaB Pr auf -Y. Fur das WarscheinlichkeitsmaB mussen die folgenden Eigenschaften gelten:
    • Pr [.f7] = 1
    • Fur paarweise disjunkte Ereignisse Al, A2 ... gilt:

    Die Gesamtwahrscheinlichkeit aller Ereignisse ist also Eins. Die Wahrscheinlichkeit der Vereinigung von disjunkten Ereignissen entspricht der Summe der Einzelwahrscheinlichkeiten.
    Eine Zufallsvariable ist eine Funktion X : 2 - Q', wobei hier