Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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 the definition of a network, are we only considering connected graphs ?

Because I keep encountering definitions that don't assume explicitly that we deal with connected graphs, but which would be very counter-intuitive if they would also apply for disconnected graphs (almost everywhere one is advised to think of a network - the mathematical object - as a network of pipes transporting some fluid; if disconnected graphs come into play this metaphor of pipes transporting something fails!).

share|cite|improve this question
"Network" means different things to different people. What context is this in? – Qiaochu Yuan Jul 22 '11 at 19:57
If you mean computer networks, they do not have to be connected. You might want the graph to be weighted or directed, depending on the situation (network characteristics and problem at hand). – Emre Jul 22 '11 at 20:02
@Qiaochu Well, there isn't much context; I was just confronted with networks during a course in discrete mathematics, where also some graph-theoretical topics were treated. Basically we just got the definition and some lemmas and theorems followed that illustrated some properties of the definitions and then we moved on to other topics. We defined a network to be a directed graph (@ Emre, sorry, should have mentioned that earlier), that contains to two special nodes, the source and the sink, and a function (the capacity) $f:E\rightarrow \mathbb{R}$. – resu Jul 23 '11 at 9:44
Also (@ Qiaochu) what would be all the other meanings network ? – resu Jul 23 '11 at 9:45
@resu: I don't know. All I'm saying is that a lot of people use the word "network" (computer scientists, biologists, social scientists, etc.) and I would be rather surprised if their usages matched exactly. It doesn't, to my knowledge, have a precise, agreed-upon mathematical definition, and before you gave that definition that I thought you were referring to a graph. – Qiaochu Yuan Jul 23 '11 at 14:17

I don't see how the metaphor fails if the graph is disconnected. Your pipe system is just broken (or perhaps under construction), and no flow is possible. A broken system of pipes is still a system of pipes.

share|cite|improve this answer

It is possible that the author had a sensor network in mind. These usually have sensors (sources) and a sink that fuses the sensor readings. The capacity can also be defined.

These networks may or may not be connected. Obviously it helps if there is always a path from all sources to the sink. If the path momentarily disappears, the sources may store their readings until a route is re-established, etc.

share|cite|improve this answer

Outside of flow networks (which are precisely defined)...

What is the right way to think of a network?

There isn't one right way. What a "network" is is context dependent. Authors often do not give a precise definition of a network, instead opting for a more encompassing intuitive definition of "network".

Should one think of a network as a connected graph ?

  • In real-world contexts, a network might not even be considered a graph.

    For example, in a biological neural network neuronal connections are made via an axon to other neurons. A single axon may connect to many other neurons (and have many connections to each of them). This is an advantage for e.g. coordinating movement.

    It's not obvious how to interpret the network as a graph (and whether or not a graph is the best data structure to use). E.g. if we represent a single axon with multiple edges, then the graph does not capture the property that if we cut that single axon, then we cut a whole bunch of edges.

  • In real-world contexts, for a network that is considered a graph (which may or may not be directed), it may or may not be important that the graph is connected (either weakly or strongly). E.g. in my area of research, network motifs, it can be largely ignored (it's not relevant to the problems we're trying to solve).

    In cases where connectivity is important (e.g. computer networks), the distinction between connected and disconnected networks is an important consideration. In other studies, a largest component (or giant component) may be instead studied.

share|cite|improve this answer

Your Answer


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.