| dbpprop:abstract
|
- In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, except when it is a source, which has more outgoing flow, or sink, which has more incoming flow. A network can be used to model traffic in a road system, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.
- Ein Netzwerk N=(V, E, s, t, c) ist in der Graphentheorie ein gerichteter Graph ohne Mehrfachkanten mit zwei ausgezeichneten Knoten, einer Quelle s und einer Senke t aus V sowie einer Kapazitätsfunktion c, die jeder Kante (x,y) aus E eine nicht-negative, reellwertige Kapazität c(x,y) zuweist. Ein s-t-Fluss ist eine Funktion f, die jeder Kante (x,y) im Netzwerk einen nicht-negativen reellen Flusswert f(x,y) zuweist. Dabei müssen folgende Bedingungen erfüllt sein: Kapazitätsbeschränkung: Der Fluss einer Kante ist höchstens so groß wie die Kapazität auf der Kante, d.h. es gilt <math>\forall (x,y)\in E:f(x,y)\leq c(x,y)</math>. Flusserhaltung: Abgesehen von der Quelle s und der Senke t muss in jeden Knoten genau so viel hineinfließen wie herausfließen, d.h. <math>\forall x\in V \setminus \{ s,t \} :\sum_{y \in x^+}f(x,y)=\sum_{y\in x^-}f(y,x)</math> Dabei sind <math>x^+</math> und <math>x^-</math> die Mengen der Knoten die mit x durch eine (von x aus gesehen) ausgehende bzw. eingehende Kante verbunden sind. Der Wert val(f) eines s-t-Flusses f ist die Summe der Flusswerte der eingehenden Kanten abzüglich der Flusswerte der ausgehenden Kanten der Senke t, <math>val(f) = \sum_{y\in t^-}f(y,t) - \sum_{y\in t^+}f(t,y)</math>. Dass der Wert des Flusses genauso gut an der Quelle s als Summe der ausgehenden abzüglich der eingehenden Flusswerte an s berechnet werden kann, folgt aus Flusserhaltungsbedingung. Es gilt <math>val(f) = \sum_{y\in s^+}f(s,y) - \sum_{y\in s^-}f(y,s)</math>. Eine Teilmenge der Knoten in einem Netzwerk, die s aber nicht t enthält, nennt man einen Schnitt. Die Kapazität eines Schnittes ist die Summe der Kapazitäten der aus dem Schnitt herausführenden Kanten. Laut dem Max-Flow-Min-Cut-Theorem kann der Wert eines maximalen Flusses im Netzwerk nicht größer als die Kapazität eines beliebigen und somit auch eines minimalen Schnittes sein. Das Restnetzwerk bezüglich eines zulässigen Flusses ist ein Graph, der alle Kanten des ursprünglichen Netzwerkes enthält, mit um den jeweiligen Flusswert verminderten Kantenkapazitäten.
- Toky v sítích jsou v rámci teorie grafů předmětem studia teorie sítí.
- Se distinguen dos vértices: la fuente s y el destino t. Se supone que cada vértice se encuentra en alguna ruta de s a t. Un flujo en G es una función <math>f: V \times V \mapsto R</math> tal que *Restricción de capacidad: <math>\forall \quad u,v \in V,\quad f(u,v) \le c(u,v)</math> Simetría: <math>f(u,v) = - f(v,u) \,</math> Conservación: <math>\forall u \in V - \left \{ s,t \right \} \quad \sum_{v \in V} f(u,v) = 0 </math> El valor del flujo es <math>|f| = \sum_{v \in V}f(s,v)</math> El problema del flujo máximo trata de maximizar este flujo.
- フローネットワーク（英: Flow network）は、グラフ理論における有向グラフの一種であり、各枝に容量（capacity）を設定し、各枝をフロー（flow）が流れる。各枝のフローはその容量を超えることはない。オペレーションズ・リサーチでは、有向グラフをネットワークと呼び、頂点をノード、枝をアークと呼ぶ。フローが満足すべき制約条件として、1つのノードに流入するフローとそのノードから流出するフローは常に等しい。ただし、始点（source）と終点（sink）では、その限りではない。このネットワークは、例えば道路網の交通量、パイプを流れる液体、電気回路を流れる電流、その他の何らかのネットワーク上を移動するものをモデル化するのに適している。
- Siecią przepływową <math>G(V,E)</math> nazywamy graf skierowany, w którym każda krawędź <math>(u,v)</math> należąca do zbioru krawędzi <math>E</math> ma nieujemną przepustowość <math>c(u,v)\geqslant 0</math>. W sieci wyrózniamy dwa wierzchołki: źródło <math>s</math> i ujście <math>t</math>.
- В теории графов транспортная сеть <math>G = (V,E)</math> — ориентированный граф, в котором каждое ребро <math>(u,v) \in E</math> имеет неотрицательную пропускную способность <math>c(u,v)</math> > <math>0</math> и поток <math>f(u,v)</math>. Выделяются две вершины источник <math>s</math> и сток <math>t</math> такие, что любая другая вершина сети лежит на пути из <math>s</math> в <math>t</math>. Транспортная сеть может быть использована для моделирования, например, дорожного трафика.
- 在圖論中，網絡流 (Network Flow) 是指在一個每條邊都有容量 (Capacity) 的有向圖分配流，使一條邊的流量不會超過它的容量。（邊有附帶容量的圖稱為網絡。）一道流必須符合一個結點的進出的流量相同的限制，除非這是一個源點 (Source) ──有較多向外的流，或是一個匯點 (Sink) ──有較多向內的流。一個網絡可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點 (Node) 的網絡中遊動的任何事物。
|
| rdfs:comment
|
- In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs.
- Ein Netzwerk N=(V, E, s, t, c) ist in der Graphentheorie ein gerichteter Graph ohne Mehrfachkanten mit zwei ausgezeichneten Knoten, einer Quelle s und einer Senke t aus V sowie einer Kapazitätsfunktion c, die jeder Kante (x,y) aus E eine nicht-negative, reellwertige Kapazität c(x,y) zuweist. Ein s-t-Fluss ist eine Funktion f, die jeder Kante (x,y) im Netzwerk einen nicht-negativen reellen Flusswert f(x,y) zuweist.
- Toky v sítích jsou v rámci teorie grafů předmětem studia teorie sítí.
- Se distinguen dos vértices: la fuente s y el destino t. Se supone que cada vértice se encuentra en alguna ruta de s a t.
- Siecią przepływową <math>G(V,E)</math> nazywamy graf skierowany, w którym każda krawędź <math>(u,v)</math> należąca do zbioru krawędzi <math>E</math> ma nieujemną przepustowość <math>c(u,v)\geqslant 0</math>. W sieci wyrózniamy dwa wierzchołki: źródło <math>s</math> i ujście <math>t</math>.
- В теории графов транспортная сеть <math>G = (V,E)</math> — ориентированный граф, в котором каждое ребро <math>(u,v) \in E</math> имеет неотрицательную пропускную способность <math>c(u,v)</math> > <math>0</math> и поток <math>f(u,v)</math>.
|
![[RDF Data]](/statics/sw-cube.png)
