Netzwerke
Graphentheorie
Ein Graph ist ein Modell einer realen Gegebenheit, das deren relevante Objekte (=Knoten) und die relevanten Verbindungen (=Kanten) zwischen den Objekten abbildet. Es gibt sehr viele Situationen, die mittels Graphen modelliert werden. Hier eine kleine Auswahl:
- wirtschaftliche oder soziale Beziehungen
- Kommunikationsnetze wie das Internet
- Verkehrsnetze: Straßennetze, U-Bahnnetz, Flugverbindungen
- Stromverteilungsnetze
- Nahwärmenetze
- Molekülstrukturen
- Stammbäume
- Ordnerstrukturen
Ein ungerichteter Graph besteht einfach aus einer Menge von Knoten (Ecken, Punkt, englisch vertices, nodes, points) und einer Menge von Kanten (Bögen, engl. edges, links, lines). Eine Kante wird durch ein ungeordnetes Paar von Knoten, den Endknoten der Kante, angegeben und als Linie gezeichnet.
In Abbildung Abbildung 1 ist ein ungerichteter Graph mit 5 Knoten und 6 Kanten dargestellt.
Ein gerichteter Graph (englisch directed graph) besteht aus einer Menge von Knoten und einer Menge von gerichteten Kanten, die durch geordnete Paare von Knoten, den Anfangsknoten und den Endknoten, bestimmt sind. Die gerichteten Kanten werden statt durch Linien durch Pfeile gekennzeichnet, wobei der Pfeil von ihrem Anfangs- zu ihrem Endknoten zeigt.
In Abbildung Abbildung 2 ist ein gerichteter Graph mit 4 Knoten und 5 gerichteten Kanten dargestellt.
Netzwerke
Ein (Fluss- oder Transport-) Netzwerk (engl. network) ist ein zusammenhängender, gerichteter Graph, bei dem jede Kante einen Fluss aufnehmen kann und jede Kante eine Kapazität (allgemeiner: untere und obere Flussschranken) für den Fluss hat. Die Menge des Flusses auf einer Kante kann die Kapazität der Kante nicht überschreiten. Ein Fluss muss die Einschränkung erfüllen, dass die Menge des Flusses in einen Knoten gleich der Menge des Flusses aus ihm heraus ist. Ein externer Fluss in oder aus einem Knoten ist erlaubt und wird neben dem Knoten oder als Fluss auf einer zusätzlichen Kante des Knotens angegeben.
Ein Fluss-Netzwerk (engl. flow network) ist ein Netzwerk, dessen Kanten zusätzlich Kosten pro Mengeneinheit des Flusses zugeordnet sind. Typischerweise will man einen Fluss durch die Kanten bestimmen, der den Einschränkungen des Netzwerks genügt und dessen Gesamtkosten minimal sind.
Vorzeichenkonventionen:
- Ein positiver Fluss fließt in Pfeilrichtung, ein negativer Fluss fließt gegen die Pfeilrichtung.
- Ein positiver externer Fluss fließt dabei in den Knoten, ein negativer externer Fluss bedeutet, dass der zugehörige positive Fluss aus dem Knoten herausfließt.
Default-Werte: Falls einem Knoten oder einer Kante keine Parameterwerte zugeschrieben werden, gelten Default-Werte.
Abbildung Abbildung 3 zeigt ein Fluss-Netzwerk. Die Kanten sind mit ihren Kapazitäten und Kosten beschriftet. Die Knoten sind mit ihren externen Flüssen beschriftet.
Anwendungen: Ein Netzwerk kann verwendet werden, um den Verkehr in einem Computer- oder Straßennetzwerk, Flüssigkeiten in Rohren, Energien in Leitungen, Ströme in einem elektrischen Stromkreis oder Ähnliches zu modellieren, solange “etwas” durch ein Netzwerk von Knoten “fließt”.
Energienetzwerke
In Energienetzwerken ist der Fluss gleich der (elektrischen oder thermischen) Leistung, die z. B. in kW angegeben wird. Die Kapazität ist die maximale Leistung, die über die Kante fließen kann. Die externen Flüsse sind die Leistungen, die in den Knoten eingespeist oder entnommen werden. Die oben erwähnte Knotenregel, dass die Menge des Flusses in einen Knoten gleich der Menge des Flusses aus ihm heraus ist, entspricht der Energieerhaltung.
Der Leistung (Last, Einspeisung, Erzeugung etc.) \(p\) auf einer Kante ist in vielen Anwendungen zeitabhängig, also eine Funktion \(p(t)\) mit kontinuierlicher Zeit \(t\). Die Knotenregel gilt dann zu jedem Zeitpunkt \(t\). Ein zeitkontinuierlicher (=analoger) Leistungsverlauf \(p(t)\) wird für datentechnische Anwendungen typischerweise in stückweise konstante Werte \(p_i\) gesampelt, siehe Beispiel: (Re-)Sampling.