To explore networks more easily we now introduce a few useful concepts.
The networks shown below have every vertex connected to every other 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:
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.
These ideas comes up frequently in chemistry, as chemicals are frequently represented as a network. Here are three examples:
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.
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.
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.
Select all connected networks:
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{}$ |
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?