Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Bicircular matroid
In the mathematical subject of matroid theory, the bicircular matroid of a graph G is the matroid B(G) whose points are the edges of G and whose independent sets are the edge sets of pseudoforests of G, that is, the edge sets in which each connected component contains at most one cycle.
The bicircular matroid was introduced by Simões-Pereira (1972) and explored further by Matthews (1977) and others. It is a special case of the frame matroid of a biased graph.
The circuits, or minimal dependent sets, of this matroid are the bicircular graphs (or bicycles, but that term has other meanings in graph theory); these are connected graphs whose circuit rank is exactly two.
There are three distinct types of bicircular graph:
All these definitions apply to multigraphs, i.e., they permit multiple edges (edges sharing the same endpoints) and loops (edges whose two endpoints are the same vertex).
The closed sets (flats) of the bicircular matroid of a graph G can be described as the forests F of G such that in the induced subgraph of V(G) − V(F), every connected component has a cycle. Since the flats of a matroid form a geometric lattice when partially ordered by set inclusion, these forests of G also form a geometric lattice. In the partial ordering for this lattice, that F1 ≤ F2 if
For the most interesting example, let G o be G with a loop added to every vertex. Then the flats of B(G o) are all the forests of G, spanning or nonspanning. Thus, all forests of a graph G form a geometric lattice, the forest lattice of G (Zaslavsky 1982).
Bicircular matroids can be characterized as the transversal matroids that arise from a family of sets in which each set element belongs to at most two sets. That is, the independent sets of the matroid are the subsets of elements that can be used to form a system of distinct representatives for some or all of the sets. In this description, the elements correspond to the edges of a graph, and there is one set per vertex, the set of edges having that vertex as an endpoint.
Hub AI
Bicircular matroid AI simulator
(@Bicircular matroid_simulator)
Bicircular matroid
In the mathematical subject of matroid theory, the bicircular matroid of a graph G is the matroid B(G) whose points are the edges of G and whose independent sets are the edge sets of pseudoforests of G, that is, the edge sets in which each connected component contains at most one cycle.
The bicircular matroid was introduced by Simões-Pereira (1972) and explored further by Matthews (1977) and others. It is a special case of the frame matroid of a biased graph.
The circuits, or minimal dependent sets, of this matroid are the bicircular graphs (or bicycles, but that term has other meanings in graph theory); these are connected graphs whose circuit rank is exactly two.
There are three distinct types of bicircular graph:
All these definitions apply to multigraphs, i.e., they permit multiple edges (edges sharing the same endpoints) and loops (edges whose two endpoints are the same vertex).
The closed sets (flats) of the bicircular matroid of a graph G can be described as the forests F of G such that in the induced subgraph of V(G) − V(F), every connected component has a cycle. Since the flats of a matroid form a geometric lattice when partially ordered by set inclusion, these forests of G also form a geometric lattice. In the partial ordering for this lattice, that F1 ≤ F2 if
For the most interesting example, let G o be G with a loop added to every vertex. Then the flats of B(G o) are all the forests of G, spanning or nonspanning. Thus, all forests of a graph G form a geometric lattice, the forest lattice of G (Zaslavsky 1982).
Bicircular matroids can be characterized as the transversal matroids that arise from a family of sets in which each set element belongs to at most two sets. That is, the independent sets of the matroid are the subsets of elements that can be used to form a system of distinct representatives for some or all of the sets. In this description, the elements correspond to the edges of a graph, and there is one set per vertex, the set of edges having that vertex as an endpoint.