Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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? –  Tim Oct 27 '12 at 22:43
    
(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? –  Tim Oct 28 '12 at 15:47
    
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. –  Jesko Hüttenhain Oct 29 '12 at 14:56
    
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? –  Tim Nov 2 '12 at 3:50
    
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. –  Jesko Hüttenhain Nov 2 '12 at 10:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.