ABSTRACT
Every connected graph G(V, E) may have several spanning trees. A spanning tree T(V, E′) is a subgraph, with the criteria that it includes all the nodes of the original graph, V = {vi}, i = 1, 2,…n, and all these nodes are connected by only selected edges E′ ⊆ E (G). Another important criterion of a spanning tree is that no cycle is allowed when selecting the edges. This is in line with the definition of a tree as a connected graph without any cycles [1]. As a rule of thumb, a tree with n nodes will form a spanning tree with only n − 1 edges [2,3]. For example, a cyclic graph with four nodes, as illustrated in Figure 5.1a, has a total of four spanning trees with each formed by three edges, as illustrated in Figure 5.1b. Another example, in Figure 5.2a, is a diamond graph with four nodes, and it has a total of eight spanning trees with each also formed by three edges, as illustrated in Figure 5.2b.
