0
$\begingroup$

From Wikipedia

a flow network (also known as a transportation 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. 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.

Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs.

From West's Introduction to Graph Theory's Appendix D Glossary and Terms

Network [176]: a directed graph with a distinguished initial vertex (source) and a distinguished, terminal vertex (sink), in which each edge is assigned a flow capacity and possibly also a flow demand (lower bound).

  1. So I wonder what the definition for a network is?

  2. Must a network be directed? Both sources said so, but from my past intuition, a network can be undirected.

  3. Must a network have a weight or flow for each edge? Must a network have a capacity on the weight or flow for each edge? Wikipedia seems say no and only flow networks can have them, while West seemed to say yes.
  4. Must a network have a source vertex and a sink vertex? Wikipedia seems say no and only flow networks can have them, while West seemed to say yes.

I understand that there may be different definitions by different people, including those not listed here. However, I would like to know what definition makes more sense and/or receives more consensus?

Thanks!

1 Answers 1

2

Here is a quite general definition of the terms you're asking for:

A network is a tuple $(G,u)$ where $G=(V,E)$ is a directed graph and $u:E\to \mathbb{R}_{>0}\cup\{\infty\}$. For $e\in E$, we call $u(e)$ the capacity of that edge.

A circulation in the network $(G,u)$ is a map $f:E\to\mathbb{R}_{\ge 0}$ with $f(e)\le u(e)$ for all edges $e\in E$ and $\begin{equation}\tag{$\dagger$}\forall v\in V: \sum_{e=(w,v)\in E} f(e) = \sum_{e=(v,w)\in E} f(e),\end{equation}$ meaning that in any vertex, the same amount flows in and out of that vertex.

Given vertices $s,t\in V$, we construct a network $(G_{st},u_{st})$ as follows: We add an edge $(t,s)$ to $G$ and call the resulting graph $G_{st}$. We define $u_{st}$ to take the same values as $u$ on $E$ and set $u_{st}((t,s)):=\infty$. A circulation in $G_{st}$ is called an $s$-$t$-flow and its value is the number $f((t,s))$.

Now to answer your questions.

  1. I would go as far as to say that a network really has to be a directed graph.
  2. A flow is not part of a network, it is something that sortof "lives" on a network. As far as capacities and flow values are concerned: You can have 'no flow' on an edge $e$ by having $f(e)=0$, and you can have 'no capacity limit' on an edge $e$ by setting $u(e)=\infty$. Formally, however, both the flow and the capacity function assign a value to every edge of the graph.
  3. A network does not have to have distinguished source and sink vertices $s$ and $t$: My above definition leaves that choice open. However, often you want to have something actually flow from some source to some sink - and you picture that source as supplying items by itself, so we want to allow that more flows out of it than in: In other words, we do not want $(\dagger)$ to hold for $s$. We solve this in the above definition by adding an uncapacitated edge from $t$ back to $s$.

I hope this helps a bit, but I suggest reading a good textbook about the topic (i.e. Combinatorial Optimization by Korte and Vygen).

  • 0
    I think you are beeing too literal here. I ment that remark to serve your intuition, 'living on' is not a formal term. The reason why I do not consider the flow as part of the network is because you will usually want to vary it, in order to find, e.g. a flow of maximal value. The edge weights, however, would feel to me as a part of the network. Remember, however, that this is intuition, not formalism.2012-11-02