Direkt zum Inhalt

Lexikon der Mathematik: Netzwerk

ein zusammenhängender gerichteter Graph N mit genau einer Quelle, genau einer Senke und einer Kapazitätsfunktion.

Dabei heißt eine Ecke uE(N) mit \({d}_{N}^{-}(u)=0\) Quelle und eine Ecke vE(N) mit \({d}_{N}^{+}(v)=0\) Senke von N. Ist B(N) die Bogenmenge von N, so nennt man eine Funktion c : B(N) → ℝ mit c(k) ≥ 0 für alle kB(N) Kapazitätsfunktion, und c(k) heißt Kapazität des Bogens k.

Ein Netzwerk N mit der Quelle u, der Senke v und der Kapazitätsfunktion c kann man sich z. B. als ein Straßensystem vorstellen, wobei c(k) die Transportkapazität der Straße k bedeutet. Es stellt sich nun die natürliche Frage, wieviel man unter Beachtung der Kapazitätseinschränkung c von der Quelle u zur Senke v transportieren kann. Zur Untersuchung solcher und ähnlicher Probleme hat sich der sogenannte Netzwerkfluß als sehr nützliches Instrument erwiesen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos