Tutorial on graphs in Maxima/Lisp by MH.
More...
Go to the source code of this file.
Detailed Description
Tutorial on graphs in Maxima/Lisp by MH.
Graphs via Maxima in the OKlibrary

For the OKlibrary, a graph is a simply a 2element list. The first element is a set of vertices and the second is a set of 2element vertex sets.
(%i3) g:[{1,2,3},{{1,2},{1,3}}];
(%o3) [{1, 2, 3}, {{1, 2}, {1, 3}}]

Basic graph operations are available in the OKlibrary.

For instance, to find the neighbourhood of a vertex in a graph:
(%i4) neighbours(1,g);
(%o4) {2, 3}

Or, to remove a vertex from a graph:
(%i5) remove_vertices_graph({2},g);
(%o5) [{1, 3}, {{1, 3}}]
(%i6) g;
(%o6) [{1, 2, 3}, {{1, 2}, {1, 3}}]

For most real work we can exploit the Maxima graph library by converting a 2element list graph to a Maxima graph using the g2mg function.
(%i7) mg:g2mg(g);
(%o7) GRAPH
(%i8) chromatic_number(mg);
(%o8) 2

We can also do the reverse, and convert a Maxima graph into a 2element list graph using the mg2g function.
(%i9) mg2g(mg);
(%o9) [{1, 2, 3}, {{1, 2}, {1, 3}}]

There are many graph generators available in the Maxima graph library.

The OKlibrary provides additional generators. For example, Kneser graphs  graphs where vertices are the melement subets of {1,..,n} and edges join disjoint vertices. For example the Petersongraph:
(%i10) k:g2mg(kneser_g(5,2))$
(%i11) print_graph(k)$
Graph on 10 vertices with 15 edges.
Adjacencies:
10 : 5 2 1
9 : 6 3 1
8 : 7 4 1
7 : 8 3 2
6 : 9 4 2
5 : 10 4 3
4 : 8 6 5
3 : 9 7 5
2 : 10 7 6
1 : 10 9 8
Definition in file Tutorial.hpp.