# What is the definition of a network in graph theory

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!

-

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 $$$$\tag{\dagger}\forall v\in V: \sum_{e=(w,v)\in E} f(e) = \sum_{e=(v,w)\in E} f(e),$$$$ 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))$.

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