OKlibrary  0.2.1.6
Tutorial.hpp File Reference

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

1. For the OKlibrary, a graph is a simply a 2-element list. The first element is a set of vertices and the second is a set of 2-element vertex sets.
```(%i3) g:[{1,2,3},{{1,2},{1,3}}];
(%o3)                    [{1, 2, 3}, {{1, 2}, {1, 3}}]
```
2. Basic graph operations are available in the OKlibrary.
1. For instance, to find the neighbourhood of a vertex in a graph:
```(%i4) neighbours(1,g);
(%o4)                               {2, 3}
```
2. 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}}]
```
3. For most real work we can exploit the Maxima graph library by converting a 2-element list graph to a Maxima graph using the g2mg function.
```(%i7) mg:g2mg(g);
(%o7)                               GRAPH
(%i8) chromatic_number(mg);
(%o8)                                  2
```
4. We can also do the reverse, and convert a Maxima graph into a 2-element list graph using the mg2g function.
```(%i9) mg2g(mg);
(%o9)                    [{1, 2, 3}, {{1, 2}, {1, 3}}]
```
5. There are many graph generators available in the Maxima graph library.
6. The OKlibrary provides additional generators. For example, Kneser graphs - graphs where vertices are the m-element subets of {1,..,n} and edges join disjoint vertices. For example the Peterson-graph:
```(%i10) k:g2mg(kneser_g(5,2))\$
(%i11) print_graph(k)\$

Graph on 10 vertices with 15 edges.