What connects us all? Well, it must be the Internet nowadays. With access to the Internet, we can play games, watch drama series, chat with friends, shop online, and order takeout conveniently. Who can ever imagine life without the Internet?
A network is composed of hosts and data links. The hosts refer to terminal devices such as personal computers, mobile phones, and servers, as well as other network devices including switches and routers. A data link is a direct connection between two hosts, over which the data packets can be transmitted in either direction. Data links can be implemented in various physical forms; the most common ones are copper cables, optical fibers, and radio waves, to name but a few.
Since it is generally not practical to build data links between every pair of hosts, the data packets may pass through intermediate hosts when the source host and the destination host are not adjacent. There are many possible routes between two hosts, so we need a routing protocol to decide which route to use. The simplest routing protocol is the Spanning Tree Protocol (STP). In STP, only a subset of all data links are enabled such that every two hosts are reachable and there is no cycle in the enabled data links. The set of enabled data links is called a spanning tree, and it is clear that there is a unique path composed of only enabled data links between any two hosts.
The Network Construction Company have just set up a network, and they want to test whether all data links work properly. To do this, they plan to carry out several rounds of testing. In each round of testing, a spanning tree is chosen and the packages are transmitted via only the data links in the spanning tree, so that the connectivity of every enabled data link can be tested. They want to minimize the number of testing rounds conducted, under the premise that every data link in the network is tested in at least one round.