In the final and 24th article in this series, the reader gets to play around with graphs using previously gained knowledge about the graphs package of Maxima.
In the previous article in this series, we got familiar with simple graphs, and how the graphs package of Maxima allows us to create and visualise them. Building on that knowledge, in this article, we are going to play around with graphs and their properties, using the functions provided by Maximas graphs package.
Graph modifications
We have already created various graphs with the create_graph() and make_graph() functions of the graphs package of Maxima. What if we wanted to modify some existing graphs, say by adding or removing some edges or vertices? For such operations, Maxima provides the following functions:
- add_edge(<edge>, <g>) – Adds <edge> into the graph <g>
- add_edges(<edge_list>, <g>) – Adds edges specified by <edge_list> into the graph <g>
- add_vertex(<vertex>, <g>) – Adds <vertex> into the graph <g>
- add_vertices(<vertex_list>, <g>) – Adds vertices specified by <vertex_list> into the graph <g>
- connect_vertices(<u_list>, <v_list>, <g>) – Connects all vertices from <u_list> to all vertices in <v_list> in the graph <g>
- contract_edge(<edge>, <g>) – Merges the vertices of the <edge> and the edges incident on those vertices, in the graph <g>
- remove_edge(<edge>, <g>) – Removes the <edge> from the graph <g>
- remove_vertex(<vertex>, <g>) – Removes the <vertex> and the associated edges from the graph <g>
Some of the above functions are demonstrated below:
$ maxima -q (%i1) load(graphs)$ /* Loading the graphs package */ ... 0 errors, 0 warnings (%i2) g: create_graph(4, [[0, 1], [0, 2]]); (%o2) GRAPH(4 vertices, 2 edges) (%i3) print_graph(g)$ Graph on 4 vertices with 2 edges. Adjacencies: 3 : 2 : 0 1 : 0 0 : 2 1 (%i4) add_edge([1, 2], g)$ (%i5) print_graph(g)$ Graph on 4 vertices with 3 edges. Adjacencies: 3 : 2 : 1 0 1 : 2 0 0 : 2 1 (%i6) contract_edge([0, 1], g)$ (%i7) print_graph(g)$ Graph on 3 vertices with 1 edges. Adjacencies: 3 : 2 : 0 0 : 2
In the above examples, if we do not intend to modify the original graph, we can make a copy of it using copy_graph(), and then operate on the copy, as follows:
(%i8) h: copy_graph(g); (%o8) GRAPH(3 vertices, 1 edges) (%i9) add_vertex(1, h)$ (%i10) print_graph(h)$ Graph on 4 vertices with 1 edges. Adjacencies: 1 : 0 : 2 2 : 0 3 : (%i11) print_graph(g)$ /* Notice g is unmodified */ Graph on 3 vertices with 1 edges. Adjacencies: 3 : 2 : 0 0 : 2 (%i12) quit();
Advanced graph creations
New graphs can also be created based on existing graphs and their properties by various interesting operations. A few of them are listed below:
- underlying_graph(<dg>) – Returns the underlying graph of the directed graph <dg>
- complement_graph(<g>) – Returns the complement graph of graph <g>
- line_graph(<g>) – Returns a graph that represents the adjacencies between the edges of graph <g>
- graph_union(<g1>, <g2>) – Returns a graph with edges and vertices of both graphs <g1> and <g2>
- graph_product(<g1>, <g2>) – Returns the Cartesian product of graphs <g1> and <g2>
Here are some examples to demonstrate the simpler functions:
$ maxima -q (%i1) load(graphs)$ ... 0 errors, 0 warnings (%i2) g: create_graph(4, [[0, 1], [0, 2], [0, 3]], directed = true); (%o2) DIGRAPH(4 vertices, 3 arcs) (%i3) print_graph(g)$ Digraph on 4 vertices with 3 arcs. Adjacencies: 3 : 2 : 1 : 0 : 3 2 1 (%i4) h: underlying_graph(g); (%o4) GRAPH(4 vertices, 3 edges) (%i5) print_graph(h)$ Graph on 4 vertices with 3 edges. Adjacencies: 0 : 1 2 3 1 : 0 2 : 0 3 : 0 (%i6) print_graph(complement_graph(h))$ Graph on 4 vertices with 3 edges. Adjacencies: 3 : 2 1 2 : 3 1 1 : 3 2 0 : (%i7) print_graph(graph_union(h, complement_graph(h)))$ Graph on 8 vertices with 6 edges. Adjacencies: 4 : 5 : 6 7 6 : 5 7 7 : 5 6 3 : 0 2 : 0 1 : 0 0 : 3 2 1 (%i8) quit();
Basic graph properties
graph_order(<g>), vertices(<g>) returns the number of vertices and the list of vertices, respectively, in the graph <g>. graph_size(<g>), edges(<g>) returns the number of edges and the list of edges, respectively, in the graph <g>.
A graph is a collection of vertices and edges. Hence, most of its properties are centred around them. The following are graph related predicates provided by the graphs package of Maxima:
- is_graph(<g>) – returns true if <g> is a graph, and false otherwise
- is_digraph(<g>) – returns true if <g> is a directed graph, and false otherwise
- is_graph_or_digraph(<g>) – returns true if <g> is a graph or a directed graph, and false otherwise
- is_connected(<g>) – returns true if graph <g> is connected, and false otherwise
- is_planar(<g>) – returns true if graph <g> can be placed on a plane without its edges crossing each other, and false otherwise
- is_tree(<g>) – returns true if graph <g> has no simple cycles, and false otherwise
- is_biconnected(<g>) – returns true if graph <g> will remain connected even after removal of any one of its vertices and the edges incident on that vertex, and false otherwise
- is_bipartite(<g>) – returns true if graph <g> is bipartite, i.e., two-colourable, and false otherwise
- is_isomorphic(<g1>, <g2>) – returns true if graphs <g1> and <g2> have the same number of vertices and are connected in the same way, and false otherwise. And, isomorphism (<g1>, <g2>) returns an isomorphism (that is a one-to-one onto mapping) between the graphs <g1> and <g2>, if it exists.
- is_edge_in_graph(<edge>, <g>) – returns true if <edge> is in graph <g>, and false otherwise
- is_vertex_in_graph(<vertex>, <g>) – returns true if <vertex> is in graph <g>, and false otherwise
The following example specifically demonstrates the isomorphism property, from the list above:
$ maxima -q (%i1) load(graphs)$ ... 0 errors, 0 warnings (%i2) g1: create_graph(3, [[0, 1], [0, 2]]); (%o2) GRAPH(3 vertices, 2 edges) (%i3) g2: create_graph(3, [[1, 2], [0, 2]]); (%o3) GRAPH(3 vertices, 2 edges) (%i4) is_isomorphic(g1, g2); (%o4) true (%i5) isomorphism(g1, g2); (%o5) [2 -> 0, 1 -> 1, 0 -> 2] (%i6) quit();
Graph neighbourhoods
A lot of the properties of graphs are linked to vertex and edge neighbourhoods, also referred to as adjacencies.
For example, a graph itself could be represented by an adjacency list or matrix, which specifies the vertices adjacent to the various vertices in the graph. adjacency_matrix(<g>) returns the adjacency matrix of the graph <g>.
The number of edges incident on a vertex is called the valency or degree of the vertex, and could be obtained using vertex_degree(<v>, <g>). degree_sequence(<g>) returns the list of degrees of all the vertices of the graph <g>. In case of a directed graph, the degrees could be segregated as in-degree and out-degree, as per the edges incident into and out of the vertex, respectively. vertex_in_degree(<v>, <dg>) and vertex_out_degree(<v>, <dg>), respectively, return the in-degree and out-degree for the vertex <v> of the directed graph <dg>.
neighbors(<v>, <g>), in_neighbors(<v>, <dg>) and out_neighbors(<v>, <dg>) return the list of adjacent vertices, adjacent in-vertices and the adjacent out-vertices, respectively, of the vertex <v> in the corresponding graphs.
average_degree(<g>) computes the average of the degrees of all the vertices of the graph <g>. max_degree(<g>) finds the maximal degree of vertices of the graph <g>, and returns one such vertex alongwith. min_degree(<g>) finds the minimal degree of vertices of the graph <g>, and returns one such vertex alongwith.
Here follows a neighbourhood related demonstration:
$ maxima -q (%i1) load(graphs)$ ... 0 errors, 0 warnings (%i2) g: create_graph(4, [[0, 1], [0, 2], [0, 3], [1, 2]]); (%o2) GRAPH(4 vertices, 4 edges) (%i3) string(adjacency_matrix(g)); /* string for output in single line */ (%o3) matrix([0,0,0,1],[0,0,1,1],[0,1,0,1],[1,1,1,0]) (%i4) degree_sequence(g); (%o4) [1, 2, 2, 3] (%i5) average_degree(g); (%o5) 2 (%i6) neighbors(0, g); (%o6) [3, 2, 1] (%i7) quit();
Graph connectivity
A graph is ultimately about connections, and hence lots of graph properties are centred around connectivity.
vertex_connectivity(<g>) returns the minimum number of vertices that need to be removed from the graph <g> to make the graph <g> disconnected. Similarly, edge_connectivity(<g>) returns the minimum number of edges that need to be removed from the graph <g> to make the graph <g> disconnected.
vertex_distance(<u>, <v>, <g>) returns the length of the shortest path between the vertices <u> and <v> in the graph <g>. The actual path could be obtained using shortest_path(<u>, <v>, <g>).
girth(<g>) returns the length of the shortest cycle in graph <g>.
vertex_eccentricity(<v>, <g>) returns the maximum of the vertex distances of vertex <v> with any other vertex in the connected graph <g>.
diameter(<g>) returns the maximum of the vertex eccentricities of all the vertices in the connected graph <g>.
radius(<g>) returns the minimum of the vertex eccentricities of all the vertices in the connected graph <g>.
graph_center(<g>) returns the list of vertices that have eccentricities equal to the radius of the connected graph <g>.
graph_periphery(<g>) is the list of vertices that have eccentricities equal to the diameter of the connected graph.
A minimal connectivity related demonstration for the graph shown in Figure 1 follows:
$ maxima -q (%i1) load(graphs)$ ... 0 errors, 0 warnings (%i2) g: create_graph(9, [[0, 1], [0, 2], [1, 8], [8, 3], [2, 3], [3, 4], [4, 5], [3, 6], [3, 7]]); (%o2) GRAPH(9 vertices, 9 edges) (%i3) vertex_connectivity(g); (%o3) 1 (%i4) edge_connectivity(g); (%o4) 1 (%i5) shortest_path(0, 7, g); (%o5) [0, 2, 3, 7] (%i6) vertex_distance(0, 7, g); (%o6) 3 (%i7) girth(g); (%o7) 5 (%i8) diameter(g); (%o8) 4 (%i9) radius(g); (%o9) 2 (%i10) graph_center(g); (%o10) [3] (%i11) graph_periphery(g); (%o11) [5, 1, 0]
Vertex 3 is the only centre of the graph, and 0, 1 and 5 are the peripheral vertices of the graph.
Graph colouring
Graph colouring has been a fascinating topic in graph theory, right since its inception. It is all about colouring the vertices or edges of a graph in such a way that no adjacent elements (vertex or edge) have the same colour.
The smallest number of colours needed to colour the vertices of a graph, such that no two adjacent vertices have the same colour, is called the chromatic number of the graph. chromatic_number(<g>) computes the same. vertex_coloring(<g>) returns a list representing the colouring of the vertices of <g>, along with the chromatic number.
The smallest number of colours needed to colour the edges of a graph, such that no two adjacent edges have the same colour, is called the chromatic index of the graph. chromatic_index(<g>) computes the same. edge_coloring(<g>) returns a list representing the colouring of the edges of <g>, along with the chromatic index.
The following demonstration continues colouring the graph from the above demonstration:
(%i12) chromatic_number(g); (%o12) 3 (%i13) vc: vertex_coloring(g); (%o13) [3, [[0, 3], [1, 1], [2, 2], [3, 1], [4, 2], [5, 1], [6, 2], [7, 2], [8, 2]]] (%i14) chromatic_index(g); (%o14) 5 (%i15) ec: edge_coloring(g); (%o15) [5, [[[0, 1], 1], [[0, 2], 2], [[1, 8], 2], [[3, 8], 5], [[2, 3], 1], [[3, 4], 2], [[4, 5], 1], [[3, 6], 3], [[3, 7], 4]]] (%i16) draw_graph(g, vertex_coloring=vc, edge_coloring=ec, vertex_size=5, edge_width=3, show_id=true)$ (%i17) quit();
Figure 2 shows the coloured version of the graph, as obtained by %i16.
Bon voyage
With this article, we have completed a two-year long mathematical odyssey through open source, starting from mathematics in Shell, covering Bench Calculator and Octave, and concluding with Maxima. I take this opportunity to thank my readers and wish them bon voyage with whatever they have gained through our interactions. However, this is not the endget set for our next journey.
