For a finite undirected graph, the graphic matroid has its edges as the ground set. A subset is a matroid independent set when its edges form a forest on the original vertices, including isolated vertices. Its matroid bases give a spanning tree in each connected component of a graph; for a connected graph, each matroid basis is a spanning tree.
For a graph triangle on vertices , label the edges , , and , with weights . The empty set, all singletons, and all pairs are forests; the triple contains the graph cycle . Thus its eight subsets have exactly the independence pattern checked in the weighted three-vector matroid, and the same fifteen exchange comparisons pass. The matroid greedy algorithm chooses , chooses , and rejects , producing the heaviest spanning tree, of weight .
A weighted graph triangle admits greedy selection of a matroid basis; a hereditary independence system without exchange traps a greedy algorithm at weight instead of
. Details. Exchange outline. Deleting edges cannot create a graph cycle. If forests have , some edge of joins different connected components of a graph of : otherwise, within each such component, would have at most its number of vertices minus one edges, giving . Adding that edge keeps a forest. This is the matroid independence axioms expressed through connectivity.
Articles by others on the same topic
A **graphic matroid** is a specific type of matroid that is associated with the edges of a graph. Matroids are combinatorial structures that generalize the notion of linear independence in vector spaces. In the case of a graphic matroid, the underlying set is composed of the edges of a graph, and the independent sets are defined based on the cycles of that graph.