The cycle matroid of a graph

A set of edges is independent exactly when it is acyclic. This is the matroid that makes Kruskal's algorithm correct: minimum spanning tree IS the greedy algorithm here.

Usage

morie_graphic_matroid(edges, n_vertices)

Arguments

edges

List or matrix of vertex pairs, vertices from 1.

n_vertices

Number of vertices.

Value

A list with ground, independent, edges.

Examples

morie_graphic_matroid(edges = data.frame(x = c(1, 2, 3, 4), y = c(2, 4, 5, 9)), n_vertices = 5L)
#> $ground
#> [1] 1 2
#> 
#> $independent
#> $independent[[1]]
#> integer(0)
#> 
#> $independent[[2]]
#> [1] 1
#> 
#> $independent[[3]]
#> [1] 2
#> 
#> $independent[[4]]
#> [1] 1 2
#> 
#> 
#> $edges
#> $edges$x
#> [1] 1 2 3 4
#> 
#> $edges$y
#> [1] 2 4 5 9
#> 
#> 
#> $n_vertices
#> [1] 5
#> 
#> $name
#> [1] "graphic"
#>