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!

$\endgroup$

1 Answer 1

3
$\begingroup$

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).

$\endgroup$
5
  • $\begingroup$ Thanks! May I ask your opinions on the references? (1) How do you think about West's Introduction to graph theory? (2) For graph/network optimization, how is the book by Korte and Vygen compared to Network Flows: Theory,Algorithms,and Applications by Ahuja, Magnanti and Orlin, and the optimization part in West's book, among others? $\endgroup$
    – Tim
    Commented Oct 27, 2012 at 22:43
  • $\begingroup$ (3) "A network does not have to have distinguished source and sink vertices s and t: My above definition leaves that choice open." Do you mean there can be different choices for s and t, or s and t can be the same vertex? $\endgroup$
    – Tim
    Commented Oct 28, 2012 at 15:47
  • $\begingroup$ During my studies, we used the book by Korte and Vygen mainly, and I do not know the books you mention in enough detail to give you a well-founded opinion. However, there is certainly more than one good book on graph theory and optimization. Regarding (3), I ment that you can choose arbitrary $s$ and $t$, so in particular you could choose them to be equal - usually, however, that makes little sense when modelling a real-life scenario. $\endgroup$ Commented Oct 29, 2012 at 14:56
  • $\begingroup$ Thanks! "A flow is not part of a network, it is something that sortof "lives" on a network." If in a directed graph with a weight for each edge, are the edge weights not considered part of the graph, but live on the graph instead? $\endgroup$
    – Tim
    Commented Nov 2, 2012 at 3:50
  • $\begingroup$ 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. $\endgroup$ Commented Nov 2, 2012 at 10:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .