2
$\begingroup$

Background

I am working on a project at present involving graph analysis. I basically need to mathematically model trees inside my graph. How can this be done using Matroids?

What I am looking for

Please note that this question is very general and it is meant to be so because I just need an overview about matroids. What are they capable of? How can they describe trees in a graph, what properties. Can you provide me just some links or papers about this?

Notes

My aim is mainly centered in finding trees in a graph. So the objective is to locate those edges that constitute a tree in my graphs. I have experienced some mathematical classic concepts for this, but I got to know something about matroids as being algebraic structures able to locate trees, loops and other interesting elements in a graph. What I need to understand is just the community opinion about matroids for these purposes.

Are matroids good at describing and finding trees in graphs?

How is this description performed?

Where can I find good links that explain me how to build a matroid to describe a graph?

How do I look in a matroid for trees?

Thankyou

  • 1
    A short answer to the first two questions is that the set of trees in a graph _is_ a matroid. Even more generally, let G be a graph. Then the set of all set of edges of G without cycles is a matroid. Thus the initial statement is just a corollary of this result. Obviously, this implies that results from matroid theory can be refereed to trees. For example, an ordered matroid has an optimal element. Thus in any graph there exists a minimal spanning tree: just order the edges of G in decreasing order of length. However, whether they are useful or not clearly depends on the specific problem.2017-03-01

0 Answers 0