Definition 1.1.4. Algorithm.
An algorithm is a formal procedure for completing a computational or mathematical task.
Section 1.1 Connecting a network
We begin with a problem posed in concrete terms: we have a network consisting of several nodes which we wish to connect together, and we know that there is a certain cost associated with connecting pairs of nodes. It should be obvious that we wish to minimize the cost of connecting our network, and for the sake of simplicity we will make the assumption that our network is reliable; that is, once two nodes are connected, they will stay connected. Therefore we only need to make sure everything is connected to the network once.
Without worrying about technical definitions until a later chapter (Chapter 6 ), we will refer to the nodes as vertices and the connections as edges.
Subsection 1.1.1 Working from an example
We can approach the problem very logically by organizing our list of edges carefully. Since we want to include edges with the least cost first, it makes sense to list the edges in that order.
| \((u,v)\) | \(w(u,v)\) | \((u,v)\) | \(w(u,v)\) |
| (6, 7) | 3 | (5, 6) | 12 |
| (0, 7) | 4 | (4, 7) | 13 |
| (2, 7) | 5 | (1, 2) | 14 |
| (1, 5) | 6 | (3, 7) | 15 |
| (4, 6) | 6 | (0, 1) | 16 |
| (2, 6) | 9 | (1, 4) | 17 |
| (0, 3) | 12 |
To connect our network is now a matter of looking at each edge in order of increasing cost and including that edge as a connection exactly when the two ends of the edge are not already connected together!
For our very small example here it is easy enough to do this on a piece of paper, keeping track of all of the connected pieces in a table. As soon as we look at the first edge, we have to make a decision about which piece of the network is will gain a vertex and which piece will become empty; in order to make this easy for ourselves, we opt to always merge into the large piece, or if the two pieces have the same number of vertices we will merge into the piece whose initial vertex had a smaller numerical index.
| Components | Use | Total | ||||||||||
| Step | \((u,v)\) | \(w\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Edge? | Cost |
| 0 | - | - | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | - | 0 |
| 1 | (6,7) | 3 | [0] | [1] | [2] | [3] | [4] | [5] | [6,7] | - | Yes | 3 |
| 2 | (0,7) | 4 | - | [1] | [2] | [3] | [4] | [5] | [0,6,7] | - | Yes | 7 |
| 3 | (2,7) | 5 | - | [1] | - | [3] | [4] | [5] | [0,2,6,7] | - | Yes | 12 |
| 4 | (1,5) | 6 | - | [1,5] | - | [3] | [4] | - | [0,2,6,7] | - | Yes | 18 |
| 5 | (4,6) | 6 | - | [1,5] | - | [3] | - | - | [0,2,4,6,7] | - | Yes | 24 |
| 6 | (2,6) | 9 | - | [1,5] | - | [3] | - | - | [0,2,4,6,7] | - | No! | 24 |
| 7 | (0,3) | 12 | - | [1,5] | - | - | - | - | [0,2,3,4,6,7] | - | Yes | 36 |
| 8 | (5,6) | 12 | - | - | - | - | - | - | [0,1,2,3,4,5,6,7] | - | Yes | 48 |
Subsection 1.1.2 Algorithm
Taking a look at what we actually did, we can explain our process in more detail so that for a bigger, more complicated problem (specifically one with a larger set of vertices or of edges) the solution could be extended. In fact we have just implemented a famous result known as Kruskal’s Algorithm.
In order to communicate our algorithm efficiently, we have to analyze what our steps actually entailed. Later on, we’ll give a more computational statement of the same algorithm, in Subsection 6.2.3.
Algorithm 1.1.5. Mathematical Kruskal’s Algorithm.
Let a graph \(G=(V,E)\) with vertex set \(V=\set{0,1,2,\dotsc,n-1}\) be given which has a cost \(w(e)\) associated with each edge \(e\text{.}\) Each edge will be denoted \((u,v)\) with \(u\lt v\text{,}\) where \(u,v\in V\text{.}\)
- Sort the edges by increasing cost, so that whenever \(i\lt j\) then also \(w(e_i)\leq w(e_j)\text{,}\) where \(i\) and \(j\) are “counting variables”.
- Write \(n\) different sets representing components of the network, denoted \(c_v=\set{v}\) for each \(v\in V\text{.}\) Also let \(F=\emptyset\) be an empty collection of edges.
- Looking at each edge \(e_i=(u_i,v_i)\) in increasing order of cost, do the following.
- If \(u_i\) and \(v_i\) are in the same component, skip immediately to the next edge.
- Otherwise, say that \(c_u\) is the component containing \(u_i\) and \(c_v\) is the component containing \(v_i\text{,}\) and do the following:
- If \(c_u\) contains fewer vertices than \(c_v\text{,}\) put all of the elements from \(c_u\) into \(c_v\) instead and leave \(c_u\) empty.
- Otherwise, put all of the elements from \(c_v\) into \(c_u\) and leave \(c_v\) empty.
- In either case, include the edge \((u_i,v_i)\) in \(F\text{.}\)
After Step 3 finishes, all of the edges will have been inspected and either included in the network or skipped; there will be as many nonempty components \(c_v\) as needed to connect the network, and the algorithm is finished! The cost-minimal set of edges is \(F\text{.}\)
This algorithm works even when there is not a possible way to connect all of the nodes into one network! If several disconnected networks are needed, this algorithm will find the least expensive way to do so.
Problem 1.1.6. A 50-edge network.
The connections of a network are given below as a table of triples \((u,v,w(u,v))\text{.}\) Find the least expensive set \(F\) of edges needed to connect the components of this network.
| \((u,v,w(u,v))\) | \((u,v,w(u,v))\) | \((u,v,w(u,v))\) | \((u,v,w(u,v))\) | \((u,v,w(u,v))\) |
| (0, 1, 8) | (2, 4, 1) | (4, 13, 1) | (5, 17, 6) | (9, 16, 8) |
| (0, 3, 3) | (2, 10, 9) | (4, 15, 5) | (5, 19, 7) | (9, 17, 6) |
| (0, 4, 8) | (2, 11, 5) | (4, 16, 9) | (6, 12, 8) | (10, 13, 7) |
| (0, 8, 10) | (2, 18, 8) | (4, 18, 3) | (7, 8, 9) | (10, 16, 8) |
| (0, 10, 4) | (2, 19, 6) | (5, 6, 5) | (7, 13, 3) | (11, 12, 10) |
| (0, 13, 1) | (3, 5, 10) | (5, 7, 8) | (7, 15, 10) | (11, 18, 8) |
| (0, 16, 4) | (3, 13, 9) | (5, 8, 10) | (7, 18, 6) | (12, 19, 1) |
| (1, 4, 4) | (3, 14, 6) | (5, 10, 8) | (8, 11, 1) | (13, 14, 7) |
| (1, 6, 10) | (3, 19, 6) | (5, 14, 6) | (8, 19, 7) | (15, 17, 7) |
| (1, 18, 5) | (4, 10, 5) | (5, 16, 4) | (9, 15, 5) | (16, 18, 9) |
Your solution should include all the steps, but your answer will consist only of the set of included edges.
Answer.
The minimal-cost connecting set consists of the following edges:
\begin{equation*}
\begin{matrix}
(0,3) \amp (2,4) \amp (4,15) \amp (7,13) \\ (0,10)
\amp (2,11) \amp (4,18) \amp (8,11) \\ (0,13) \amp (2,19) \amp (5,6)
\amp (9,15) \\ (0,16) \amp (3,14) \amp (5,16) \amp (12,19) \\ (1,4)
\amp (4,13) \amp (5,17) \amp \end{matrix}
\end{equation*}
It is important to note that throughout the process of applying the algorithm, the values of some of the quantities changed: this is only natural!We expect this just from what we observed initially in our small example network. Speaking algorithmically, we will say that variables are these changeable quantities and constants or parameters are those quantities which do not change once the algorithm begins. In this case, the numbers of vertices and edges are both parameters for a given graph.
Finally, this algorithm is labeled as a “mathematical”algorithm because it is not sufficiently detailed to actually implement in a computer program. To program the algorithm, several of the steps-as-written would need to be explained as algorithms in their own right!
