If we think of the theory of vector spaces, it is impossible to fail to observe the analogy of the properties of spanning trees with the bases of vector Spaces.

         Figure 1.1. In bold: (a) the spanning tree T, (b) the spanning tree T^/

bring to mind the classic exchange property between the bases of vector spaces. This proximity is not fortuitous and can be clarified in the following way. Let G =(X,E) be a connected graph. It is possible to define a vector space on the set E in which a set of edges F ⊆ E is linearly independent if, by definition, the induced spanning subgraph G(F) is acyclic, and F is a spanning subset if G(F) is connected. A basis of this vector space is thus a subset F which is linearly independent and which spans E, that is, such that the spanning subgraph G(F) is both acyclic and connected, that is a spanning tree of G. The sets of edges of the spanning trees of G are therefore the bases of this vector space. With propositions(A spanning subgraph of  a connected graph G is a spanning tree of G if and only if it is connected and edge-minimal. ) and (. A spanning subgraph of a connected graph G is a spanning tree of G if and only if it is acyclic and edge-maximal.) we recognize the classic characterization of the basis of a vector space: a minimal spanning subset or a  maximal linearly independent subset. We find directly the finitedimension of this vector space: it is the number of edges common to all spanning trees, that is  n−1, where n is the number of vertices of the graph.This algebraic aspect of the graphs is the starting point of a very important and interesting theory, the theory of matroids.

__________________________________________________________________________________________________________

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(49-52)

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength