To explore networks more easily we now introduce a few useful concepts.
Subnetworks
The networks shown below have every vertex connected to every other vertex:
The degree of each individual vertex is equal to one less than the number of vertices overall. For example, if you have $5$5 vertices and connect one to all the others, you draw $4$4 edges from each vertex.
Now if we take one of these networks and delete some edges, or some of its vertices (and all edges connected to it), we get a subnetwork of the original. Any simple network that has $n$n vertices is a subnetwork of the corresponding network with $n$n vertices above. We can just add or delete edges to get from one to the other:
The original network on the left has the coloured edges added in, and then the vertices moved a little. We end up with a network where every vertex is connected to every other vertex. We can then go backwards - start at the right, move the vertices and then delete the coloured edges to recover the original network.
For an undirected network, we call it connected if we can move from any vertex to any other vertex along an edge, and disconnected if we can’t. We use the same words for a directed network, though we can move along the (directed) edges in both directions.
The top two networks are connected, the bottom two are disconnected.
These ideas comes up frequently in chemistry, as chemicals are frequently represented as a network. Here are three examples:
The degree of the vertex corresponds to the element. Hydrogen (orange) always has degree $1$1, oxygen (blue) degree $2$2, nitrogen (purple) degree $3$3, and carbon (green) degree $4$4.
These three chemicals have a subnetwork in common - the “benzene ring” of six carbon atoms, with some hydrogens still attached:
Each of the three chemicals' networks have a single edge connecting this subnetwork to the top part.
Edge weights
We represent relationships in a network with edges, and often we will want to attach a measurement to each edge to show how the relationships are different. For example, if we were making a network based on the roads between towns, we might want to show the distances between towns, or how long it takes to drive, as well as, which towns are connected.
To show this kind of extra detail, we add a number to each edge, and call this number a weight. Here are a few examples.
Approximate travel times, in hours, between some European capitals
Average length of bonds in acetic acid, measured in Angstrom.
A simple electrical circuit diagram, with resistances measured in Ohms.
These numbers are going to transform the way we look at networks. We will be able to include a lot more information once we can give weight to relationships.
If a network has weights on its edges, we can give a weight to the whole network by adding up all the weights. This applies to subnetworks and paths through the network as well.
This network has an overall weight of $4+5+7+3+6+6+11+5+16+21=84$4+5+7+3+6+6+11+5+16+21=84.
The subnetwork in the middle (highlighted in orange) has weight $4+5+7+3+6=25$4+5+7+3+6=25.
The red path on the right has weight $3+5+16+11=35$3+5+16+11=35.
Practice questions
Question 1
Select all connected networks:
A
B
C
D
Question 2
For each number in the first row of the table, draw a simple network where every vertex is directly connected to every other vertex by an edge.
Then fill in the number of edges in the resulting network in the second row.
Vertices $2$2 $3$3 $4$4 $5$5 $6$6 Edges $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$ $\editable{}$
Question 3
Consider the following network:
What is the weight of the edge from $S$S to $Q$Q?
What is the weight of the entire network?