Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
6  
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
2  
David Aldous defines a network to be "a graph with context-dependent extra structure." stat.berkeley.edu/~aldous/Talks/sparse_entropy.pdf –  Tom LaGatta Mar 13 '13 at 0:07

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.