[Math] the definition of a network in graph theory

graph theorysoft-question

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!

Best Answer

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

Related Question