MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In current graph theory, a "network" is a precisely defined object: It is a directed graph associated with a function, the "capacity", which is defined on the edge set and has certain specific properties, and for which "flows" - other functions with yet other properties - may be defined.

However, "network" is also a common word. The similarity between everyday's life "networks" (especially electric ones) is overwhelming, and it is not surprising: there is a long history of interplays between graph theory and electric engineering, probably beginning with a famous paper by Kirchhoff (but please correct me if there are even earlier connections). I have the feeling - but again, I might be wrong - that (electric) networks first made it into pure graph theory through the articles of Brooks, Smith, Stone and Tutte, and in particular through The dissection of rectangles into squares (1940); but they still used the word quite informally.

My question is:

When was this similarity formalized? When did networks become more than merely a metaphor or a source of heuristics and assume today's precise definition?

I have an upper bound: in both famous 1956 papers on the Max-Flow-Min-Cut theorem (Ford-Fulkerson and Elias-Feinstein-Shannon), the definition is given already quite clearly, if casually.

Not quite sure whether this question can have an answer at all, as the boundaries are clearly fluid.

share|cite|improve this question
I don't agree that "network" is a precisely defined concept. There is one precisely defined object (that you mention) commonly called a network, but so are lots of other things. Many people use "network" more or less interchangeably with "graph". Perhaps what you are meaning to ask is when the directed-graph-with-a-source-and-a-sink-and-capacities-on-the-edges thing was first defined? – Brendan McKay Mar 12 '13 at 2:02
Ok, I was not aware of this. I thought the definition of "network" was well-established in graph theory - I have found it in almost all textbooks. But ok, then I am actually addressing the question you mean. – Delio Mugnolo Mar 12 '13 at 7:03
David Aldous defines a network to be "a graph with context-dependent extra structure." – Tom LaGatta Mar 13 '13 at 0:07

Your Answer


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

Browse other questions tagged or ask your own question.