Finding minimal spanning trees and dominating sets

Networks have applications for a wide variety of problems. Two obvious areas that see many applications are communication and distribution. For example, we might wish to find a way of distributing goods to several cities (nodes) in a road network that covers the smallest distance from a particular point. For problems like this, we need to look at minimal spanning trees and dominating sets.

In this recipe, we will find a minimal spanning tree and a dominating set in a network.

Getting ready

For this recipe, we need to import the NetworkX package under the nx alias and the Matplotlib pyplot module as plt.

How to do it...

Follow these steps to find a minimum spanning tree and dominating set for a network:

1. First, we will create a sample network to analyze:

   G = nx.gnm_random_graph(15, 22, seed=12345)

2. Next, as usual, we will draw the network before doing any analysis:

   fig, ax = plt.subplots()

   pos = nx.circular_layout...