Let $G = (V, E)$ be a finite connected graph without multiple edges or loops.
We consider the task about the numbering of all the spanning trees of $G$.
In [2, p. 180, p. 191] described a method of solution of this task,
based on the properties of minors of an incidence matrix of $G$.
In the same place (p. 191–193) gave algorithm of four Japanese mathematicians
(Kasahara Y., Tezuka K., Ling Shun Tong, Kitahashi T., [6]),
reduced the task to removal of brackets in the product of formal sums of edges of $G$.
Here we concider the method based on lexicographical order on the set of
all sequences of edges of $G$.
We will remind that a spanning tree $T$ of the graph $G$ is a tree consisting
of edges of $G$ and connecting all the vertices of $G$.
We shall assume that $V =\{ 1,2, \ldots, n\} $, where $n$ is a
number of vertices of $G$. If $a, b \in V$,
then $ (a, b) $ will be designated the edge with end-points $a$ and $b$.
Let $T$ be a spanning in $G$.
Then the set of his edges can be written in the form
\begin{equation}
(a_1, b_1), (a_2, b_2), \ldots, (a_ {n-1}, b_ {n-1}), \tag{A}
\end{equation}
where
\begin{equation}
a_i{i+1} \ {\rm or} \ a_i=a_{i+1}\ \text{and} \ b_i{i+1}, \ \text{where}\ i=1,2,\ldots, n-2.
\tag{B}
\end{equation} On a set of sequences of in the form of (A) with the additional condition (B)
we will consider a lexicographic order.
The smallest (with respect to this order)
spanning tree will be the tree $T_0$ with edges
$ (1,2)$, $(1,3)$, $ (1,4)$, $\ldots$, $ (1, n) $
provided $(1,b) \in E$
for $b=2,3, \ldots, n$.
The greatest spanning tree $T_1$ will be
$ (1, n) $, $ (2, n) $, $ (3, n) $, $\ldots$, $ (n-1, n) $
under a similar condition.
Touching all sequences of a look (A) in ascending order
between $T_0$ and $T_1$
and checking lack of cycles at the corresponding
sets of edges,
we will be able to get a list of all spanning trees.
We will give results of work of the appropriate computer program.
Example 1. For complite graph $K_n$ on $n$ vertices
for $n\leq 9$ the
lists of all the spanning trees are obtained.
Due to Kely theorem $K_n$ has $n^{n-2}$ spanning trees.
For $n=9$ thos number is equal $4\,782\,969$.
Example 2. Let $G$ be a graph on $12$ vertices in figure 1 (in the left).
Then $G$ has $2\,415$ spanning trees.
Let $P$ be a finite set of points in the plane $R^2$.
Then $G = (V, E) $ is a plane geometrical graph on top of $P$,
if $V\subset R^2$ and egdes of $G$ are stright-line segments with the
end-points in $P$ and two edges of $G$ intersects only in points of $P$ [3].
If $G$ is a tree and $V=P$, then $G$ called a spanning tree on top of $P$.
Example 3. Let $P$ be a set of square tops,
and also its center. Then there are $45$ spanning trees on top of $P$.
Example 4. Let $P$ consists of square tops, and also
middle of its parties. Then there are $3\ 273$ spanning trees on top of $P$.
Example 7. We will consider a set $P=L_{n,m}$
consisting of $n\cdot m$ points on the plane:
$$L_ { n, m } = \{ (i, j): i=1,2, \ldots, n, j=1,2, \ldots, m\}, $$
where $n, m\geq of 1$ are integers.
Thus, $L_ { n, m } $ is a uniform lattice which points lie on $n$
horizontal straight lines and for $m$
vertical straight lines.
The numbers $St(P)$ of a spanning trees on top of this lattice
for small $n$ and $m$ it is specified in the following table:
At transfer the spanning trees it is possible to carry out a filtration.
For example, it is possible to keep only those trees in the final list,
which degrees of vertices not exceeded some number $r$.
So, the complete graph on $8$ vertices has $8 ^6=262\,144$
spanning trees. Among them $201\ 600$ spanning trees
which degree of vertices don't exceed $3 $,
and $20\,160$ spanning trees with degree of vertices $\leq 2$.
Some modification of the main algorihm
allows to receive the list of all crossing-free geometrical graph
on top of $P$ [3].
For example, if
$P$ consists of square tops, and also
middle of its parties, the number of such a graph on top of $P$
is equal to $21\,795$ (this number included also the empty graph).
If to add to $P$
the center of a square, this number will become to $167\,570$.
In work is considered
also a task about creation of all triangulations of a finite set $P\subset R^2$.
The algorithm of the solution of this task is available in [3].
The alternative description of algorithm of search is provided in this work.
Example 9. Let $P=L_{ n, m } $ be a uniform lattice on the plane
(see example 7). Then the number $Tr(P)$ of triangulations of $L_{ n, m } $
for small $n$ and $m$ is specified in the following table:
