Connect 'em
Chris has 16 computers forming a network which consists of the computers connected through wires.
He can send data from one computer to another, if they are connected through a series of wires and computers.
What is the minimum number of wires that are required to connect the computers in such a way that even if one wire is cut, it is still possible to send data from any computer to the other?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
We'll call a collection of a computers (henceforth, vertices) a component , if there is a way to transmit information from any one of them to any other. To have connected all of the vertices is to have all of them in the same component, i.e, to have exactly one component in the network.
Notice that by adding an wire (henceforth, edge), we can decrease the number of components by at most 1. This means that we need at least 15 edge to connect all the computers together.
Since cutting any one edge would reduce it to a network with 14 edges, the 15 edge network won't work.
But a 16 edge network definitely does work, and here is one: