The method
generateGraphs can generate all graphs with a given property. For example, we can verify the number of graphs on a given number of vertices. Compare these results to the Online Encyclopedia of Integer Sequences (
http://oeis.org/), where the sequence name is also its OEIS identifier.
A000088 = apply(1..9, n -> #generateGraphs n) |
B = apply(1..12, n -> generateGraphs(n, OnlyBipartite => true)); |
Further, we can use filterGraphs to refine the set of generate graphs for deeper properties.
Here we filter for forests, then for trees only,
forestsOnly = buildGraphFilter {"NumCycles" => 0}; |
A005195 = apply(B, graphs -> #filterGraphs(graphs, forestsOnly)) |
treesOnly = buildGraphFilter {"NumCycles" => 0, "Connectivity" => 0, "NegateConnectivity" => true}; |
A000055 = apply(B, graphs -> #filterGraphs(graphs, treesOnly)) |
Moreover, we can generate random graphs using the
generateRandomGraphs method. Here we verify a result of Erdos and Rényi (see
http://www.ams.org/mathscinet-getitem?mr=120167), which says that a random graph on
n vertices with edge probability
(1+ε)log
(n)/n is almost always connected while a graph with edge probability
(1-ε)log
(n)/n is almost never connected, at least as
n tends to infinity.
connected = buildGraphFilter {"Connectivity" => 0, "NegateConnectivity" => true}; |
prob = n -> log(n)/n; |
apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, 2*(prob n)), connected)) |
apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, (prob n)/2), connected)) |