Graph Theory Package For Giac/Xcas Graphtheory User Manual

User Manual:

Open the PDF directly: View PDF PDF.
Page Count: 87

Graph theory
package for
Giac/Xcas
Reference manual
June 2018
draft
Table of contents
1. Introduction .............................................. 7
1.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2. Notations used in this manual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2. Constructing graphs ....................................... 9
2.1. General graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1. Creating undirected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2. Creating directed graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3. Creating vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.4. Creating edges and arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.5. Creating paths and trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.6. Specifying adjacency or weight matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2. Promoting to directed and undirected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1. Converting edges to pairs of arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2. Assigning weight matrix to an unweighted graph . . . . . . . . . . . . . . . . . . . . . 12
2.3. Cycle and path graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.1. Cycle graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.2. Path graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.3. Trails of edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4. Complete graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.1. Complete graphs with multiple vertex partitions . . . . . . . . . . . . . . . . . . . . . 13
2.4.2. Complete trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5. Sequence graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.1. Creating graphs from degree sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.2. Validating graphic sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6. Intersection graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6.1. Interval graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6.2. Kneser graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.7. Special graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.7.1. Hypercube graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.7.2. Star graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.7.3. Wheel graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.7.4. Web graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.7.5. Prism graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.7.6. Antiprism graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.7.7. Grid graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.7.8. Sierpi«ski graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.9. Generalized Petersen graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.10. LCF graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.8. Isomorphic copies of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8.1. Creating an isomorphic copy of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8.2. Permuting graph vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.8.3. Relabeling graph vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.9. Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.9.1. Extracting subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.9.2. Induced subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.9.3. Underlying graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.10. Operations on graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.10.1. Graph complement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3
2.10.2. Seidel switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.10.3. Transposing graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.10.4. Union of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.10.5. Disjoint union of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.10.6. Joining two graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.10.7. Power graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.10.8. Graph products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.10.9. Transitive closure graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.10.10. Line graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.10.11. Plane dual graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.11. Random graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.11.1. Random general graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.11.2. Random bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.11.3. Random trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.11.4. Random planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.11.5. Random regular graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.11.6. Random tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.11.7. Random flow networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.11.8. Randomizing edge weights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3. Modifying graphs ......................................... 37
3.1. Modifying vertices of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.1. Adding and removing single vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2. Modifying edges of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1. Adding and removing single edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.2. Accessing and modifying edge weights . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.3. Contracting edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.4. Subdividing edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3. Using attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1. Graph attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.2. Vertex attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.3. Edge attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4. Import and export ........................................ 43
4.1. Importing graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1.1. Loading graphs from dot files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1.2. The dot file format overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2. Exporting graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.1. Saving graphs in dot format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.2. Saving graph drawings in L
ATE
X format . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5. Graph properties ......................................... 47
5.1. Basic properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.1. Listing vertices and edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.2. Vertex degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.3. Vertex adjacency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.1.4. Edge incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2. Algebraic properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2.1. Adjacency matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2.2. Weight matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2.3. Incidence matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2.4. Characteristic polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.2.5. Graph spectrum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2.6. Seidel spectrum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2.7. Integer graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4Table of contents
5.3. Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.1. Vertex connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.2. Connected and biconnected components . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.3.3. Graph rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3.4. Articulation points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3.5. Strongly connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3.6. Edge connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4. Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4.1. Tree graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4.2. Forest graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.4.3. Height of a tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.4.4. Lowest common ancestor of a pair of nodes . . . . . . . . . . . . . . . . . . . . . . . . 58
5.5. Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.5.1. Vertex distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.5.2. All-pairs vertex distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.5.3. Diameter of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.5.4. Girth of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.6. Acyclic graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.6.1. Checking if a graph is acyclic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.6.2. Topological sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.6.3. st ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.7. Vertex matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.7.1. Maximum matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.7.2. Maximum matching in bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.8. Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.8.1. Clique graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.8.2. Triangle-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.8.3. Maximal cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.8.4. Maximum clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.8.5. Minimum clique cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.9. Vertex coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.9.1. Greedy coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.9.2. Minimal coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.9.3. Chromatic number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.9.4. k-coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.10. Edge coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6. Traversing graphs ........................................ 71
6.1. Walks and tours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.1.1. Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.1.2. Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2. Optimal routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2.1. Shortest paths in unweighted graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2.2. Cheapest paths in weighted graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.2.3. Traveling salesman problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.3. Spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.3.1. Constructing a spanning tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.3.2. Minimal spanning tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.3.3. Counting all spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7. Visualizing graphs ........................................ 75
7.1. Drawing graphs by using various methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.1.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.1.2. Drawing disconnected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.1.3. Spring method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.1.4. Drawing trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Table of contents 5
7.1.5. Drawing planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.1.6. Circular graph drawings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7.2. Custom vertex positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.2.1. Setting vertex positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.2.2. Generating vertex positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.3. Highlighting parts of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
7.3.1. Highlighting vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
7.3.2. Highlighting edges and trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.3.3. Highlighting subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Bibliography ................................................ 85
Command Index .............................................. 87
6Table of contents
Chapter 1
Introduction
1.1. Overview
This document contains an overview of the graph theory commands built in the Giac/Xcas soft-
ware, including the syntax, the detailed description and practical examples for each command.
1.2. Notations used in this manual
7
Chapter 2
Constructing graphs
2.1. General graphs
The commands graph and digraph are used for constructing general graphs.
2.1.1. Creating undirected graphs
The command graph accepts between one and three mandatory arguments, each of them being
one of the following structural elements of the resulting graph:
¡the number or list of vertices (a vertex may be any atomic object, such as an integer, a
symbol or a string); it must be the first argument if used,
¡the set of edges (each edge is a list containing two vertices), a permutation, a trail of edges
or a sequence of trails; it can be either the first or the second argument if used,
¡the adjacency or weight matrix.
Additionally, some of the following options may be appended to the sequence of arguments:
•directed = true or false,
•weighted = true or false,
•color = an integer or a list of integers representing color(s) of the vertices,
•coordinates = a list of vertex 2D or 3D coordinates.
The graph command may also be called by passing a string, representing the name of a special
graph, as its only argument. In that case the corresponding graph will be constructed and returned.
The supported graphs and their names are listed below.
1. Clebsch graph: clebsch
2. Coxeter graph: coxeter
3. Desargues graph: desargues
4. Dodecahedral graph: dodecahedron
5. Dürer graph: durer
6. Dyck graph: dyck
7. Grinberg graph: grinberg
8. Grotzsch graph: grotzsch
9. Harries graph: harries
10. Harries–Wong graph: harries-wong
11. Heawood graph: heawood
9
12. Herschel graph: herschel
13. Icosahedral graph: icosahedron
14. Levi graph: levi
15. Ljubljana graph: ljubljana
16. McGee graph: mcgee
17. Möbius–Kantor graph: mobius-kantor
18. Nauru graph: nauru
19. Octahedral graph: octahedron
20. Pappus graph: pappus
21. Petersen graph: petersen
22. Robertson graph: robertson
23. Truncated icosahedral graph: soccerball
24. Shrikhande graph: shrikhande
25. Tetrahedral graph: tehtrahedron
2.1.2. Creating directed graphs
The digraph command is used for creating directed graphs, although it is also possible with the
graph command by specifying the option directed=true. Actually, calling digraph is the same as
calling graph with that option appended to the sequence of arguments. However, creating special
graphs is not supported by digraph since they are all undirected. Edges in directed graphs are
called arcs. Edges and arcs are different structures: an edge is represented by a two-element set
containing its endpoints, while an arc is represented by the ordered pairs of its endpoints.
The following series of examples demonstrates the various possibilities when using graph and
digraph commands.
2.1.3. Creating vertices
A graph consisting only of vertices and no edges can be created simply by providing the number
of vertices or the list of vertex labels.
>graph(5)
an undirected unweighted graph with 5 vertices and 0 edges
>graph([a,b,c])
an undirected unweighted graph with 3 vertices and 0 edges
2.1.4. Creating edges and arcs
Edges/arcs must be specified inside a set so that it can be distinguished from a (adjacency or
weight) matrix. If only a set of edges/arcs is specified, the vertices needed to establish these will
be created automatically. Note that, when constructing a directed graph, the order of the vertices
in an arc matters; in undirected graphs it is not meaningful.
10 Constructing graphs
>graph(%{[a,b],[b,c],[a,c]%})
an undirected unweighted graph with 3 vertices and 3 edges
Edge weights may also be specified.
>graph(%{[[a,b],2],[[b,c],2.3],[[c,a],3/2]%})
an undirected weighted graph with 3 vertices and 3 edges
If the graph contains isolated vertices (not connected to any other vertex) or a particular order
of vertices is desired, the list of vertices has to be specified first.
>graph([d,b,c,a],%{[a,b],[b,c],[a,c]%})
an undirected unweighted graph with 4 vertices and 3 edges
2.1.5. Creating paths and trails
A directed graph can also be created from a list of nvertices and a permutation of order n.
The resulting graph consists of a single directed path with the vertices ordered according to the
permutation.
>graph([a,b,c,d],[1,2,3,0])
a directed unweighted graph with 4 vertices and 3 arcs
Alternatively, one may specify edges as a trail.
>digraph([a,b,c,d],trail(b,c,d,a))
a directed unweighted graph with 4 vertices and 3 arcs
Using trails is also possible when creating undirected graphs. Also, some vertices in a trail may
be repeated, which is not allowed in a path.
>graph([a,b,c,d],trail(b,c,d,a,c))
an undirected unweighted graph with 4 vertices and 4 edges
There is also the possibility of specifying several trails in a sequence, which is useful for designing
more complex graphs.
>graph(trail(1,2,3,4,2),trail(3,5,6,7,5,4))
an undirected unweighted graph with 7 vertices and 9 edges
2.1.6. Specifying adjacency or weight matrix
A graph can be created from a single square matrix A= [aij]nof order n. If it contains only ones
and zeros and has zeros on its diagonal, it is assumed to be the adjacency matrix for the desired
graph. Otherwise, if an element outside the set f0;1gis encountered, it is assumed that the matrix
of edge weights is passed as input, causing the resulting graph to be weighted accordingly. In each
case, exactly nvertices will be created and i-th and j-th vertex will be connected iff aij =/ 0. If the
matrix is symmetric, the resulting graph will be undirected, otherwise it will be directed.
>graph([[0,1,1,0],[1,0,0,1],[1,0,0,0],[0,1,0,0]])
an undirected unweighted graph with 4 vertices and 3 edges
>graph([[0,1.0,2.3,0],[4,0,0,3.1],[0,0,0,0],[0,0,0,0]])
a directed weighted graph with 4 vertices and 4 arcs
2.1 General graphs 11
List of vertex labels can be specified before the matrix.
>graph([a,b,c,d],[[0,1,1,0],[1,0,0,1],[1,0,0,0],[0,1,0,0]])
an undirected unweighted graph with 4 vertices and 3 edges
When creating a weighted graph, one can first specify the list of nvertices and the set of edges,
followed by a square matrix Aof order n. Then for every edge fi; j gor arc (i; j)the element
aij of Ais assigned as its weight. Other elements of Aare ignored.
>digraph([a,b,c],%{[a,b],[b,c],[a,c]%}, [[0,1,2],[3,0,4],[5,6,0]])
a directed weighted graph with 3 vertices and 3 arcs
When a special graph is desired, one just needs to pass its name to the graph command. An
undirected unweighted graph will be returned.
>graph("petersen")
an undirected unweighted graph with 10 vertices and 15 edges
2.2. Promoting to directed and undirected graphs
2.2.1. Converting edges to pairs of arcs
To promote an existing undirected graph to a directed one or an unweighted graph to a weighted
one, use the commands make_directed and make_weighted, respectively.
The command make_directed is called with one or two arguments, an undirected graph G(V ;
E)and optionally a square matrix of order jVj. Every edge fi; j g 2 Eis replaced with the pair
of arcs (i; j)and (j ; i). If matrix Ais specified, aij and aji are assigned as weights of these arcs,
respectively. Thus a directed (and possibly weighted) graph is created and returned.
>make_directed(cycle_graph(4))
C4: a directed unweighted graph with 4 vertices and 8 arcs
>make_directed(cycle_graph(4), [[0,0,0,1],[2,0,1,3],[0,1,0,4],[5,0,4,0]])
C4: a directed weighted graph with 4 vertices and 8 arcs
2.2.2. Assigning weight matrix to an unweighted graph
The command make_weighted accepts one or two arguments, an unweighted graph G(V ; E)and
optionally a square matrix Aof order jVj. If the matrix specification is omitted, a square matrix
of ones is assumed. Then a copy of Gis returned where each edge/arc (i; j)2Egets aij assigned
as its weight. If Gis an undirected graph, it is assumed that Ais symmetric.
>make_weighted(graph(%{[1,2],[2,3],[3,1]%}), [[0,2,3],[2,0,1],[3,1,0]])
an undirected weighted graph with 3 vertices and 3 edges
2.3. Cycle and path graphs
2.3.1. Cycle graphs
The command cycle_graph is used for constructing a cycle graph of arbitrary order.
12 Constructing graphs
cycle_graph accepts a positive integer nor a list of distinct vertices as its only argument and
returns the graph consisting of a single cycle through the specified vertices in the given order. If n
is specified it is assumed to be the desired number of vertices, in which case they will be created
and labeled with the first nintegers (starting from 0 in Xcas mode and from 1 in Maple mode).
The resulting graph will be given the name Cn, for example C4 for n= 4.
>C5:=cycle_graph(5)
C5: an undirected unweighted graph with 5 vertices and 5 edges
>draw_graph(C5)
0
1
23
4
>cycle_graph(["a","b","c","d","e"])
C5: an undirected unweighted graph with 5 vertices and 5 edges
2.3.2. Path graphs
The command path_graph is used for constructing a path graph of arbitrary length.
path_graph accepts a positive integer nor a list of distinct vertices as its only argument and
returns a graph consisting of a single path through the specified vertices in the given order. If n
is specified it is assumed to be the desired number of vertices, in which case they will be created
and labeled with the first nintegers (starting from 0 in Xcas mode resp. from 1 in Maple mode).
Note that a path cannot intersect itself. Paths that are allowed to cross themselves are called trails
(see the command trail).
>path_graph(5)
an undirected unweighted graph with 5 vertices and 4 edges
>path_graph(["a","b","c","d","e"])
an undirected unweighted graph with 5 vertices and 4 edges
2.3.3. Trails of edges
If the dummy command trail is called with a sequence of vertices as arguments, it returns the
symbolic expression representing the trail of edges through the specified vertices. The resulting
symbolic object is recognizable by graph and digraph commands. Note that a trail may cross
itself (some vertices may be repeated in the given sequence).
>T:=trail(1,2,3,4,2):; graph(T)
Done;an undirected unweighted graph with 4 vertices and 4 edges
2.4. Complete graphs
2.4.1. Complete graphs with multiple vertex partitions
The command complete_graph is used for construction of complete (multipartite) graphs.
2.4 Complete graphs 13
If complete_graph is called with a single argument, a positive integer nor a list of distinct vertices,
it returns the complete graph with the specified vertices. If integer nis specified, it is assumed that
it is the desired number of vertices and they will be created and labeled with the first nintegers
(starting from 0 in Xcas mode and from 1 in Maple mode).
If a sequence of positive integers n1; n2; :::; nkis passed as argument, complete_graph returns the
complete multipartite graph with partitions of size n1; n2; :::; nk.
>K5:=complete_graph(5)
an undirected unweighted graph with 5 vertices and 10 edges
>draw_graph(K5)
0
1
23
4
>K3:=complete_graph([a,b,c])
an undirected unweighted graph with 3 vertices and 3 edges
>edges(K3)
f[a; b];[a; c];[b; c]g
>K33:=complete_graph(3,3)
an undirected unweighted graph with 6 vertices and 9 edges
>draw_graph(K33)
0 1 2
3 4 5
2.4.2. Complete trees
To construct the complete binary tree of depth n, use the command complete_binary_tree which
accepts n(a positive integer) as its only argument.
>complete_binary_tree(2)
an undirected unweighted graph with 7 vertices and 6 edges
To construct the complete k-ary tree of the specified depth use the command complete_kary_tree.
complete_kary_tree accepts kand n(positive integers) as its arguments and returns the complete
k-ary tree of depth n. For example, to get a ternary tree with two levels, input:
>complete_kary_tree(3,2)
an undirected unweighted graph with 13 vertices and 12 edges
14 Constructing graphs
2.5. Sequence graphs
2.5.1. Creating graphs from degree sequences
The command sequence_graph is used for constructing the graph from its degree sequence.
sequence_graph accepts a list Lof positive integers as its only argument and, if Lrepresents a
graphic sequence, the corresponding graph Gwith jLjvertices is returned. If the argument is not
a graphic sequence, an error is returned.
>sequence_graph([3,2,4,2,3,4,5,7])
an undirected unweighted graph with 8 vertices and 15 edges
The graph Gis constructed in O(jLj2log jLj)time by using the algorithm of Havel and Hakimi.
2.5.2. Validating graphic sequences
The command is_graphic_sequence is used to check whether a list of integers represents the
degree sequence of some graph or not.
is_graphic_sequence accepts a list Lof positive integers as its only argument and returns true if
there exists a graph G(V ; E)with degree sequence fdeg v:v2Vgequal to Land false otherwise.
The algorithm, which has the complexity O(jLj2), is based on the theorem of Erd®s and Gallai.
>is_graphic_sequence([3,2,4,2,3,4,5,7])
true
2.6. Intersection graphs
2.6.1. Interval graphs
The command interval_graph is used for construction of interval graphs.
interval_graph accepts a sequence or list of real-line intervals as its argument and returns an
undirected unweighted graph with these intervals as vertices (the string representations of the
intervals are used as labels), each two of them being connected with an edge if and only if the
corresponding intervals intersect.
>G:=interval_graph(0..8,1..pi,exp(1)..20,7..18,11..14,17..24,23..25)
an undirected unweighted graph with 7 vertices and 10 edges
>draw_graph(G)
2.6.2. Kneser graphs
The commands kneser_graph and odd_graph are used for construction of Kneser graphs.
2.6 Intersection graphs 15
kneser_graph accepts two positive integers n≤20 and kas its arguments and returns the Kneser
graph K(n; k). The latter is obtained by setting all k-subsets of a set of nelements as vertices
and connecting each two of them if and only if the corresponding sets are disjoint. Therefore each
Kneser graph is the complement of a certain intersection graph.
Kneser graphs can get exceedingly complex even for relatively small values of nand k. Note that
the number of vertices in K(n; k)is equal to n
k.
>kneser_graph(5,2)
an undirected unweighted graph with 10 vertices and 15 edges
>G:=kneser_graph(8,1)
an undirected unweighted graph with 8 vertices and 28 edges
>draw_graph(G,spring,labels=false)
The command odd_graph is used for creating so-called odd graphs, which are Kneser graphs with
parameters n= 2 d+ 1 and k=dfor d>1.
odd_graph accepts a positive integer d≤8as its only argument and returns d-th odd graph
K(2 d+ 1; d). Note that the odd graphs with d > 8will not be constructed as they are too big to
handle.
>odd_graph(3)
an undirected unweighted graph with 10 vertices and 15 edges
2.7. Special graphs
2.7.1. Hypercube graphs
The command hypercube_graph is used for creating hypercube graphs.
hypercube_graph accepts a positive integer nas its only argument and returns the hypercube
graph of dimension non 2nvertices. The vertex labels are strings of binary digits of length n.
Two vertices are joined by an edge if and only if their labels differ in exactly one character. The
hypercube graph for n= 2 is a square and for n= 3 it is a cube.
>H:=hypercube_graph(3)
an undirected unweighted graph with 8 vertices and 12 edges
>draw_graph(H,planar)
16 Constructing graphs
>H:=hypercube_graph(5)
an undirected unweighted graph with 32 vertices and 80 edges
2.7.2. Star graphs
The command star_graph is used for creating star graphs.
star_graph accepts a positive integer nas its only argument and returns the star graph with n+ 1
vertices, which is equal to the complete bipartite graph complete_graph(1,n) i.e. a n-ary tree
with one level.
>G:=star_graph(5)
an undirected unweighted graph with 6 vertices and 5 edges
>draw_graph(G)
2.7.3. Wheel graphs
The command wheel_graph is used for creating wheel graphs.
wheel_graph accepts a positive integer nas its only argument and returns the wheel graph with
n+ 1 vertices.
>G:=wheel_graph(5)
an undirected unweighted graph with 6 vertices and 10 edges
>draw_graph(G)
2.7.4. Web graphs
The command web_graph is used for creating web graphs.
web_graph accepts two positive integers aand bas its arguments and returns the web graph with
parameters aand b, namely the Cartesian product of cycle_graph(a) and path_graph(b).
>G:=web_graph(7,3)
an undirected unweighted graph with 21 vertices and 35 edges
2.7 Special graphs 17
>draw_graph(G,labels=false)
2.7.5. Prism graphs
The command prism_graph is used for creating prism graphs.
prism_graph accepts a positive integer nas its only argument and returns the prism graph with
parameter n, namely petersen_graph(n,1).
>G:=prism_graph(5)
an undirected unweighted graph with 10 vertices and 15 edges
>draw_graph(G)
2.7.6. Antiprism graphs
The command antiprism_graph is used for creating antiprism graphs.
antiprism_graph accepts a positive integer nas its only argument and returns the antiprism
graph with parameter n, which is constructed from two concentric cycles of nvertices by joining
each vertex of the inner to two adjacent nodes of the outer cycle.
>G:=antiprism_graph(7)
an undirected unweighted graph with 14 vertices and 28 edges
>draw_graph(G)
2.7.7. Grid graphs
The command grid_graph resp. torus_grid_graph is used for creating rectangular resp. torus
grid graphs.
18 Constructing graphs
grid_graph accepts two positive integers mand nas its arguments and returns the mby ngrid
on m·nvertices, namely the Cartesian product of path_graph(m) and path_graph(n).
>G:=grid_graph(15,20)
an undirected unweighted graph with 300 vertices and 565 edges
>draw_graph(G,spring)
Connecting vertices in the opposite corners of the generated grid yields an interesting new graph.
>G:=add_edge(G,[["14:0","0:19"],["0:0","14:19"]])
an undirected unweighted graph with 300 vertices and 567 edges
>draw_graph(G,plot3d)
In the following example, the Möbius strip is constructed by connecting the vertices in the opppo-
site sides of a narrow grid graph.
>G:=grid_graph(20,3)
an undirected unweighted graph with 60 vertices and 97 edges
>G:=add_edge(G,[["0:0","19:2"],["0:1","19:1"],["0:2","19:0"]])
an undirected unweighted graph with 60 vertices and 100 edges
>draw_graph(G,plot3d,labels=false)
torus_grid_graph accepts two positive integers mand nas its arguments and returns the mby n
torus grid on m n vertices, namely the Cartesian product of cycle_graph(m) and cycle_graph(n).
>G:=torus_grid_graph(8,3)
an undirected unweighted graph with 24 vertices and 48 edges
>draw_graph(G,spring,labels=false)
2.7 Special graphs 19
2.7.8. Sierpi«ski graphs
The command sierpinski_graph is used for creating Sierpi«ski-type graphs Sk
nand STk
n[9].
sierpinski_graph accepts two positive integers nand kas its arguments (and optionally the
symbol triangle as the third argument) and returns the Sierpi«ski (triangle) graph with parame-
ters nand k.
The Sierpi«ski triangle graph STk
nis obtained by contracting all non-clique edges in Sk
n. To detect
such edges the variant of the algorithm by Bron and Kerbosch, developed by Tomita et al. in
[20], is used, which can be time consuming for n > 6.
In particular, ST3
nis the well-known Sierpi«ski sieve2.1 graph of order n.
>S:=sierpinski_graph(4,3)
an undirected unweighted graph with 81 vertices and 120 edges
>draw_graph(S,spring)
>sierpinski_graph(4,3,triangle)
an undirected unweighted graph with 42 vertices and 81 edges
>sierpinski_graph(5,3,triangle)
an undirected unweighted graph with 123 vertices and 243 edges
A drawing of the graph produced by the last command line is shown in Figure 4.1.
2.7.9. Generalized Petersen graphs
The command petersen_graph is used for creating generalized Petersen graphs P(n; k).
petersen_graph accepts two arguments, nand k(positive integers). The second argument may
be omitted, in which case k= 2 is assumed. The graph P(n; k), which is returned, is a connected
cubic graph consisting of—in Schläfli notation—an inner star polygon fn; kgand an outer regular
polygon fngsuch that the npairs of corresponding vertices in inner and outer polygons are
connected with edges. For k= 1 the prism graph of order nis obtained.
The well-known Petersen graph is equal to the generalized Petersen graph P(5;2). It can also be
constructed by calling graph("petersen").
2.1.https://en.wikipedia.org/wiki/Sierpinski_triangle
20 Constructing graphs
>draw_graph(graph("petersen"))
To obtain the dodecahedral graph P(10;2), input:
>petersen_graph(10)
an undirected unweighted graph with 20 vertices and 30 edges
To obtain Möbius–Kantor graph P(8;3), input:
>G:=petersen_graph(8,3)
an undirected unweighted graph with 16 vertices and 24 edges
>draw_graph(G)
0 1
2
3
45
6
78 9
10
11
1213
14
15
Note that Desargues, Dürer and Nauru graphs are also generalized Petersen graphs P(10;3),P(6;
2) and P(12;5), respectively.
2.7.10. LCF graphs
The command lcf_graph is used for constructing a cubic Hamiltonian graph from its LCF nota-
tion2.2.
lcf_graph takes one or two arguments, a list Lof nonzero integers, called jumps, and optionally
a positive integer n, called exponent (by default, n= 1). The command returns the graph on njLj
vertices obtained by iterating the sequence of jumps ntimes.
For example, the following command line creates the Frucht graph.
>F:=lcf_graph([-5,-2,-4,2,5,-2,2,5,-2,-5,4,2])
an undirected unweighted graph with 12 vertices and 18 edges
>draw_graph(F,planar)
2.2. For the details about LCF notation, see https://en.wikipedia.org/wiki/LCF_notation.
2.7 Special graphs 21
The following command line constructs the truncated octahedral graph.
>G:=lcf_graph([3,-7,7,-3],6)
an undirected unweighted graph with 24 vertices and 36 edges
>draw_graph(G,planar,labels=false)
2.8. Isomorphic copies of graphs
The commands isomorphic_copy,permute_vertices and relabel_vertices are used for con-
structing isomorphic copies of existing graphs.
2.8.1. Creating an isomorphic copy of a graph
The command isomorphic_copy accepts two arguments, a graph G(V ; E)and a permutation σ
of order jVj, and returns the copy of graph Gwith vertices rearranged according to σ.
>G:=isomorphic_copy(path_graph([1,2,3,4,5]),randperm(5))
an undirected unweighted graph with 5 vertices and 4 edges
>vertices(G)
[2;5;3;4;1]
2.8.2. Permuting graph vertices
The command permute_vertices accepts two arguments, a graph G(V ; E)and a list Lof length
jVjcontaining all vertices from Vin a certain order, and returns a copy of Gwith vertices
rearranged as specified by L.
>G:=permute_vertices(path_graph([a,b,c,d]),[b,d,a,c])
an undirected unweighted graph with 4 vertices and 3 edges
>vertices(G)
[b; d; a; c]
2.8.3. Relabeling graph vertices
The command relabel_vertices accepts two arguments, a graph G(V ; E)and a list Lof vertex
labels, and returns the copy of Gwith vertices relabeled with labels from L.
>P:=path_graph([1,2,3,4])
an undirected unweighted graph with 4 vertices and 3 edges
>edges(P)
22 Constructing graphs
f[1;2];[2;3];[3;4]g
>G:=relabel_vertices(P,[a,b,c,d])
an undirected unweighted graph with 4 vertices and 3 edges
>edges(G)
f[a; b];[b; c];[c; d]g
2.9. Subgraphs
2.9.1. Extracting subgraphs
To extract the subgraph of G(V ; E)formed by edges from L⊂E, use the command subgraph
which accepts two arguments: Gand L.
>K5:=complete_graph(5)
an undirected unweighted graph with 5 vertices and 10 edges
>S:=subgraph(K5,[[1,2],[2,3],[3,4],[4,1]])
an undirected unweighted graph with 4 vertices and 4 edges
>draw_graph(highlight_subgraph(K5,S))
2.9.2. Induced subgraphs
To obtain the subgraph of Ginduced by set of vertices L⊂V, use the command induced_sub-
graph.
induced_subgraph accepts two arguments Gand Land returns the subgraph of Gformed by all
edges in Ewhich have endpoints in L.
>G:=graph("petersen")
an undirected unweighted graph with 10 vertices and 15 edges
>S:=induced_subgraph(G,[5,6,7,8,9])
an undirected unweighted graph with 5 vertices and 5 edges
>draw_graph(highlight_subgraph(G,S))
2.9 Subgraphs 23
2.9.3. Underlying graphs
For every graph G(V ; E)there is an undirected and unweighted graph U(V ; E0), called the
underlying graph of G, where E0is obtained from Eby dropping edge directions.
To construct Uuse the command underlying_graph which accepts Gas its only argument. The
result is obtained by copying Gand “forgetting” the directions of edges as well as their weights.
>G:=digraph(%{[[1,2],6],[[2,3],4],[[3,1],5],[[3,2],7]%})
a directed weighted graph with 3 vertices and 4 arcs
>U:=underlying_graph(G)
an undirected unweighted graph with 3 vertices and 3 edges
>edges(U)
f[1;2];[1;3];[2;3]g
2.10. Operations on graphs
2.10.1. Graph complement
The command graph_complement is used for constructing complements of graphs.
graph_complement accepts a graph G(V ; E)as its only argument and returns the complement
Gc(V ; Ec)of G, where Ecis the largest set containing only edges/arcs not present in G.
>C5:=cycle_graph(5)
C5: an undirected unweighted graph with 5 vertices and 5 edges
>draw_graph(C5)
0
1
23
4
>G:=graph_complement(C5)
an undirected unweighted graph with 5 vertices and 5 edges
>draw_graph(G)
0
1
23
4
2.10.2. Seidel switching
The command seidel_switch is used for Seidel switching in graphs.
24 Constructing graphs
seidel_switch accepts two arguments, an undirected and unweighted graph G(V ; E)and a list
of vertices L⊂V. The result is a copy of Gin which, for each vertex v2L, its neighbors become
its non-neighbors and vice versa.
>S:=seidel_switch(cycle_graph(5),[1,2])
an undirected unweighted graph with 5 vertices and 7 edges
>draw_graph(S)
0
1
23
4
2.10.3. Transposing graphs
The command reverse_graph is used for reversing arc directions in digraphs.
reverse_graph accepts a graph G(V ; E)as its only argument and returns the reverse graph GT(V ;
E0)of Gwhere E0=f(j ; i): (i; j)2Eg, i.e. returns the copy of Gwith the directions of all edges
reversed.
Note that reverse_graph is defined for both directed and undirected graphs, but gives meaningful
results only for directed graphs.
GTis also called the transpose graph of Gbecause adjacency matrices of Gand GTare transposes
of each other (hence the notation).
>G:=digraph(6, %{[1,2],[2,3],[2,4],[4,5]%})
a directed unweighted graph with 6 vertices and 4 arcs
>GT:=reverse_graph(G)
a directed unweighted graph with 6 vertices and 4 arcs
>edges(GT)
f[2;1];[3;2];[4;2];[5;4]g
2.10.4. Union of graphs
The command graph_union is used for constructing union of two or more graphs.
graph_union accepts a sequence of graphs Gk(Vk; Ek)for k= 1;2; :::; n as its argument and returns
the graph G(V ; E)where V=V1[V2[···[Vkand E=E1[E2[···[Ek.
>G1:=graph([1,2,3],%{[1,2],[2,3]%})
an undirected unweighted graph with 3 vertices and 2 edges
>G2:=graph([1,2,3],%{[3,1],[2,3]%})
an undirected unweighted graph with 3 vertices and 2 edges
>G:=graph_union(G1,G2)
an undirected unweighted graph with 3 vertices and 3 edges
>edges(G)
2.10 Operations on graphs 25
f[1;2];[1;3];[2;3]g
2.10.5. Disjoint union of graphs
To construct disjoint union of graphs use the command disjoint_union.
disjoint_union accepts a sequence of graphs Gk(Vk; Ek)for k= 1;2; :::; n as its argument and
returns the graph obtained by labeling all vertices with strings k:v where v2Vkand all edges with
strings k:e where e2Ekand calling the graph_union command subsequently. As all vertices and
edges are labeled differently, it follows jVj=Pk=1
njVkjand jEj=Pk=1
njEkj.
>G:=disjoint_union(cycle_graph([1,2,3]),path_graph([1,2,3]))
an undirected unweighted graph with 6 vertices and 5 edges
>draw_graph(G)
2.10.6. Joining two graphs
The command graph_join is used for joining graphs.
graph_join accepts two graphs Gand Has its arguments and returns the graph which is obtained
by connecting all the vertices of Gto all vertices of H. The vertex labels in the resulting graph
are strings of the form 1:u and 2:v where uis a vertex in Gand vis a vertex in H.
>G:=graph_join(path_graph(2),graph(3))
an undirected unweighted graph with 5 vertices and 7 edges
>draw_graph(G,spring)
1:0
1:1
2:0
2:1 2:2
2.10.7. Power graphs
The command graph_power is used for constructing the powers of a graph.
graph_power accepts two arguments, a graph G(V ; E)and a positive integer k, and returns the
k-th power Gkof Gwith vertices Vsuch that v; w 2Vare connected with an edge if and only if
there exists a path of length at most kin G.
The graph Gkis constructed from its adjacency matrix Akwhich is obtained by adding powers of
the adjacency matrix Aof G:
Ak=X
i=1
k
Ak:
26 Constructing graphs
The above sum is obtained by assigning Ak Aand repeating the instruction Ak (Ak+I)Afor
k¡1times, so exactly kmatrix multiplications are required.
>G:=graph(trail(1,2,3,4,5))
an undirected unweighted graph with 5 vertices and 4 edges
>draw_graph(G,circle)
>P2:=graph_power(G,2)
an undirected unweighted graph with 5 vertices and 7 edges
>draw_graph(P2,circle)
>P3:=graph_power(G,3)
an undirected unweighted graph with 5 vertices and 9 edges
>draw_graph(P3,circle)
2.10.8. Graph products
There are two distinct operations for computing the product of two graphs: Cartesian product and
tensor product. These operations are available in Giac as the commands cartesian_product and
tensor_product, respectively.
The command cartesian_product accepts a sequence of graphs Gk(Vk; Ek)for k= 1;2; :::; n as its
argument and returns the Cartesian product G1×G2×···×Gnof the input graphs. The Cartesian
product G(V ; E) = G1×G2is the graph with list of vertices V=V1×V2, labeled with strings v1:v2
where v12V1and v22V2, such that (u1:v1,u2:v2)2Eif and only if u1is adjacent to u2and v1=v2
or u1=u2and v1is adjacent to v2.
>G1:=graph(trail(1,2,3,4,1,5))
an undirected unweighted graph with 5 vertices and 5 edges
>draw_graph(G1,circle)
2.10 Operations on graphs 27
>G2:=star_graph(3)
an undirected unweighted graph with 4 vertices and 3 edges
>draw_graph(G2,circle=[1,2,3])
>G:=cartesian_product(G1,G2)
an undirected unweighted graph with 20 vertices and 35 edges
>draw_graph(G)
The command tensor_product accepts a sequence of graphs Gk(Vk; Ek)for k= 1;2; :::; n as its
argument and returns the tensor product G1×G2×···×Gnof the input graphs. The tensor product
G(V ; E) = G1×G2is the graph with list of vertices V=V1×V2, labeled with strings v1:v2 where
v12V1and v22V2, such that (u1:v1,u2:v2)2Eif and only if u1is adjacent to u2and v1is adjacent
to v2.
>T:=tensor_product(G1,G2)
an undirected unweighted graph with 20 vertices and 30 edges
>draw_graph(T)
2.10.9. Transitive closure graph
The command transitive_closure is used for constructing the transitive closure graph of the
given graph. Transitive closure of a (directed) graph G(V ; E)is the graph T(V ; E 0)in which two
vertices v; w 2Vare connected by an edge (arc) e=vw 2E0if and only if there exists a (directed)
path from vto win G.
28 Constructing graphs
transitive_closure accepts one or two arguments, the input graph Gand optionally the option
weighted=true (or simply weighted) or the option weighted=false (which is the default). The
command returns the transitive closure Tof the input graph G. If Gis a digraph, then Tis also a
digraph. When weighted=true is specified, the graph Tis weighted such that the weight of edge
v w 2E0is equal to the length (or weight, if Gis weighted) of the shortest path from vto win G.
The lengths/weights of the shortest paths are obtained by the command allpairs_distance if G
is weighted resp. the command vertex_distance if Gis unweighted. Therefore Tis constructed
in at most O(jVj3)time if weighted=true resp. O(jVjjEj)time if weighted=false.
>G:=digraph([1,2,3,4,5,6],%{[1,2],[2,3],[2,4],[4,5],[3,5]%})
a directed unweighted graph with 6 vertices and 5 arcs
>draw_graph(G)
>T:=transitive_closure(G,weighted)
a directed weighted graph with 6 vertices and 9 arcs
>draw_graph(T)
>G:=assign_edge_weights(G,1,99)
a directed weighted graph with 6 vertices and 5 arcs
>draw_graph(G)
>draw_graph(transitive_closure(G,weighted=true))
2.10 Operations on graphs 29
2.10.10. Line graph
The command line_graph is used for constructing the line graph of an undirected graph G(V ; E).
line_graph accepts the input graph Gas its only argument and returns the line graph L(G)with
jEjdistinct vertices, one vertex for each edge in E. Two vertices v1and v2in L(G)are adjacent if
and only if the corresponding edges e1; e22Ehave a common endpoint. The vertices in L(G)are
labeled with strings in form v-w, where e=vw 2E.
>K4:=complete_graph([1,2,3,4])
an undirected unweighted graph with 4 vertices and 6 edges
>L:=line_graph(K4)
an undirected unweighted graph with 6 vertices and 12 edges
>draw_graph(L,spring)
2.10.11. Plane dual graph
The command plane_dual is used for constructing the plane dual graph of an undirected bicon-
nected planar graph.
plane_dual accepts one argument, the input graph G(V ; E)or the list Fof faces of a planar
embedding of G, and returns the graph Hwith faces of Gas its vertices in which two vertices are
adjacent if and only if they share an edge as faces of G.
Note that the concept of dual graph is usually defined for multigraphs2.3. By the strict definition,
every planar multigraph has the corresponding dual multigraph; moreover, the dual of the latter
is equal to the former. Since Giac does not support multigraphs, a simplified definition suitable
for simple graphs is used.
The algorithm runs in O(jVj2)time.
>H:=hypercube_graph(3)
an undirected unweighted graph with 8 vertices and 12 edges
>draw_graph(H,spring)
The cube has six faces, hence its plane dual graph Dhas six vertices. Also, every face obviously
shares an edge with exactly four other faces, so the degree of each vertex in Dis equal to 4.
>D:=plane_dual(H)
2.3. See https://en.wikipedia.org/wiki/Dual_graph for the strict definition of plane dual graph.
30 Constructing graphs
an undirected unweighted graph with 6 vertices and 12 edges
>draw_graph(D,spring)
A graph isomorphic to Dis obtained when passing a list of faces of Hto the plane_dual command.
The order of vertices is determined by the order of faces.
>is_planar(H,F)
Done;true
>plane_dual(F)
an undirected unweighted graph with 6 vertices and 12 edges
2.11. Random graphs
2.11.1. Random general graphs
The commands random_graph and random_digraph are used for generating general graphs at
random.
random_graph and random_digraph both accept two arguments. The first argument is a positive
integer nor a list of labels Lof length n. The second argument is a positive real number p < 1or
a positive integer m. The command returns a random (di)graph on nvertices (using elements of
Las vertex labels) in which each edge/arc is inserted with probability por which contains exactly
medges/arcs chosen at random.
>G:=random_digraph(10,0.2)
a directed unweighted graph with 10 vertices and 15 arcs
>draw_graph(G,spring,labels=false)
>G:=random_graph(1000,0.01)
an undirected unweighted graph with 1000 vertices and 4922 edges
>is_connected(G)
true
>is_biconnected(G)
2.11 Random graphs 31
false
>G:=random_graph(100,99)
an undirected unweighted graph with 100 vertices and 99 edges
>is_tree(G)
false
>draw_graph(G,spring)
2.11.2. Random bipartite graphs
The command random_bipartite_graph is used for generating bipartite graphs at random.
random_bipartite_graph accepts two arguments. The first argument is either a positive integer
nor a list of two positive integers aand b. The second argument is either a positive real number
p < 1or a positive integer m. The command returns a random bipartite graph on nvertices (or
with two partitions of sizes aand b) in which each possible edge is present with probability p(or
medges are inserted at random).
>G:=random_bipartite_graph([3,4],0.5)
an undirected unweighted graph with 7 vertices and 8 edges
>draw_graph(G)
>G:=random_bipartite_graph(30,60)
an undirected unweighted graph with 30 vertices and 60 edges
2.11.3. Random trees
The command random_tree is used for generating tree graphs uniformly at random.
random_tree accepts a positive integer nas its only argument and returns a random tree generated
on nnodes (i.e. inserts n¡1edges in the initially empty graph).
>T:=random_tree(30)
an undirected unweighted graph with 30 vertices and 29 edges
32 Constructing graphs
>draw_graph(T,labels=false)
2.11.4. Random planar graphs
The command random_planar_graph is used for generating random planar graphs, controlling
edge density and vertex connectivity.
random_planar_graph accepts two or three arguments, a positive integer n(or a list Lof length
n), a positive real number p < 1and optionally an integer k2f0;1;2;3g(by default, k= 1). The
command returns a random k-connected planar graph on nvertices (using elements of Las vertex
labels).
The result is obtained by first generating a random maximal planar graph and then attempting
to remove each edge with probability p, maintaining the k-connectivity of the graph (if k= 0, the
graph may be disconnected). The running time is O(jVj)if k= 0,O(jVj2)if k2f1;2gand O(jVj3)
if k= 3.
The following command line generates a biconnected planar graph.
>G:=random_planar_graph(20,0.8,2)
an undirected unweighted graph with 20 vertices and 25 edges
>draw_graph(G,planar,labels=false)
The command line below generates a triconnected planar graph.
>G:=random_planar_graph(15,0.9,3)
an undirected unweighted graph with 15 vertices and 25 edges
>draw_graph(G,planar,labels=false)
The next command line generates a disconnected planar graph with high probability.
>G:=random_planar_graph(30,0.9,0)
an undirected unweighted graph with 30 vertices and 23 edges
>is_forest(G)
2.11 Random graphs 33
true
>draw_graph(G,spring,labels=false)
By default, a connected planar graph is generated, like in the following example.
>G:=random_planar_graph(15,0.618)
an undirected unweighted graph with 15 vertices and 19 edges
>is_connected(G)
true
>is_biconnected(G)
false
>articulation_points(G)
[1;2;4;10;11]
>draw_graph(G,planar)
2.11.5. Random regular graphs
The command random_regular_graph is used for generating random d-regular graphs on a certain
set of vertices, using the algorithm presented in [17]2.4.
random_regular_graph accepts two mandatory arguments, a positive integer n(or a list Lof
length n) and a nonnegative integer d. Optionally, the option connected may be specified as the
third argument, indicating that the generated graph must be 1-connected (by default no restriction
is made). The command creates nvertices (using elements of Las vertex labels) and returns a
random d-regular (connected) graph on these vertices.
Note that a d-regular graph on nvertices exists if and only if n > d + 1 and n d is even. If these
conditions are not met, random_regular_graph returns an error.
This algorithm generates regular graphs with approximately uniform probability. It means that
for n!1 and dnot growing so quickly with nthe probability distribution converges to uniformity.
The runtime of the algorithm is negligible for n6100. For n > 200 the algorithm is considerably
slower.
>G:=random_regular_graph(16,3)
an undirected unweighted graph with 16 vertices and 24 edges
2.4. See Algorithm 2 on page 2.
34 Constructing graphs
>is_regular(G)
true
>degree_sequence(G)
[3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3]
>draw_graph(G,spring)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2.11.6. Random tournaments
The command random_tournament is used for generating random tournaments. A tournament of
order nis a graph obtained by assigning a direction to each edge in a complete graph Kn(for each
edge there are two possible directions).
random_tournament accepts a positive integer n(or a list Lof length n) as its only argument and
returns a random tournament on nvertices. If Lis specified, its elements are used to label the
vertices.
>G:=random_tournament([1,2,3,4])
a directed unweighted graph with 4 vertices and 6 arcs
>is_tournament(G)
true
>draw_graph(G)
2.11.7. Random flow networks
Giac]
2.11.8. Randomizing edge weights
The command assign_edge_weights is used for assigning weights to edges of a graph at random.
assign_edge_weights accepts two or three arguments. The first argument is always the input
graph G(V ; E). If only two arguments are given, the second one is an interval a..b of real numbers.
Otherwise, if three arguments are given, the second resp. the third argument is a positive integer
mresp. n. The command operates such that for each edge e2E, its weight is chosen uniformly
from the real interval [a; b)or from the set of integers lying between mand n, including both m
and n. After assigning weights to all edges, the modified copy of Gis returned.
2.11 Random graphs 35
>G:=assign_edge_weights(grid_graph(5,3),1,99)
an undirected weighted graph with 15 vertices and 22 edges
>draw_graph(G,spring)
>G:=assign_edge_weights(graph_complement(complete_graph(2,3,4)),e..pi)
an undirected weighted graph with 9 vertices and 10 edges
>draw_graph(G)
36 Constructing graphs
Chapter 3
Modifying graphs
3.1. Modifying vertices of a graph
3.1.1. Adding and removing single vertices
For adding and removing vertices to/from graphs use the commands add_vertex and
delete_vertex, respectively.
The command add_vertex accepts two arguments, a graph G(V ; E)and a single label vor a list
of labels L, and returns the graph G0(V[fvg; E)or G00 (V[L; E)if a list Lis given.
>K5:=complete_graph([1,2,3,4,5])
an undirected unweighted graph with 5 vertices and 10 edges
>add_vertex(K5,6)
an undirected unweighted graph with 6 vertices and 10 edges
>add_vertex(K5,[a,b,c])
an undirected unweighted graph with 8 vertices and 10 edges
Note that vertices already present in Gwon't be added. For example:
>add_vertex(K5,[4,5,6])
an undirected unweighted graph with 6 vertices and 10 edges
The command delete_vertex accepts two arguments, a graph G(V ; E)and a single label vor a
list of labels L, and returns the graph
G0(Vnfvg;fe2E:eis not incident to vg)
or, if Lis given,
G00 (VnL; fe2E:eis not incident to any v2Lg):
If any of the specified vertices does not belong to G, an error is returned.
>delete_vertex(K5,2)
an undirected unweighted graph with 4 vertices and 6 edges
>delete_vertex(K5,[2,3])
an undirected unweighted graph with 3 vertices and 3 edges
3.2. Modifying edges of a graph
3.2.1. Adding and removing single edges
For adding and removing edges or arcs to/from graphs use the commands add_edge or add_arc
and delete_edge and delete_arc, respectively.
37
The command add_edge accepts two arguments, an undirected graph G(V ; E)and an edge or a list
of edges or a trail of edges (entered as a list of vertices), and returns the copy of Gwith the specified
edges inserted. Edge insertion implies creation of its endpoints if they are not already present.
>C4:=cycle_graph(4)
C4: an undirected unweighted graph with 4 vertices and 4 edges
>add_edge(C4,[1,3])
C4: an undirected unweighted graph with 4 vertices and 5 edges
>add_edge(C4,[1,3,5,7])
C4: an undirected unweighted graph with 6 vertices and 7 edges
The command add_arc works similarly to add_edge but applies only to directed graphs. Note that
the order of endpoints in an arc matters.
>add_arc(digraph(trail(a,b,c,d,a)),[[a,c],[b,d]])
a directed unweighted graph with 4 vertices and 6 arcs
When adding edge/arc to a weighted graph, its weight should be specified alongside its endpoints,
or it will be assumed that it equals to 1.
>add_edge(graph(%{[[1,2],5],[[3,4],6]%}),[[2,3],7])
an undirected weighted graph with 4 vertices and 3 edges
3.2.2. Accessing and modifying edge weights
The commands get_edge_weight and set_edge_weight are used to access and modify the weight
of an edge/arc in a weighted graph, respectively.
set_edge_weight accepts three arguments: a weighted graph G(V ; E), edge/arc e2Eand the
new weight w, which may be any number. It returns the modified copy of G.
The command get_edge_weight accepts two arguments, a weighted graph G(V ; E)and an edge
or arc e2E. It returns the weight of e.
>G:=set_edge_weight(graph(%{[[1,2],4],[[2,3],5]%}),[1,2],6)
an undirected weighted graph with 3 vertices and 2 edges
>get_edge_weight(G,[1,2])
6
3.2.3. Contracting edges
The command contract_edge is used for contracting (collapsing) edges in a graph.
contract_edge accepts two arguments, a graph G(V ; E)and an edge/arc e= (v; w)2E, and
merges wand vinto a single vertex, deleting the edge e. The resulting vertex inherits the label of
v. The command returns the modified graph G0(Vnfwg; E0).
>K5:=complete_graph(5)
an undirected unweighted graph with 5 vertices and 10 edges
>contract_edge(K5,[1,2])
38 Modifying graphs
an undirected unweighted graph with 4 vertices and 6 edges
To contract a set fe1; e2; :::; ekg⊂Eof edges in G, none two of which are incident (i.e. when the
given set is a matching in G), one can use the foldl command. In the following example, the
complete graph K5is obtained from Petersen graph by edge contraction.
>P:=graph("petersen")
an undirected unweighted graph with 10 vertices and 15 edges
>G:=foldl(contract_edge,P,[0,5],[1,6],[2,7],[3,8],[4,9])
an undirected unweighted graph with 5 vertices and 10 edges
>draw_graph(G)
0
1
23
4
3.2.4. Subdividing edges
The command subdivide_edges is used for subdividing edges of a graph.
subdivide_edges accepts two or three arguments, a graph G(V ; E), a single edge/arc or a list
of edges/arcs in Eand optionally a positive integer r(which defaults to 1). Each of the specified
edges/arcs will be subdivided with exactly rnew vertices, labeled with the smallest available
integers. The resulting graph, which is homeomorphic to G, is returned.
If the endpoints of the edge being subdivided have valid coordinates, the coordinates of the inserted
vertices will be computed accordingly.
>G:=graph("petersen")
an undirected unweighted graph with 10 vertices and 15 edges
>G:=subdivide_edges(G,[2,3])
an undirected unweighted graph with 11 vertices and 16 edges
>G:=subdivide_edges(G,[[1,2],[3,4]])
an undirected unweighted graph with 13 vertices and 18 edges
>G:=subdivide_edges(G,[0,1],2)
an undirected unweighted graph with 15 vertices and 20 edges
>draw_graph(G)
0
1
23
4
5
6
78
9
10
11
12
13
14
3.2 Modifying edges of a graph 39
3.3. Using attributes
3.3.1. Graph attributes
The graph structure maintains a set of attributes as tag-value pairs which can be accessed and
modified by the user.
The command set_graph_attribute is used for modifying the existing graph attributes or adding
new ones. It accepts two arguments, a graph Gand a sequence or list of graph attributes in form
tag=value where tag is any string. Alternatively, attributes may be specified as a sequence of two
lists [tag1,tag2,...] and [value1,value2,...]. The command sets the specified values to the
indicated attribute slots, which are meant to represent some global properties of the graph G, and
returns the modified copy of G.
The previously set graph attribute values can be fetched with the command get_graph_attribute
which accepts two arguments: a graph Gand a sequence or list of tags. The corresponding values
will be returned in a sequence or list, respectively. If some attribute is not set, undef is returned
as its value.
To list all graph attributes of Gfor which the values are set, use the list_graph_attributes
command which takes Gas its only argument.
To discard a graph attribute, use the discard_graph_attribute command. It accepts two argu-
ments: a graph Gand a sequence or list of tags to be cleared, and returns the modified copy of G.
Two tags are normally being used by the CAS commands: directed and weighted, so it is not advis-
able to overwrite their values using this command (instead, use make_directed,make_weighted
and underlying_graph commands). Another attribute used internally is name, which holds the
name of the respective graph (as a string).
>G:=digraph(trail(1,2,3,1))
a directed unweighted graph with 3 vertices and 3 arcs
>G:=set_graph_attribute(G,"name"="C3","message"="this is some text")
C3: a directed unweighted graph with 3 vertices and 3 arcs
>get_graph_attribute(G,"message")
this is some text
>list_graph_attributes(G)
[directed =true;weighted =false;name =C3;message =this is some text]
>G:=discard_graph_attribute(G,"message")
C3: a directed unweighted graph with 3 vertices and 3 arcs
>list_graph_attributes(G)
[directed =true;weighted =false;name =C3]
3.3.2. Vertex attributes
For every vertex of a graph, the list of attributes in form of tag-value pairs is maintained, which
can be accessed and modified by the user.
The command set_vertex_attribute is used for modifying the existing vertex attributes or
adding new ones. It accepts three arguments, a graph G(V ; E), a vertex v2Vand a sequence or list
of attributes in form tag=value where tag is any string. Alternatively, attributes may be specified
as a sequence of two lists [tag1,tag2,...] and [value1,value2,...]. The command sets the
specified values to the indicated attributes of the vertex vand returns the modified copy of G.
40 Modifying graphs
The previously set attribute values for vcan be fetched with the command get_vertex_attribute
which accepts three arguments: G,vand a sequence or list of tags. The corresponding values will
be returned in a sequence or list, respectively. If some attribute is not set, undef is returned as
its value.
To list all attributes of vfor which the values are set, use the list_vertex_attributes command
which takes two arguments, Gand v.
The discard_vertex_attribute command is used for discarding attribute(s) assigned to some
vertex v2V. It accepts three arguments: G,vand a sequence or list of tags to be cleared, and
returns the modified copy of G.
The attributes label,color,shape and pos are also used internally. These hold the vertex label, color,
shape and coordinates in a drawing, respectively. If the color is not set for a vertex, the latter is
drawn in yellow. The shape attribute may have one of the following values: square,triangle,diamond,
star or plus. If the shape attribute is not set or has a different value, the circled shape is applied
when drawing the vertex.
The following example shows how to change individual labels and colors.
>T:=complete_binary_tree(3)
an undirected unweighted graph with 15 vertices and 14 edges
>T:=set_vertex_attribute(T,5,"label"="root","color"=red)
an undirected unweighted graph with 15 vertices and 14 edges
>draw_graph(T,tree="root")
0
1
2
3 4
root
6
7 8 9 10
11 12
13 14
A vertex may also hold custom attributes.
>T:=set_vertex_attribute(T,"root","depth"=3,"shape"="square")
an undirected unweighted graph with 15 vertices and 14 edges
>list_vertex_attributes(T,"root")
[label =root;color =r e d; shape =square;depth = 3]
>T:=discard_vertex_attribute(T,"root","color")
an undirected unweighted graph with 15 vertices and 14 edges
>list_vertex_attributes(T,"root")
[label =root;shape =square;depth = 3]
3.3.3. Edge attributes
For every edge of a graph, the list of attributes in form of key-value pairs is maintained, which can
be accessed and modified by the user.
The command set_edge_attribute is used for modifying the existing edge attributes or adding
new ones. It accepts three arguments, a graph G(V ; E), an edge/arc e2Eand a sequence or list
of attributes in form tag=value where tag is any string. Alternatively, attributes may be specified
as a sequence of two lists [tag1,tag2,...] and [value1,value2,...]. The command sets the
specified values to the indicated attributes of the edge/arc eand returns the modified copy of G.
3.3 Using attributes 41
The previously set attribute values for ecan be fetched with the command get_edge_attribute
which accepts three arguments: G,eand a sequence or list of tags. The corresponding values will
be returned in a sequence or list, respectively. If some attribute is not set, undef is returned as
its value.
To list all attributes of efor which the values are set, use the list_edge_attributes command
which takes two arguments, Gand e.
To discard attribute(s) assigned to ecall the discard_edge_attribute command, which accepts
three arguments: G,eand a sequence or list of tags to be cleared, and returns the modified copy
of G.
The attributes weight,color,style,pos and temp are also used internally. They hold the edge weight,
color, line style, the coordinates of the weight label anchor (and also the coordinates of the arrow)
and true if the edge is temporary. If the color attribute is not set for an edge, the latter is drawn
in blue, unless it is a temporary edge, in which case it is drawn in light grey. The style attribute
may have one of the following values: dashed,dotted or bold. If the style attribute is not set or has
a different value, the solid line style is applied when drawing the edge.
The following example illustrates the possibilities of using edge attributes.
>T:=complete_binary_tree(3)
an undirected unweighted graph with 15 vertices and 14 edges
>T:=set_edge_attribute(T,[1,4],"cost"=12.8,"message"="this is some text")
an undirected unweighted graph with 15 vertices and 14 edges
>list_edge_attributes(T,[1,4])
[cost =12.8;message =this is some text]
>T:=discard_edge_attribute(T,[1,4],"message")
an undirected unweighted graph with 15 vertices and 14 edges
>T:=set_edge_attribute(T,[1,4],"style"="dotted","color"=magenta)
an undirected unweighted graph with 15 vertices and 14 edges
>list_edge_attributes(T,[1,4])
[color =m a g e n t a; style =dotted;cost =12.8]
>T:=set_edge_attribute(T,[5,11],"temp"=true)
an undirected unweighted graph with 15 vertices and 14 edges
>draw_graph(T)
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
42 Modifying graphs
Chapter 4
Import and export
4.1. Importing graphs
4.1.1. Loading graphs from dot files
The command import_graph is used for importing a graph from text file in dot format4.1.
import_graph accepts a string filename as its only argument and returns the graph constructed
from instructions written in the file filename or undef on failure. The passed string should contain
the path to a file in dot format. The file extension .dot may be omitted in the filename since dot
is the only supported format. The alternative extension is .gv,4.2 which must be explicitly specified.
If a relative path to the file is specified, i.e. if it does not contain a leading forward slash, the
current working directory (which can be obtained by calling the pwd command) will be used as the
reference. The working directory can be changed by using the command cd.
For example, assume that the file example.dot is saved in the directory Documents/dot/ with the
following contents:
graph "Example graph" {
a [label="Foo"];
b [shape=diamond,color=red];
a -- b [style=bold];
b -- c [color=green];
b -- d [style=dotted];
}
To import the graph, input:
>G:=import_graph("Documents/dot/example.dot")
Example graph: an undirected unweighted graph with 4 vertices and 3 edges
>draw_graph(G)
Foo
b
c d
4.1.2. The dot file format overview
Giac has some basic support for dot language4.3. Each dot file is used to hold exactly one graph
and should consist of a single instance of the following environment:
strict? (graph | digraph) name? {
...
}
4.1.https://en.wikipedia.org/wiki/DOT_(graph_description_language)
4.2. Although it is recommended to use .gv as the extension for dot files to avoid a certain confusion between different
file types, Giac uses the .dot extension because it coincides with the format name. This may change in the future.
4.3. For the complete syntax definition see https://www.graphviz.org/doc/info/lang.html.
43
The keyword strict may be omitted, as well as the name of the graph, as indicated by the question
marks. The former is used to differentiate between simple graphs (strict) and multigraphs (non-
strict). Since Giac supports only simple graphs, strict is redundant.
For specifying undirected graphs the keyword graph is used, while the digraph keyword is used
for undirected graphs.
The graph/digraph environment contains a series of instructions describing how the graph should
be built. Each instruction ends with the semicolon (;) and has one of the following forms.
syntax creates
vertex_name [attributes]? isolated vertices
V1 <edgeop> V2 <edgeop> ::: <edgeop> Vk [attributes]? edges and trails
graph [attributes] graph attributes
Here, attributes is a comma-separated list of tag-value pairs in form tag=value,<edgeop> is
-- for undirected and -> for directed graphs. Each of V1,V2 etc. is either a vertex name or a set
of vertex names in form {vertex_name1 vertex_name2 ...}. In the case a set is specified, each
vertex from that set is connected to the neighbor operands. Every specified vertex will be created
if it does not exist yet.
Any line beginning with #is ignored. C-like line and block comments are recognized and skipped
as well.
Using the dot syntax it is easy to specify a graph with adjacency lists. For example, the following
is the contents of a file which defines the octahedral graph with 6 vertices and 12 edges.
# octahedral graph
graph "octahedron" {
1 -- {3 6 5 4};
2 -- {3 4 5 6};
3 -- {5 6};
4 -- {5 6};
}
4.2. Exporting graphs
The command export_graph is used for saving graphs to disk in dot or L
ATE
X format.
4.2.1. Saving graphs in dot format
export_graph accepts two mandatory arguments, a graph Gand a string filename, and writes G
to the file specified by filename, which must be a path to the file, either relative or absolute; in
the former case the current working directory will be used as the reference. If only two arguments
are given the graph is saved in dot format. The file name may be entered with or without .dot
extension. The command returns 1 on success and 0 on failure.
>export_graph(G,"Documents/dot/copy_of_philosophers")
1
4.2.2. Saving graph drawings in L
A
TE
X format
When calling the export_graph command, an optional third argument in form latex[=<params>]
may be given. In that case the drawing of G(obtained by calling the draw_graph command) will
be saved to the L
ATE
X file indicated by filename (the extension .tex may be omitted). Optionally,
one can specify a parameter or list of parameters params which will be passed to the draw_graph
command.
44 Import and export
For example, let us create a picture of the Sierpi«ski sieve graph of order n= 5, i.e. the graph ST3
5.
>G:=sierpinski_graph(5,3,triangle)
an undirected unweighted graph with 123 vertices and 243 edges
>export_graph(G,"Documents/st53.tex",latex=[spring,labels=false])
1
The L
ATE
X file obtained by exporting a graph is easily converted into an EPS file, which can
subsequently be inserted4.4 in a paper, report or some other document. A Linux user simply needs
to launch a terminal emulator, navigate to the directory in which the exported file, in this case
st53.tex, is stored and enter the following command:
latex st53.tex && dvips st53.dvi && ps2eps st53.ps
This will produce the (properly cropped) st53.eps file in the same directory. Afterwards, it is
recommended to enter
rm st53.tex st53.aux st53.log st53.dvi st53.ps
to delete the intermediate files. The above two commands can be combined in a simple shell script
which takes the name of the exported file (without the extension) as its input argument:
#!/bin/bash
# convert LaTeX to EPS
latex $1.tex
dvips $1.dvi
ps2eps $1.ps
rm $1.tex $1.aux $1.log $1.dvi $1.ps
Assuming that the script is stored under the name latex2eps in the same directory as st53.tex,
to do the conversion it is enough to input:
bash latex2eps st53
The drawing produced in our example is shown in Figure 4.1.
Fig. 4.1. drawing of the Sierpi«ski graph ST3
5using L
AT
E
X and PSTricks
4.4. Alternatively, a PSTricks picture from the body of the .tex file can be copied to some other L
AT
E
X document.
4.2 Exporting graphs 45
Chapter 5
Graph properties
5.1. Basic properties
5.1.1. Listing vertices and edges
The command vertices or graph_vertices resp. edges is used for extracting set of vertices
resp. set of edges from a graph.
vertices or graph_vertices accepts a graph G(V ; E)as its only argument and returns the set
of vertices Vin the same order in which they were created.
edges accepts one or two arguments, a graph G(V ; E)and optionally the identifier weights. The
command returns the set of edges E(in a non-meaningful order). If weights is specified, each edge
is paired with the corresponding weight (in this case Gmust be a weighted graph).
>G:=hypercube_graph(2)
an undirected unweighted graph with 4 vertices and 4 edges
>vertices(G)
[00;01;10;11]
>C:=graph("coxeter")
an undirected unweighted graph with 28 vertices and 42 edges
>vertices(C)
[a1; a2; a7; z1; a3; z2; a4; z3; a5; z4; a6; z5; z6; z7; b1; b3; b6; b2; b4; b7; b5; c1; c4; c5; c2; c6; c3; c7]
>H:=digraph([[0,2.32,0,0.25],[0,0,0,1.32],[0,0.50,0,0],[0.75,0,3.34,0]])
a directed weighted graph with 4 vertices and 6 arcs
>edges(H)
f[0;1];[0;3];[1;3];[2;1];[3;0];[3;2]g
>edges(H,weights)
f[[0;1];2.32];[[0;3];0.25];[[1;3];1.32];[[2;1];0.5];[[3;0];0.75];[[3;2];3.34]g
5.1.2. Vertex degrees
The command vertex_degree is used for computing the degree of a vertex, i.e. counting the
vertices adjacent to it.
vertex_degree accepts two arguments, a graph G(V ; E)and a vertex v2V, and returns the
cardinality of the set fw2V: (v; w)2Eg, i.e. the number of vertices in Vwhich are adjacent to v.
When dealing with directed graphs, one can also use the specialized command vertex_in_degree
resp. vertex_out_degree which accepts the same arguments as vertex_degree but returns the
number of arcs (w; v)2Eresp. the number of arcs (v; w)2E, where w2V.
>G:=graph(trail(1,2,3,4,1,5,6,7,1,8,9,4))
47
an undirected unweighted graph with 9 vertices and 11 edges
>draw_graph(G)
>vertex_degree(G,1)
5
>T:=random_tournament([1,2,3,4,5])
a directed unweighted graph with 5 vertices and 10 arcs
>draw_graph(T)
>vertex_out_degree(T,1)
3
>vertex_in_degree(T,5)
2
To obtain the list of degrees of all vertices v2V, use the degree_sequence command.
degree_sequence accepts a graph G(V ; E)as its only argument and returns the list of degrees of
vertices from Vin the same order as returned by the command vertices. If Gis a digraph, arc
directions are ignored.
>degree_sequence(G)
[5;2;2;3;2;2;2;2;2]
5.1.3. Vertex adjacency
The command has_edge is used for checking if two vertices in an undirected graph are adjacent
or not.
has_edge accepts two arguments, the input graph G(V ; E)and a list [u,v] where u; v 2V. The
command returns true if uv 2Eand false otherwise.
For digraphs, there is the similar command has_arc with the same input syntax. Note, however,
that the order of vertices uand vmatters this time.
>G:=graph(trail(1,2,3,4,5,2))
an undirected unweighted graph with 5 vertices and 5 edges
>has_edge(G,[1,2])
true
48 Graph properties
>has_edge(G,[2,1])
true
>has_edge(G,[1,3])
false
>D:=digraph(trail(1,2,3,4,5,2))
a directed unweighted graph with 5 vertices and 5 arcs
>has_arc(D,[1,2])
true
>has_arc(D,[2,1])
false
The command neighbors is used for obtaining the list of vertices in a graph that are adjacent to
the particular vertex or the complete adjacency structure of the graph, in sparse form.
neighbors accepts one or two arguments. The first, mandatory argument is the input graph
G(V ; E). The second, optional argument is a vertex v2V. The command returns the list of
neighbors of vin Gif vis given and the list of lists of neighbors for all vertices in V, in order of
vertices(G), otherwise.
Note that neighbors works for undirected as well as for directed graphs, but ignores edge directions
in the latter case.
>neighbors(G,3)
[2;4]
>neighbors(G)
f[2];[1;3;5];[2;4];[3;5];[2;4]g
The command departures resp. arrivals is used for determining all neighbors of a vertex vin a
digraph which are the heads resp. the tails of the corresponding arcs.
departures resp. arrivals accepts one or two arguments, the input digraph G(V ; E)and option-
ally a vertex v2V, and returns the list Lvcontaining all vertices w2Vfor which v w 2E
resp. wv 2E. If vis omitted, the list of lists Lvfor every v2Vis returned.
>G:=digraph(trail(1,2,3,4,2,5,1,6,7,8,4))
a directed unweighted graph with 8 vertices and 10 arcs
>draw_graph(G,spring)
>departures(G,2); arrivals(G,2); departures(G,1); arrivals(G,1)
[3;5];[1;4];[2;6];[5]
5.1.4. Edge incidence
The command incident_edges is used for obtaining edges incident to the given vertex in a graph.
5.1 Basic properties 49
incident_edges accepts two argument, the input graph G(V ; E)and a vertex v2Vor a list of
vertices L⊂V. The command returns the list of edges e1; e2; :::; ek2Ewhich have vas one of its
endpoints.
Note that edge directions are ignored when Gis a digraph. To obtain only outgoing or incoming
edges, use the commands departures and arrivals, respectively.
>G:=cycle_graph([1,2,3,4,5])
C5: an undirected unweighted graph with 5 vertices and 5 edges
>incident_edges(G,1)
f[1;2];[1;5]g
>incident_edges(G,[2,4,5])
f[1;2];[1;5];[2;3];[3;4];[4;5]g
>G:=random_tournament([1,2,3,4,5])
a directed unweighted graph with 5 vertices and 10 arcs
>incident_edges(G,2)
f[2;1];[2;3];[2;5];[4;2]g
5.2. Algebraic properties
5.2.1. Adjacency matrix
The command adjacency_matrix is used for obtaining the adjacency matrix of a graph G(V ; E)
where V=fv1; v2; :::; vng.
adjacency_matrix accepts the input graph Gas its only argument and returns the square matrix
A= [aij]of order nsuch that, for i; j = 1;2; :::; n,
aij =1, if the set Econtains edge/arc vivj,
0;otherwise:
Note that tr (A) = 0. Also, the adjacency matrix of an undirected graph is always symmetrical.
>G:=graph("octahedron")
an undirected unweighted graph with 6 vertices and 12 edges
>A:=adjacency_matrix(G)
0
B
B
B
B
B
B
@
011110
101101
110011
110011
101101
011110
1
C
C
C
C
C
C
A
>transpose(A)==A
true
>D:=digraph(trail(1,2,3,4,5,2,6,7,3,8,1))
a directed unweighted graph with 8 vertices and 10 arcs
50 Graph properties
>draw_graph(D)
1
2
3
4
5 6
7 8
>A:=adjacency_matrix(D)
0
B
B
B
B
B
B
B
B
B
B
@
01000000
00100100
00010001
00001000
01000000
00000010
00100000
10000000
1
C
C
C
C
C
C
C
C
C
C
A
>transpose(A)==A
false
5.2.2. Weight matrix
The command weight_matrix is used for obtaining the weight matrix of a weighted graph G(V ; E)
where V=fv1; v2; :::; vng.
weight_matrix accepts the input graph Gas its only argument and returns the square matrix
M= [mij]of order nsuch that mij equals zero if viand vjare not adjacent and the weight of the
edge/arc vivjotherwise, for all i; j = 1;2; :::; n (note that the weight of an edge/arc may be any
real number).
Note that tr (M) = 0. Also, the weight matrix of an undirected graph is always symmetrical.
>G:=graph(%{[[1,2],1],[[2,3],2],[[4,5],3],[[5,2],4]%})
an undirected weighted graph with 5 vertices and 4 edges
>weight_matrix(G)
0
B
B
B
B
@
01000
10204
02000
00003
04030
1
C
C
C
C
A
5.2.3. Incidence matrix
The command incidence_matrix is used for obtaining the incidence matrix of a graph.
incidence_matrix accepts the input graph G(V ; E), where V=fv1; v2; :::; vngand E=fe1; e2; :::;
emg, as its only argument and returns the n×mmatrix B= [bi j]such that, for all i= 1;2; :::; n
and j= 1;2; :::; m,
bij =1;if the vertex viis incident to the edge ej,
0;otherwise
5.2 Algebraic properties 51
if Gis undirected resp.
bij =8
<
:
1;if the vertex viis the head of the arc ej,
¡1;if the vertex viis the tail of the arc ej,
0;otherwise
if Gis directed.
>K4:=complete_graph([1,2,3,4])
an undirected unweighted graph with 4 vertices and 6 edges
>edges(K4)
f[1;2];[1;3];[1;4];[2;3];[2;4];[3;4]g
>incidence_matrix(K4)
0
B
B
@
111000
100110
010101
001011
1
C
C
A
>DG:=digraph(trail(1,2,3,4,5,3),trail(1,5,2,4,1))
a directed unweighted graph with 5 vertices and 9 arcs
>draw_graph(DG)
1
2
34
5
>edges(DG)
f[1;2];[1;5];[2;3];[2;4];[3;4];[4;1];[4;5];[5;2];[5;3]g
>incidence_matrix(DG)
0
B
B
B
B
@
¡1¡10001000
1 0 ¡1¡100010
0010¡10001
00011¡1¡1 0 0
0100001¡1¡1
1
C
C
C
C
A
5.2.4. Characteristic polynomial
The command graph_charpoly or charpoly is used for obtaining the characteristic polynomial
of an undirected graph.
graph_charpoly or charpoly accepts one or two arguments, the input graph G(V ; E)and option-
ally a value or symbol x. The command returns p(x), where pis the characteristic polynomial of
the adjacency matrix of G.
>G:=graph(%{[1,2],[2,3]%})
an undirected unweighted graph with 3 vertices and 2 edges
>charpoly(G,x)
52 Graph properties
x3¡2x
>charpoly(G,3)
21
>G:=graph("shrikhande")
an undirected unweighted graph with 16 vertices and 48 edges
>charpoly(G,x)
x16 ¡48 x14 ¡64 x13 +768 x12 +1536 x11 ¡5888 x10 ¡15360 x9+23040 x8+81920 x7¡
36864 x6¡245760 x5¡32768 x4+393216 x3+196608 x2¡262144 x¡196608
5.2.5. Graph spectrum
The command graph_spectrum is used for obtaining the spectrum of eigenvalues of a graph.
graph_spectrum accepts the input graph Gas its only argument and returns the list in which
every element is an eigenvalue of the adjacency matrix of Gpaired with its multiplicity.
>C5:=cycle_graph(5)
C5: an undirected unweighted graph with 5 vertices and 5 edges
>gs:=graph_spectrum(C5)
0
B
B
B
B
@
2 1
5
p¡1
22
¡5
p¡1
22
1
C
C
C
C
A
>p:=charpoly(C5,x)
x5¡5x3+ 5 x¡2
>expand(roots(p))==expand(gs)
true
The last result indicates that gs and roots(p) are equal.
5.2.6. Seidel spectrum
The command seidel_spectrum is used for obtaining the Seidel spectrum of a graph.
seidel_spectrum accepts the input graph G(V ; E)as its only argument and returns the list in
which every element is an eigenvalue of the matrix J¡I¡2Apaired with its multiplicity. Here Jis
all-one n×nmatrix, Iis the identity matrix of order n,Ais the adjacency matrix of Gand n=jVj.
>G:=graph("clebsch")
an undirected unweighted graph with 16 vertices and 40 edges
>seidel_spectrum(G)
¡310
5 6
>P:=graph("petersen")
an undirected unweighted graph with 10 vertices and 15 edges
5.2 Algebraic properties 53
>seidel_spectrum(P)
¡3 5
3 5
5.2.7. Integer graphs
The command is_integer_graph is used for determining if a graph is an integer graph, i.e. if its
spectrum consists only of integers.
is_integer_graph accepts the input graph Gas its only argument. The return value is true if
Gis an integer graph and false otherwise.
>G:=graph("levi")
an undirected unweighted graph with 30 vertices and 45 edges
>is_integer_graph(G)
true
>factor(charpoly(G,x))
x10 (x¡3) (x¡2)9(x+ 2)9(x+ 3)
5.3. Connectivity
5.3.1. Vertex connectivity
The commands is_connected,is_biconnected and is_triconnected are used for determining
if a graph is connected, biconnected or triconnected, respectively.
All three commands accept only one argument, the input graph G(V ; E). They return true if G
possesses the required type of connectivity and false otherwise.
Gis connected or 1-connected if for every pair v; w 2Vthere exists a path with endpoints uand
vin Gor in the underlying graph of Gif the latter is directed.
Gis biconnected or 2-connected if it remains connected after removing a vertex from G.
Gis triconnected or 3-connected if it remains connected after removing a pair of distinct vertices
from G.
The strategy for checking 1- and 2-connectivity is to use depth-first search (see [7] and [18]). Both
algorithms run in O(jVj+jEj)time. The algorithm for checking 3-connectivity is quite simple but
less efficient: it works by choosing a vertex v2Vand checking if the subgraph induced by Vnfvg
is biconnected, moving on to the next vertex if so, and repeating the process until all vertices are
visited exactly once or a non-biconnected subgraph is found for some v. In the latter case the input
graph is not triconnected. The complexity of this algorithm is O(jVjjEj).
>G:=graph_complement(complete_graph(2,3,4))
an undirected unweighted graph with 9 vertices and 10 edges
>is_connected(G)
false
>C:=connected_components(G)
f[0;1];[2;3;4];[5;6;7;8]g
>H:=induced_subgraph(G,C[2])
54 Graph properties
an undirected unweighted graph with 4 vertices and 6 edges
>is_connected(H)
true
>is_biconnected(path_graph(5))
false
>is_biconnected(cycle_graph(5))
true
>is_triconnected(graph("petersen"))
true
>is_triconnected(cycle_graph(5))
false
5.3.2. Connected and biconnected components
The command connected_components resp. biconnected_components is used for decomposing
a graph into connected resp. biconnected components.
connected_components resp. biconnected_components accept the input graph G(V ; E)as its
only argument and returns the minimal partition fV1; V2; :::; Vkgof Vsuch that the subgraph Gi⊂G
induced by Viis connected resp. biconnected for each i= 1;2; :::; k. The partition is returned as a
list of lists V1; V2; :::; Vk.
The connected components of Gare easily obtained by depth-first search in O(jVj+jEj)time. To
find the biconnected components of G,Tarjan's algorithm is used [18], which also runs in linear
time.
>G:=graph_complement(complete_graph(3,5,7))
an undirected unweighted graph with 15 vertices and 34 edges
>is_connected(G)
false
>C:=connected_components(G)
f[0;1;2];[3;4;5;6;7];[8;9;10;11;12;13;14]g
>G:=highlight_subgraph(G,induced_subgraph(G,C[1]))
an undirected unweighted graph with 15 vertices and 34 edges
>G:=highlight_subgraph(G,induced_subgraph(G,C[2]),magenta,cyan)
an undirected unweighted graph with 15 vertices and 34 edges
>draw_graph(G)
0
12
3
4
56
7
8
9
10
1112
13
14
>H:=graph(trail(1,2,3,4,2),trail(4,5,6,7,5))
an undirected unweighted graph with 7 vertices and 8 edges
5.3 Connectivity 55
>draw_graph(H)
1
2
3
45
6
7
>is_biconnected(H)
false
>biconnected_components(H)
f[1;2];[2;3;4];[4;5];[5;6;7]g
5.3.3. Graph rank
The command graph_rank is used for computing the rank of a graph.
graph_rank accepts one or two arguments, the input graph G(V ; E)and optionally a set of edges
S⊂E(by default S=E), and returns jVj¡kwhere kis the number of connected components of
the spanning subgraph of Gwith edge set S.
>G:=graph(%{[1,2],[3,4],[4,5]%})
an undirected unweighted graph with 5 vertices and 3 edges
>graph_rank(G)
3
>graph_rank(G,[[1,2],[3,4]])
2
5.3.4. Articulation points
The command articulation_points is used for obtaining the articulation points of a graph,
i.e. cut vertices, if any.
articulation_points accepts the input graph G(V ; E)as its only argument and returns the list
of articulation points of G. A vertex v2Vis an articulation point of Gif the subgraph H⊂G
induced by Vnfvgis disconnected.
The articulation points of Gare found by depth-first serach in O(jVj+jEj)time [7].
>articulation_points(path_graph([1,2,3,4]))
[2;3]
>articulation_points(cycle_graph(1,2,3,4))
[]
5.3.5. Strongly connected components
The command strongly_connected_components is used for decomposing a graph into strongly
connected components. A (di)graph His strongly connected if for each pair (v; w)of distinct
vertices in Hthere is a (directed) path from vto win H.
56 Graph properties
strongly_connected_components accepts the input graph G(V ; E)as its only argument and
returns the minimal partition fV1; V2; :::; Vkgof Vsuch that the subgraph Gi⊂Ginduced by Viis
strongly connected for each i= 1;2; :::; k. The result is returned as a list of lists V1; V2; :::; Vk.
The strategy is to use Tarjan's algorithm for strongly connected components [18], which runs in
O(jVj+jEj)time.
Note that an undirected graph is strongly connected if and only if it is connected.
The command is_strongly_connected can be used to determine if the given graph Gis strongly
connected. It accepts Gas its only argument and returns true if Ghas exactly one strongly
connected component and false otherwise.
>G:=digraph([1,2,3],%{[1,2],[1,3],[2,3],[3,2]%})
a directed unweighted graph with 3 vertices and 4 arcs
>draw_graph(G)
1
23
>is_connected(G)
true
>is_strongly_connected(G)
false
>strongly_connected_components(G)
f[1];[2;3]g
5.3.6. Edge connectivity
5.4. Trees
5.4.1. Tree graphs
The command is_tree is used for determining if the particular graph is a tree. An undirected
graph G(V ; E)is a tree if jVj=jEj+ 1 and Gis connected.
is_tree accepts the input graph Gas its only argument and returns true if Gis a tree and false
otherwise.
The only expensive step in the algorithm is determining whether Gis connected. The condition
jVj=jEj+ 1 is checked first, hence the algorithm runs in O(jVj)time.
>is_tree(complete_binary_tree(3))
true
>is_tree(cycle_graph(5))
false
5.4 Trees 57
5.4.2. Forest graphs
The command is_forest is used for determining if the particular graph is a forest, i.e. if its
connected components are all trees.
is_forest accepts the input graph Gas its only argument and returns true if Gis a forest and
false otherwise.
The only expensive step in the algorithm is the decomposition of Gto connected components.
Therefore the algorithm runs in O(jVj+jEj)time.
>L:=[]:; for k from 10 to 30 do L.append(random_tree(k)); od:;
Done;Done
>G:=disjoint_union(op(L))
an undirected unweighted graph with 420 vertices and 399 edges
>is_connected(G)
false
>is_forest(G)
true
5.4.3. Height of a tree
The command tree_height is used for determining the height of a tree with respect to the specified
root node. The height of a tree is the length of the longest path in that tree that has the root node
as one of its endpoints.
tree_height accepts two arguments, the input tree graph G(V ; E)and a vertex r2V, which is
used as the root node. The command returns the height of Gwith respect to r.
The strategy is to start a depth-first search from the root node and look for the deepest node.
Therefore the algorithm runs in O(jVj)time.
>G:=random_tree(1000)
an undirected unweighted graph with 1000 vertices and 999 edges
>r:=rand(1000)
296
>tree_height(G,r)
20
5.4.4. Lowest common ancestor of a pair of nodes
The command lowest_common_ancestor determines the lowest common ancestor (LCA) of a pair
of nodes in a tree, or for every element of a list of such pairs.
lowest_common_ancestor accepts two mandatory arguments, the input tree graph G(V ; E)and
the root node r2V. There are two possibilities for specifying the nodes to operate on: either the
nodes u; v 2Vare given as the third and the fourth argument, or a list of pairs of nodes in form
[[u1,v1],[u2,v2],...,[uk,vk]], where ui; vi2Vand ui=/ vifor i= 1;2; :::; k, is given as the
third argument. The command returns the LCA of uand vor the list containing LCA of every
pair of nodes ui; vifor i= 1;2; :::; k.
The strategy is to use Tarjan's offline LCA algorithm [19]. The implementation is simple and
uses the disjoint-set (union-find) data structure. It runs in nearly linear time.
58 Graph properties
In the following example, the algorithm efficiency is tested on a large random tree with 10000 nodes.
The lowest common ancestors for the list Lcotaining 100 pairs of vertices, chosen at random, need
to be determined.
>G:=random_tree(10000)
an undirected unweighted graph with 10000 vertices and 9999 edges
3.562 sec
>V:=vertices(G):; L:=[]:; for k from 1 to 100 do L.append(rand(2,V)); od:;
Done;Done;Done
>lowest_common_ancestor(G,0,L):;
9.409 sec
5.5. Distance
5.5.1. Vertex distance
The command vertex_distance is used for computing the length of the shortest path between
two vertices of a graph.
vertex_distance accepts three arguments, the input graph G(V ; E), a vertex v2Vcalled the
source and a vertex w2Vcalled the target, or a list L⊂Vof target vertices. The command returns
the distance between vand was the number of edges in a shortest path from vto w, or the list
of distances if a list of target vertices is given.
>G:=graph("petersen") // Xcas mode
an undirected unweighted graph with 10 vertices and 15 edges
>vertex_distance(G,1,3)
2
>vertex_distance(G,1,[3,6,9])
[2;1;2]
5.5.2. All-pairs vertex distance
5.5.3. Diameter of a graph
5.5.4. Girth of a graph
The commands girth and odd_girth are used for computing the (odd) girth of an undirected
unweighted graph.
girth resp. odd_girth accepts the input graph G(V ; E)as its only argument and returns the girth
resp. odd girth of G. The (odd) girth of Gis defined to be the length of the shortest (odd) cycle
in G. If there is no (odd) cycle in G, the command returns +1.
The strategy is to apply breadth-first search from each vertex of the input graph. The runtime is
therefore O(jVjjEj).
>G:=graph("petersen")
an undirected unweighted graph with 10 vertices and 15 edges
>girth(G)
5.5 Distance 59
5
>G:=hypercube_graph(3)
an undirected unweighted graph with 8 vertices and 12 edges
>G:=subdivide_edges(G,["000","001"])
an undirected unweighted graph with 9 vertices and 13 edges
>girth(G)
4
>odd_girth(G)
5
>G:=complete_binary_tree(2)
an undirected unweighted graph with 7 vertices and 6 edges
>girth(G)
+1
5.6. Acyclic graphs
5.6.1. Checking if a graph is acyclic
The command is_acyclic is used for checking that the given digraph has no directed cycle. A
directed graph with no directed cycle is said to be acyclic.
is_acyclic accepts the input digraph G(V ; E)as its only argument and returns true if Gis
acyclic and false otherwise.
The algorithm attempts to find topological order for its vertices. If that succeeds, the graph is
acyclic, otherwise not. The algorithm runs in O(jVj+jEj)time.
>is_acyclic(digraph(trail(1,2,3,4,5)))
true
>is_acyclic(digraph(trail(1,2,3,4,5,2)))
false
5.6.2. Topological sorting
The command topologic_sort or topological_sort is used for finding a linear ordering of
vertices of an acyclic digraph which is consistent with the arcs of the digraph.
topologic_sort accepts the input graph G(V ; E)as its only argument and returns the list of
vertices of Gin a particular order: a vertex uprecedes a vertex vif u v 2E, i.e. if there is an arc
from uto v.
Note that topological sorting is possible only if the input graph is acyclic. If this condition is not
met, topologic_sort returns an error. Otherwise, it finds the required ordering by applying
Kahn's algorithm [13], which runs in O(jVj+jEj)time.
>G:=digraph(%{[c,a],[c,b],[c,d],[a,d],[b,d],[a,b]%})
a directed unweighted graph with 4 vertices and 6 arcs
>is_acyclic(G)
60 Graph properties
true
>topologic_sort(G)
[c; a; b; d]
5.6.3. st ordering
The command st_ordering is used for finding a st-orientation in an undirected biconnected graph
with respect to the given source and sink nodes.
st_ordering accepts three or four arguments: the input graph G(V ; E), a vertex s2Vcalled
the source, a vertex t2Vcalled the target or sink such that st 2Eand optionally an unassigned
identifier D. The command returns the permutation σwhich defines a particular order of vertices
in V. That ordering defines the orientation for each edge e2E, which causes Gto become acyclic
with a single source sand sink t. The ordering defined by σis the topological ordering of the
resulting digraph. If the optional argument Dis given, the digraph is stored to it.
The orientation of e=uv 2Eis determined by the ordinals nand mof its endpoints uand v,
respectively, which are assigned by the permutation σ. If n < m, then uis the head and vis the
tail of the corresponding arc, and vice versa otherwise.
Note that the input graph Ghas a st-orientation if and only if Gis biconnected. Furthermore, if
the latter is true, a st-orientation can be computed for any pair s; t 2Vsuch that st 2E.
If the input graph is not biconnected, st_ordering returns an error. Otherwise, it applies the
algorithm of Even and Tarjan [5], which runs in O(jVj+jEj)time, to find st-ordering for the
given pair of vertices.
>G:=graph(%{[a,b],[a,c],[a,d],[b,c],[b,d],[c,d]%})
an undirected unweighted graph with 4 vertices and 6 edges
>vertices(G)
[a; b; c; d]
>st_ordering(G,a,d,D)
[0;2;1;3]
>draw_graph(D)
a b
cd
5.7. Vertex matching
5.7.1. Maximum matching
The command maximum_matching is used for finding maximum matching in undirected graphs.
maximum_matching accepts the input graph G(V ; E)as its only argument and returns a list of
edges e1; e2; :::; em2Esuch that eiand ejare not adjacent (i.e. have no common endpoints) for all
16i < j 6m, under condition that mis maximal. Edges ekfor k= 1; :::; m represent the matched
pairs of vertices in G.
5.7 Vertex matching 61
The command applies Edmonds' blossom algorithm5.1 [4], which finds maximum matching in
O(jVj2jEj)time.
>G:=graph("octahedron")
an undirected unweighted graph with 6 vertices and 12 edges
>maximum_matching(G)
f[1;3];[6;4];[5;2]g
>G:=graph("soccerball")
an undirected unweighted graph with 60 vertices and 90 edges
>draw_graph(highlight_edges(G,maximum_matching(G)),labels=false)
5.7.2. Maximum matching in bipartite graphs
If the input graph is bipartite, maximum matching can be found much faster by using the
bipartite_matching command which applies the algorithm of Hopcroft and Karp [10].
bipartite_matching accepts an undirected, unweighted bipartite graph Gas its only argument
and returns a sequence containing two elements: the size of the maximum matching and the list
of edges connecting matched pairs of vertices. The algorithm runs in O¡jVj
pjEjtime.
>G:=graph("desargues")
an undirected unweighted graph with 20 vertices and 30 edges
>is_bipartite(G)
true
>n,M:=bipartite_matching(G)
10;f[0;1];[2;3];[4;5];[6;7];[8;9];[10;13];[11;18];[12;15];[14;17];[16;19]g
>draw_graph(highlight_edges(G,M))
5.1. For a good description of the blossom algorithm, see https://en.wikipedia.org/wiki/Blossom_algorithm.
62 Graph properties
5.8. Cliques
5.8.1. Clique graphs
The graph is a clique if it is complete, i.e. if each two of its vertices are adjacent to each other. To
check if a graph is a clique one can use the is_clique command.
is_clique accepts a graph G(V ; E)as its only argument and returns true if Gis a complete
graph; else the returned value is false.
>K5:=complete_graph(5)
an undirected unweighted graph with 5 vertices and 10 edges
>is_clique(K5)
true
>G:=delete_edge(K5,[1,2])
an undirected unweighted graph with 5 vertices and 9 edges
>is_clique(G)
false
5.8.2. Triangle-free graphs
The command is_triangle_free is used for determining is the particular graph triangle-free. A
graph is triangle-free if it contains no clique of cardinality equal to 3, and hence no cliques with
cardinality greater than two.
triangle_free accepts the input graph Gas its only argument and returns true if Gis triangle-
free and false otherwise.
The strategy is to check whether tr (A3) = 0, where Ais the adjacency matrix of G. If the last
equality holds, the graph is triangle-free. This method is very fast as just one matrix multiplication
needs to be carried out completely. Additionally, the matrix Ais sparse, so a large number of
vertices usually does not cause memory problems.
>is_triangle_free(graph("soccerball"))
true
>is_triangle_free(graph("tetrahedron"))
false
5.8.3. Maximal cliques
Each subgraph of a graph G(V ; E)which is itself a complete graph is called a clique in G. A clique
is maximal if it cannot be extended by adding more vertices from Vto it. To count all maximal
cliques in a graph one can use the clique_stats command.
clique_stats accepts Gas the only mandatory argument. If it is the only argument given, the
command returns a list of pairs, each pair consisting of two integers: clique cardinality k(first) and
the number nk>0of k-cliques in G(second). Therefore, the sum of second members of all returned
pairs is equal to the total count of all maximal cliques in G. As an optional second argument one
may give a positive integer kor an interval m.. nwith integer bounds. In the first case only the
number of k-cliques for the given kis returned; in the second case, only cliques with cardinality
between mand n(inclusive) are counted.
5.8 Cliques 63
The strategy used to find all maximal cliques is a variant of the algorithm of Bron and Kerbosch
as described in [20]. Its worst-case running time is O(3jVj/3). However, the performance is usually
almost instantaneous for graphs with 100 vertices or less.
>G:=random_graph(50,0.5)
an undirected unweighted graph with 50 vertices and 588 edges
>clique_stats(G)
0
B
B
B
B
B
B
@
314
4185
5370
6201
747
8 5
1
C
C
C
C
C
C
A
>G:=random_graph(100,0.5)
an undirected unweighted graph with 100 vertices and 2461 edges
>clique_stats(G,5)
3124
>G:=random_graph(500,0.25)
an undirected unweighted graph with 500 vertices and 31257 edges
>clique_stats(G,5..7)
0
@
5153444
618486
7355
1
A1.218 sec
5.8.4. Maximum clique
The largest maximal clique in the graph G(V ; E)is called maximum clique. The command max-
imum_clique can be used to find one in the given graph.
maximum_clique accepts the graph Gas its only argument and returns maximum clique in G
as a list of vertices. The clique may subsequently be extracted from Gusing the command
induced_subgraph.
The strategy used to find maximum clique is an improved variant of the classical algorithm by
Carraghan and Pardalos developed by Östergård in [15].
In the following examples, the maximum cliques were obtained almost instantly.
>G:=sierpinski_graph(5,5)
an undirected unweighted graph with 3125 vertices and 7810 edges
>maximum_clique(G)
[1560;1561;1562;1563;1564]
>G:=random_graph(300,0.3)
an undirected unweighted graph with 300 vertices and 13380 edges
>maximum_clique(G)
[46;64;144;183;208;241;244;261]
>G:=graph_complement(complete_graph(4,3))
64 Graph properties
an undirected unweighted graph with 7 vertices and 9 edges
>cliq:=maximum_clique(G)
[0;1;2;3]
>draw_graph(highlight_subgraph(G,induced_subgraph(G,cliq)))
5.8.5. Minimum clique cover
The minimum clique cover for the graph G(V ;E)is the smallest set S=fC1; C2; :::; Ckgof cliques in
Gsuch that for every v2Vthere exists i6ksuch that v2Ci. In Giac, such cover can be obtained
by calling the clique_cover command.
clique_cover accepts graph Gas its mandatory argument and returns the smallest possible cover.
Optionally, a positive integer may be passed as the second argument. In that case the requirement
that kis less or equal to the given integer is set. If no such cover is found, clique_cover returns
empty list.
The strategy is to find the minimal vertex coloring in the complement Gcof G(note that these
two graphs share the same set of vertices). Each set of equally colored vertices in Gccorresponds
to a clique in G. Therefore, the color classes of Gcmap to the elements C1; :::; Ckof the minimal
clique cover in G.
There is a special case in which Gis triangle-free, which is treated separately. Such a graph G
contains only 1- and 2-cliques; in fact, every clique cover in Gconsists of a matching Mtogether
with the singleton cliques (i.e. the isolated vertices which remain unmatched). The total number
of cliques in the cover is equal to jVj¡jMj, hence to find the minimal cover one just needs to find
maximum matching in G, which can be done in polynomial time.
>G:=random_graph(30,0.2)
an undirected unweighted graph with 30 vertices and 88 edges
>clique_cover(G)
f[0;2;7];[1;3];[4;10;13;14];[5;6];[8;15;26];[9;22;25];[11;16];[12;17;23];[18;20;24];[19;28];
[21;27;29]g
To find minimal clique cover in the truncated icosahedral graph it suffices to find maximum
matching, since it is triangle-free.
>clique_cover(graph("soccerball"))
f[1;2];[3;16];[4;5];[6;7];[8;49];[9;10];[11;12];[13];[14;15];[17;18];[19;20];[21;22];[23];[24;25];
[26;30];[27;28];[29;48];[31;32];[33;46];[34;35];[36;37];[38;39];[40];[41;42];[43;44];[45;47];
[50];[51;52];[53;54];[55;57];[56;60];[58;59]g
The vertices of Petersen graph can be covered with five, but not with three cliques.
>clique_cover(graph("petersen"),3)
[]
>clique_cover(graph("petersen"),5)
5.8 Cliques 65
f[0;1];[2;3];[4;9];[5;7];[6;8]g
5.9. Vertex coloring
To color vertices of a graph G(V ; E)means to assign to each vertex v2Va positive integer.
Each integer represents a distinct color. The key property of a graph coloring is that the colors
of adjacent vertices must differ from one another. Two different colorings of Gmay use different
number of colors.
5.9.1. Greedy coloring
The command greedy_color is used for coloring vertices of a graph in a greedy fashion.
greedy_color accepts one mandatory argument, the input graph G. Optionally, a permutation p
of order jVjmay be passed as the second argument. Vertices are colored one by one in the order
specified by p(or in the default order if pis not given) such that each vertex gets the smallest
available color. The list of vertex colors is returned in the order of vertices(G).
Generally, different choices of permutation pproduce different colorings. The total number of
different colors may not be the same each time. The complexity of the algorithm is O(jVj+jEj).
>G:=graph("petersen")
an undirected unweighted graph with 10 vertices and 15 edges
>greedy_color(G)
[1;2;1;2;3;2;1;3;3;2]
>L:=greedy_color(G,randperm(10))
[1;2;1;4;3;4;1;3;2;2]
Observe that a different number of colors is obtained by executing the last command line. To
display the colored graph, input:
>draw_graph(highlight_vertex(G,vertices(G),L),labels=false)
The first six positive integers are always mapped to the standard Xcas colors, as indicated in
Table 5.1. Note that the color 0 (black) and color 7 (white) are swapped; a vertex with color 0 is
uncolored or white, and vertex with color 7 is black. Also note that Xcas will map the numbers
greater than 7 to colors too, but the number of available colors is limited.
5.9.2. Minimal coloring
The vertex coloring of Gis minimal (or optimal) if the smallest possible number of colors is used.
To obtain such a coloring use the command minimal_vertex_coloring.
minimal_vertex_coloring accepts one mandatory argument, the graph G. Optionally, a symbol
sto may be passed as the second argument. The command returns the vertex colors in order of
vertices(G) or, if the second argument is given, stores the colors as vertex attributes and returns
the modified copy of G.
66 Graph properties
value color
1 red
2 green
3 yellow
4 blue
5 magenta
6 cyan
7 black
Table 5.1. interpretation of abstract vertex/edge colors in Xcas
Giac requires the GLPK library5.2 to solve the minimal vertex coloring problem (MVCP), which is
converted to the equivalent integer linear programming problem and solved by using the branch-
and-bound method with specific branch/backtrack techniques [3]. Lower and upper bounds for the
number of colors nare obtained by finding a maximal clique (ncannot be lower than its cardinality)
and by using the heuristic proposed by Brélaz in [1] (which will use at least ncolors), respectively.
The algorithm is usually fast for graphs up to 40 vertices and for sparse graphs in general. For
larger, denser graphs (e.g. with edge density around 0.5, which are the most difficult ones) one may
have to wait for several minutes, even hours, and sometimes for a practically infinite time. Note that
MVCP is a NP-hard problem, which means that no polynomial (i.e. efficient) algorithm is known.
In the following example, the Grotzsch graph is colored with minimal number of colors by first
finding the coloring and then assigning it to the graph by using the highlight_vertex command.
>G:=graph("grotzsch")
an undirected unweighted graph with 11 vertices and 20 edges
>coloring:=minimal_vertex_coloring(G)
[4;2;3;1;1;4;1;3;2;1;2]
>draw_graph(highlight_vertex(G,vertices(G),coloring),labels=false)
To illustrate the combinatorial explosion which characterizes MVCP one can use the following
example. Note that finding an optimal coloring in Gis equivalent to finding the minimal clique
cover in its complement Gc.
First, a random graph Gwith 40 vertices and edge density 0.5 is generated. Such a graph is
considered to be relatively small.
>G:=random_graph(40,0.5)
an undirected unweighted graph with 40 vertices and 393 edges
The chromatic number is computed by solving MVCP via minimal_vertex_coloring in less than
a second.
>chromatic_number(G)
8
273 msec
5.2. GNU Linear Programming Kit, https://www.gnu.org/software/glpk/
5.9 Vertex coloring 67
Next, all maximal cliques in Gcare counted using the clique_stats command.
>S:=clique_stats(graph_complement(G))
0
B
B
B
B
@
3 5
466
5238
689
7 3
1
C
C
C
C
A
>n:=sum(col(S,1))
401
To obtain the minimal coloring, a naive algorithm must check if a combination of 2;3; :::; 8maximal
cliques forms a cover in Gc. In the worst case it will check Pk=2
8n
kcombinations, the number
which is computed by the next command line.
>sum(comb(n,k),k=2..8)
15776262844602110
The magnitude of the above result (≈1.6 ×1017) indicates that the algorithm would run practically
forever. (In particular, assuming that the algorithm requires 1µs to test one combination of
cliques, the runtime is about 5070 years.) The fact that chromatic_number required only quarter
of a second to obtain minimal coloring indicates that the implemented algorithm is far more
sophisticated than a simple brute-force approach.
Note that solving MVCP for different graphs of exactly the same size (but which do not share the
same edge structure) may take quite different time in each instance. For example, the time required
to color a graph with 50 vertices and edge density 0.5 may take any value between six seconds and
six minutes. Also note that some graphs will take exponential time (that is, “forever”) to obtain
the coloring. Table 5.2 shows the runtimes (in seconds) of solving MVCP for random graphs with
10 kvertices and edge density d
10 for k= 1;2; :::; 7and d= 1;2; :::; 5, using Intel i3-7130U processor
at 2.70 GHz. For each pair (k; d), ten graphs were generated and the average runtime was recorded
in the table.
5.9.3. Chromatic number
The command chromatic_number is used for exact computation and approximation of the chro-
matic number of a graph.
chromatic_number accepts one mandatory argument, the input graph G(V ; E), and optionally a
second argument. To obtain only upper and lower bound for the chromatic number (which is much
faster than computing exactly) the option approx or interval should be passed as the second
argument. Alternatively, an unassigned identifier is passed as the second argument; in that case
the corresponding coloring will be stored to it in form of a list of colors of the individual vertices,
ordered as in vertices(G).
The command returns the chromatic number χGof the graph Gin the case of exact computation.
If the option approx or interval is given, an interval lb..ub is returned, where lb is the best
lower bound and ub the best upper bound for χGfound by the algorithm.
The strategy is call minimal_vertex_coloring in the case of exact computation. When approx-
imating the chromatic number, the algorithm will establish the lower bound by searching for
maximum clique. The timeout for this operation is set to 5 seconds as it can be time consuming. If
the maximum clique is not found after that time, the largest clique found is used. Then, an upper
bound is established by by using the heuristic proposed by Brélaz in [1]. Obtaining the bounds
for χGis usually very fast, but the difference between the bounds grows with jVj.
Unless the input graph is sparse enough, the algorithm slows down considerably for jVj>40.
68 Graph properties
number of vertices edge density
0.1 0.2 0.3 0.4 0.5
10 0.0008892 0.0010818 0.0006116 0.0005825 0.0006331
20 0.0014682 0.00378 0.0038329 0.0077918 0.0067932
30 0.0021163 0.0173315 0.0372468 0.111016 0.143657
40 0.0252134 0.177707 0.626175 1.67746 2.31473
50 0.130089 1.83819 17.3564 120.181 246.161
Table 5.2. average runtime of the algorithm for minimal coloring (in seconds)
>chromatic_number(graph("grotzsch"),cols)
4
>cols
[4;2;3;1;1;4;1;3;2;1;2]
>G:=random_graph(30,0.75)
an undirected unweighted graph with 30 vertices and 313 edges
>chromatic_number(G)
10
>G:=random_graph(300,0.05)
an undirected unweighted graph with 300 vertices and 2196 edges
>chromatic_number(G,approx)
4..7
5.9.4. k-coloring
The command is_vertex_colorable is used for determining whether the vertices of a graph can
be colored with at most kcolors.
is_vertex_colorable accepts two or three arguments: the input graph G(V ; E), a positive integer
kand optionally an unassigned identifier. The command returns true if Gcan be colored using
at most kcolors and false otherwise. If an identifier is given, a coloring using at most kcolors is
stored to it as a list of vertex colors, in the order of vertices(G).
The strategy is to first apply a simple greedy coloring procedure which runs in linear time. If
the number of required colors is greater than k, the heuristic proposed by Brélaz in [1] is used,
which runs in quadratic time. If the number of required colors is still larger than k, the algorithm
attempts to find the chromatic number χGusing kas the upper bound in the process.
>G:=graph("grotzsch")
an undirected unweighted graph with 11 vertices and 20 edges
>is_vertex_colorable(G,3)
false
>is_vertex_colorable(G,4)
true
>G:=random_graph(70,0.2)
an undirected unweighted graph with 70 vertices and 469 edges
>chromatic_number(G,approx)
5.9 Vertex coloring 69
5..6
>is_vertex_colorable(G,5)
false
818 msec
From the results of the last two command lines it follows that χG= 6. Finding χGby utilizing the
next command line is simpler, but requires much more time.
>chromatic_number(G)
6
92.7 sec
5.10. Edge coloring
70 Graph properties
Chapter 6
Traversing graphs
6.1. Walks and tours
6.1.1. Eulerian graphs
The command is_eulerian is used for determining whether the given graph is an Eulerian graph
and for finding Eulerian trails in such graphs.
is_eulerian accepts one or two arguments, the input graph G(V ; E)and optionally an unassigned
identifier T, and returns true if Gis Eulerian and false otherwise. If Tis given, the corresponding
Eulerian trail is stored to it.
The graph Gis Eulerian if it has a trail covering all its edges. Such a trail is called Eulerian trail.
An Eulerian trail may be closed, in which case it is called Eulerian cycle. Note that every edge
e2Emust be visited, i.e. “strolled through”, exactly once. However, the edge endpoints (i.e. the
vertices in G) may be visited more than once.
The strategy is to apply Hierholzer's algorithm for finding an Eulerian path [8]. It works by
covering one cycle at a time in the input graph. The required time is O(jEj).
>is_eulerian(complete_graph(4))
false
>purge(T):; is_eulerian(complete_graph([1,2,3,4,5]),T); T
Done;true;[1;2;3;4;1;5;2;4;5;3;1]
6.1.2. Hamiltonian graphs
6.2. Optimal routing
6.2.1. Shortest paths in unweighted graphs
The command shortest_path is used to find the shortest path between two vertices in an undi-
rected unweighted graph.
shortest_path accepts three arguments: a graph G(V ; E), the source vertex s2Vand the target
vertex t2Vor a list Tof target vertices. The shortest path from source to target is returned. If more
targets are specified, the list of shortest paths from the source to each of these vertices is returned.
The strategy is to run breadth-first traversal on the graph Gstarting from the source vertex s.
The complexity of the algorithm is therefore O(jVj+jEj).
>G:=graph("dodecahedron")
an undirected unweighted graph with 20 vertices and 30 edges
>shortest_path(G,1,16)
[1;6;11;16]
71
>paths:=shortest_path(G,1,[16,19])
f[1;6;11;16];[1;5;10;14;19]g
>H:=highlight_trail(G,paths,[red,green])
an undirected unweighted graph with 20 vertices and 30 edges
>draw_graph(H)
1
25
6
3
7
4
89
10
1115
12
13
14
16
17
18
19
20
6.2.2. Cheapest paths in weighted graphs
The command dijkstra is used to find the cheapest path between two vertices of an undirected
weighted graph.
dijkstra accepts two or three arguments: a weighted graph G(V ; E)with nonnegative weights, a
vertex s2Vand optionally a vertex t2Vor list Tof vertices in V. It returns the cheapest path
from sto tor, if more target vertices are given, the list of such paths to each target vertex t2T,
computed by Dijkstra's algorithm in O(jVj2)time. If no target vertex is specified, all vertices in
Vnfsgare assumed to be targets.
A cheapest path from sto tis represented with a list [[v1,v2,...,vk],c] where the first element
consists of path vertices with v1=sand vk=t, while the second element cis the weight (cost) of
that path, equal to the sum of weights of its edges.
>
6.2.3. Traveling salesman problem
6.3. Spanning trees
6.3.1. Constructing a spanning tree
The command spanning_tree accepts one or two arguments, an undirected graph Gand optionally
a vertex r2V. It returns the spanning tree Tof Grooted in ror, if none is given, in the first
vertex in the list V, obtained by depth-first traversal in O(jVj+jEj)time.
6.3.2. Minimal spanning tree
The command minimal_spanning_tree accepts an undirected graph G(V ; E)as its only argument
and returns its minimal spanning tree obtained by Kruskal's algorithm in O(jEjlog jVj)time.
6.3.3. Counting all spanning trees
The command number_of_spanning_trees is used for counting all spanning trees in a graph.
number_of_spanning_trees accepts the input graph G(V ; E)as its only argument and returns
the total number nof mutually different spanning trees in G.
72 Traversing graphs
The strategy is based on Theorem 2.2.12 (Matrix Tree Theorem) in [24], page 86. First the adja-
cency matrix Aand the degree sequence δof Gare obtained. Then the matrix B= ∆ ¡Ais
computed, where ∆is the diagonal matrix of order jVjcorresponding to δ. The last row and the
last column of Bare popped out, yielding the matrix Cof order jVj¡1. Now n=det C.
>number_of_spanning_trees(graph("octahedron"))
384
>number_of_spanning_trees(graph("dodecahedron"))
5184000
>number_of_spanning_trees(hypercube_graph(4))
42467328
>number_of_spanning_trees(graph("soccerball"))
375291866372898816000
6.3 Spanning trees 73
Chapter 7
Visualizing graphs
7.1. Drawing graphs by using various methods
To visualize a graph use the draw_graph command. It is capable to produce a drawing of the given
graph using one of the several built-in methods.
7.1.1. Overview
draw_graph accepts one or two arguments, the mandatory first one being the graph G(V ; E). This
command assigns 2D or 3D coordinates to each vertex v2Vand produces a visual representation
of Gbased on these coordinates. The second (optional) argument is a sequence of options. Each
option is one of the following:
•labels=true or false: controls the visibility of vertex labels and edge weights (by default
true, i.e. the labels and weights are displayed)
•spring: draw the graph Gusing a multilevel force-directed algorithm
•tree[=r or [r1,r2,...]]: draw the tree or forest G, optionally specifying root nodes for
each tree
•bipartite: draw the bipartite graph Gkeeping the vertex partitions separated
•circle[=L] or convexhull[=L]: draw the graph Gby setting the hull vertices from list
L⊂V(assuming L=Vby default) on the unit circle and all other vertices in origin,
subsequently applying a force-directed vertex placement algorithm to generate the layout
while keeping the hull vertices fixed
•planar or plane: draw the planar graph Gusing a force-directed algorithm
•plot3d: draw the connected graph Gas if the spring option was enabled, but with vertex
positions in 3D instead of 2D
•any unassigned identifier P: when given, the vertex coordinates will be stored to it in form
of a list
The style options spring,tree,circle,planar and plot3d cannot be mixed, i.e. at most one can
be specified. The option labels may be combined with any of the style options. Note that edge
weights will not be displayed when using plot3d option when drawing a weighted graph.
When no style option is specified, the algorithm first checks if the graph Gis a tree or if it is
bipartite, in which cases it is drawn accordingly. Otherwise, the graph is drawn as if the option
circle was specified.
Tree, circle and bipartite drawings can be obtained in linear time with a very small overhead,
allowing graphs to be drawn quickly no matter the size. The force-directed algorithms are more
expensive and operating in the time which is quadratic in the number of vertices. Their performance
is, nevertheless, practically instantaneous for graphs with several hundreds of vertices (or less).
7.1.2. Drawing disconnected graphs
When the input graph has two or more connected components, each component is drawn separately
and the drawings are subsequently arranged such that the bounding box of the whole drawing has
the smallest perimeter under condition that as little space as possible is wasted inside the box.
75
For example, the command lines below draw a sparse random planar graph.
>G:=random_planar_graph(100,0.9,0)
an undirected unweighted graph with 100 vertices and 74 edges
>draw_graph(G,planar)
7.1.3. Spring method
When the option spring is specified, the input graph is drawn using the force-directed algorithm
described in [11] (for an example of such a drawing see Figure 4.1). The idea, originally due
to Fruchterman and Reingold [6], is to simulate physical forces in a spring-electrical model
where the vertices and edges represent equally charged particles and springs connecting them,
respectively.
In a spring-electrical model, each vertex is being repulsed by every other vertex with a force
inversely proportional to the distance between them. At the same time, it is attracted to each of its
neighbors with a force proportional to the square of the distance. Assuming that xvis the vector
representing the position of the vertex v2V, the total force Fvapplied to vis equal to
Fv=X
w2Vnfvg¡C K2
kxv¡xwk2(xv¡xw) + X
w2N(v)
kxv¡xwk
K(xv¡xw);
where N(v)is the set of neighbors of vand C,Kare certain positive real constants (actually, K
may be any positive number, it affects only the scaling of the entire layout). Applying the forces
iteratively and updating vertex positions in each iteration (starting from a random layout) leads the
system to the state of minimal energy. By applying a certain “cooling” scheme to the model which
cuts down the force magnitude in each iteration. the layout “freezes” after a number of iterations
large enough to achieve the minimal energy state.
The force-directed method is computationally expensive and for larger graphs the pleasing layout
cannot be obtained most of the time since the algorithm, starting with a random initial layout,
gets easily “stuck” in the local energy minimum (ideally, the vertex positions should settle in the
global minimal energy constellation). To avoid this a multilevel scheme is applied. The input graph
is iteratively coarsened, either by removing the vertices from a maximal independent vertex set
or contracting the edges of a maximal matching in each iteration. Each coarsening level is then
processed by the force-directed algorithm, starting from the deepest (coarsest) one and lifting the
obtained layout to the first upper level, using it as the initial layout for that level. The lifting is
achieved by using the prolongation matrix technique described in [12]. To support drawing of large
graphs (with 1000 vertices or more), the matrices used in the lifting process are stored as sparse
matrices. The multilevel algorithm is significantly faster than the original, single-level one and
usually produces better results.
Graph layouts obtained by using force-directed method have a unique property of reflecting sym-
metries in the design of the input graph, if any. Thus the drawings become more appealing and
illustrate the certain properties of the input graph better. To make the symmetry more prominent,
the drawing is rotated such that the axis, with respect to which the layout exhibits the largest
symmetry score, becomes vertical. As the symmetry detection is in general very computationally
expensive—up to O(jVj7)when using the symmetry measure of Purchase [23], for example—the
algorithm deals only with the convex hull and the barycenter of the layout, which may not always
be enough to produce the optimal result. Nevertheless, this approach is very fast and seems to
work most of the time for graphs with a high level of symmetry (for example the octahedral graph).
76 Visualizing graphs
For example, the following command lines produce a drawing of the tensor product of two graphs
using the force-directed algorithm.
>G1:=graph(trail(1,2,3,4,5,2))
an undirected unweighted graph with 5 vertices and 5 edges
>G2:=star_graph(3)
an undirected unweighted graph with 4 vertices and 3 edges
>G:=tensor_product(G1,G2)
an undirected unweighted graph with 20 vertices and 30 edges
>draw_graph(G,spring,labels=false)
The following command lines demonstrate drawing of a much larger graph.
>S:=sierpinski_graph(5,4)
an undirected unweighted graph with 1024 vertices and 2046 edges
>draw_graph(S,spring)
Note that vertex labels are automatically suppressed because of the large number of vertices. On
our system, the algorithm took less than 2 seconds to produce the layout.
The spring method is also used for creating 3D graph layouts, which are obtained by passing the
option plot3d to the draw_graph command.
>draw_graph(graph("soccerball"),plot3d,labels=false)
>G1:=graph("icosahedron"):; G2:=graph("dodecahedron"):;
Done;Done
7.1 Drawing graphs by using various methods 77
>G1:=highlight_edges(G1,edges(G1),red)
an undirected unweighted graph with 12 vertices and 30 edges
>G2:=highlight_edges(G2,edges(G2),magenta)
an undirected unweighted graph with 20 vertices and 30 edges
>G:=disjoint_union(G1,G2)
an undirected unweighted graph with 32 vertices and 60 edges
>draw_graph(G,plot3d,labels=false)
y
x
z
7.1.4. Drawing trees
When the tree[=r] option is specified and the input graph Gis a tree (and r2V), it is drawn using
a fast but simple node positioning algorithm inspired by the well-known algorithm of Walker [22],
using the first vertex (or the vertex r) as the root node. When drawing a rooted tree, one usually
requires the following aesthetic properties [2].
A1. The layout displays the hierarchical structure of the tree, i.e. the y-coordinate of a node is
given by its level.
A2. The edges do not cross each other.
A3. The drawing of a sub-tree does not depend on its position in the tree, i.e. isomorphic sub-
trees are drawn identically up to translation.
A4. The order of the children of a node is displayed in the drawing.
A5. The algorithm works symmetrically, i.e. the drawing of the reflection of a tree is the reflected
drawing of the original tree.
The algorithm implemented in Giac generally satisfies all the above properties but A3. Instead,
it tries to spread the inner sub-trees evenly across the available horizontal space. It works by
organizing the structure of the input tree into levels by using depth-first search and laying out
each level subsequently, starting from the deepest one and climbing up to the root node. In the
end, another depth-first traversal is made, shifting the sub-trees horizontally to avoid intersections
between their edges. The algorithm runs in O(jVj)time and uses the minimum of horizontal space
to draw the tree with respect to the specified root node r.
For example, the following command line produces the drawing of a random tree on 100 nodes.
>draw_graph(random_tree(100))
78 Visualizing graphs
7.1.5. Drawing planar graphs
The algorithm implemented in Giac which draws planar graphs uses augmentation techniques
to extend the input graph Gto a graph G0, which is homeomorphic to some triconnected graph,
by adding temporary edges. The augmented graph G0is then drawn using Tutte's barycentric
method [21], a force-directed algorithm which puts each vertex in the barycenter of its neighbors.
It is guaranteed that a (non-strict) convex drawing will be produced, without edge crossings. In
the end, the duplicate of the outer face and the temporary edges inserted during the augmentation
stage are removed.
Tutte's algorithm requires that the vertices of the chosen outer face are initially fixed somewhere
the boundary of a convex polygon. In addition, to produce a more flexible layout, the outer face is
duplicated such that the subgraph induced by the vertices on both the outer face and its duplicate
is a prism graph. Then only the duplicates of the outer face vertices are fixed, allowing the outer
face itself to take a more natural shape. The duplicate of the outer face is removed after a layout
is produced.
The augmentation process consists of two parts. Firstly, the input graph Gis decomposed into
biconnected components called blocks using the depth-first search (see [7], page 25). Each block is
then decomposed into faces (represented by cycles of vertices) using Demoucron's algorithm (see
[7], page 88, with a correction proposed in [14]). Embeddings obtained for each blocks are then
combined by adding one temporary edge for each articulation point, joining the two corresponding
blocks. Figure 7.1 shows the outer faces of two blocks B1and B2, connected by an articulation
point (cut vertex). The temporary edge (shown in blue) is added to join B1and B2into a single
block. After “folding up” the tree of blocks, the algorithm picks the largest face in the resulting
biconnected graph to be the outer face of the planar embedding.
The second part of the augmentation process consists of recursively decomposing each non-convex
inner face into several convex polygons by adding temporary edges. An inner face f= (v1; :::; vn)
is non-convex if there exist kand lsuch that 16k < l ¡1< n and either vkvl2E, in which case
the edge vkvlis a chord (see Figure 7.2 for an example) or there exists a face g= (w1; w2; :::; vk; :::;
vl; :::; wm¡1; wm)such that the vertices vk+1; :::; vl¡1are not contained in g(see Figure 7.3 for an
example). In Figures 7.1,7.2 and 7.3, the temporary edges added by the algorithm are drawn in
green.
B1
B2
temp. edge
Fig. 7.1. joining two blocks
f
chord
Fig. 7.2. a chorded face
f
g
vl
vk
Fig. 7.3. two adjacent faces
This method of drawing planar graphs operates in O(jVj2)time. Nevertheless, it is quite fast
for graphs up to 1000 vertices, usually producing results in less than a second. The drawback of
this method is that it sometimes creates clusters of vertices which are very close to each other,
resulting in a very high ratio of the area of the largest inner face to the area of the smallest inner
face. However, if the result is not satisfactory, one should simply redraw the graph and repeat the
process until a better layout is found. The planar embedding will in general be different each time.
Another drawback of this method is that sparse planar graphs are sometimes drawn poorly.
The following example shows that the above described improvement of the barycentric method
handles non-triconnected graphs well.
7.1 Drawing graphs by using various methods 79
>G:=graph(trail(1,2,3,4,5,6,7,8,9,10,1),trail(11,12,6,11,1,12))
an undirected unweighted graph with 12 vertices and 15 edges
>draw_graph(G,planar)
Note that the inner diamond-like shape in the above drawing would end up flattened—making the
two triangular faces invisible—if the input graph was not augmented. It is so because the vertices
with labels 11 and 12 are “attracted” to each other (namely, the two large faces are “inflating”
themselves to become convex), causing them to merge eventually.
In the following example the input graph Gis connected but not biconnected (it has two articu-
lation points). It is obtained by removing a vertex from the Sierpi«ski triangle graph ST3
3. Note
that the syntax mode is set to Xcas in this example, so the first vertex label is zero.
>G:=sierpinski_graph(3,3,triangle)
an undirected unweighted graph with 15 vertices and 27 edges
>G:=delete_vertex(G,3)
an undirected unweighted graph with 14 vertices and 23 edges
>draw_graph(G,planar,labels=false)
In the above example, several redraws were required to obtain a good planar embedding.
7.1.6. Circular graph drawings
The drawing method selected by specifying the option circle=L or convexhull=L when calling
draw_graph on a triconnected graph G(V ; E), where L⊂Vis a set of vertices in G, uses the
following strategy. First, positions of the vertices from Lare fixed so that they form a regular
polygon on the unit circle. Other vertices, i.e. all vertices from VnL, are placed in origin. Then
an iterative force-directed algorithm [16], similar to Tutte's barycentric method, is applied to
obtain the final layout.
This approach gives best results for symmetrical graphs such as generalized Petersen graphs. In
addition, if the input graph is planar, the drawing will also be planar (there is a possibility, however,
that some very short edges may cross each other as the number of force update iterations is limited).
In the following example the Sierpi«ski graph S4
2is drawn using the above method. Note that the
command lines below are executed in Xcas mode.
>G:=sierpinski_graph(2,4)
an undirected unweighted graph with 16 vertices and 30 edges
>draw_graph(G,circle=[0,1,4,5,7,13,15,14,11,10,8,2])
80 Visualizing graphs
7.2. Custom vertex positions
7.2.1. Setting vertex positions
The command set_vertex_positions is used to assign custom coordinates to vertices of a graph
to be used when drawing the graph.
set_vertex_positions accepts two arguments, the graph G(V ; E)and the list Lof positions to be
assigned to vertices in order of vertices(G). The positions may be complex numbers, lists of coor-
dinates or points (geometrical objects created with the command point). set_vertex_positions
returns the copy G0of Gwith the given layout stored in it.
Any subsequent call to draw_graph with G0as an argument and without specifying the drawing
style will result in displaying vertices at the stored coordinates. However, if a drawing style is
specified, the stored layout is ignored (although it stays stored in G0).
>G:=digraph([1,2,3,4,5],%{[1,2],[2,3],[3,4],[2,5]%})
a directed unweighted graph with 5 vertices and 4 arcs
>draw_graph(G,circle)
>H:=set_vertex_positions(G,[[0,0],[0.5,0],[1.0,0],[1.5,0],[0.5,1]])
a directed unweighted graph with 5 vertices and 4 arcs
>draw_graph(H)
7.2.2. Generating vertex positions
Vertex positions can be generated for a particular graph Gby using the draw_graph command with
the additional argument Pwhich should be an unassigned identifier. After the layout is obtained,
it will be stored to Pas a list of positions (complex numbers for 2D drawings or points for 3D
drawings) for each vertex in order of vertices(G).
7.2 Custom vertex positions 81
This feature combines well with the set_vertex_positions command, as when one obtains the
desired drawing of the graph Gby calling draw_graph, the layout coordinates can be easily stored
to the graph for future reference. In particular, each subsequent call of draw_graph with Gas an
argument will display the stored layout. The example below illustrates this property by setting a
custom layout to the octahedral graph.
>G:=graph("octahedron")
an undirected unweighted graph with 6 vertices and 12 edges
>draw_graph(G)
>draw_graph(G,P,spring):;
Now Pcontains vertex coordinates, which can be permanently stored to G:
>G:=set_vertex_positions(G,P)
an undirected unweighted graph with 6 vertices and 12 edges
>draw_graph(G)
It should be noted that, after a particular layout is fixed, it stays valid when some edges or vertices
are removed or when an edge is contracted. The stored layout becomes invalid only if a new vertex
is added to the graph (unless its position is specified by set_vertex_attribute upon the creation)
or if the position attribute of an existing vertex is discarded.
7.3. Highlighting parts of a graph
7.3.1. Highlighting vertices
The command highlight_vertex is used for changing color of one or more vertices in a graph.
highlight_vertex accepts two or three arguments: the graph G(V ; E), a vertex v2Vor a list
L⊂Vof vertices and optionally the new color (or a list of colors) for the selected vertices (the
default color is green). It returns a modified copy of Gin which the specified vertices are colored
with the specified color.
>G:=graph("dodecahedron")
an undirected unweighted graph with 20 vertices and 30 edges
>L:=maximum_independent_set(G)
82 Visualizing graphs
[2;4;6;12;13;10;16;19]
>draw_graph(highlight_vertex(G,L))
7.3.2. Highlighting edges and trails
To highlight an edge or a set of edges in a graph, use the highlight_edges command. If the edges
form a trail, it is usually more convenient to use the highlight_trail command (see below).
highlight_edges accepts two or three arguments: the graph G(V ; E), an edge eor a list of edges
Land optionally the new color (or a list of colors) for the selected edges (the default color is red).
It returns a modified copy of Gin which the specified edges are colored with the specified color.
>M:=maximum_matching(G)
f[1;2];[5;4];[6;11];[3;8];[7;12];[9;13];[10;15];[14;19];[16;17]g
>draw_graph(highlight_edges(G,M))
>S:=spanning_tree(G)
an undirected unweighted graph with 20 vertices and 19 edges
>draw_graph(highlight_edges(G,edges(S),magenta))
highlight_trail accepts two or three arguments: the input graph G(V ; E), a list L⊂Vor a
list [L1,L2,...,Lk] of such lists (each list represents the vertices of the corresponding trail) and
optionally a positive integer cor a list of positive integers [c1,c2,...,ck]. The command returns
the copy of Gin which edges between consecutive vertices in Lare highlighted with color c(by
default red) or the trail represented by Liis highlighted with color cifor i= 1;2; :::; k.
Note that a trail can cross itself, which means that the elements of Lare not required to be unique.
>draw_graph(highlight_trail(G,[6,15,20,19,18,17,16,11,7,2,3,8,13,9,14,10]))
7.3 Highlighting parts of a graph 83
1
25
6
3
7
4
89
10
1115
12
13
14
16
17
18
19
20
7.3.3. Highlighting subgraphs
The command highlight_subgraph is used for highlighting subgraph(s) of the given graph.
highlight_subgraph accepts two or four arguments: the graph G(V ; E), a subgraph Sof G
or a list of subgraphs of Gand optionally the new colors for edges and vertices of the selected
subgraph(s), respectively. It returns a modified copy of Gwith the selected subgraph(s) colored
as specified.
>G:=graph(%{[1,2],[2,3],[3,1],[3,4],[4,5],[5,6],[6,4]%})
an undirected unweighted graph with 6 vertices and 7 edges
>A:=articulation_points(G)
[3;4]
>B:=biconnected_components(G)
[[4;6;5];[3;4];[1;3;2]]
>H:=highlight_vertex(G,A,magenta)
an undirected unweighted graph with 6 vertices and 7 edges
>draw_graph(H)
>S:=induced_subgraph(G,B[0])
an undirected unweighted graph with 3 vertices and 3 edges
>H:=highlight_subgraph(G,S)
an undirected unweighted graph with 6 vertices and 7 edges
>draw_graph(H,spring)
84 Visualizing graphs
Bibliography
[1] Daniel Brélaz. New Methods to Color the Vertices of a Graph. Communications of the ACM, 22:251–256, 1979.
[2] Cristoph Buchheim, Michael Jünger, and Sebastian Leipert. Improving Walker's Algorithm to Run in Linear
Time. In M. T. Goodrich and S. G. Kobourov, editors, Graph Drawing 2002, Lecture Notes in Computer
Science vol 2528, pages 344–353. Springer-Verlag Berlin Heidelberg, 2002.
[3] Isabel M. Díaz and Paula Zabala. A Branch-and-Cut Algorithm for Graph Coloring. Discrete Applied Math-
ematics, 154:826–847, 2006.
[4] Jack Edmonds. Paths, Trees, and Flowers. In Gessel I. and GC. Rota, editors, Classic Papers in Combinatorics,
pages 361–379. Birkhäuser Boston, 2009. Modern Birkhäuser Classics.
[5] Shimon Even and Robert E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2:339–344,
1976.
[6] T. M. J. Fruchterman and E. M. Reingold. Graph Drawing by Force-Directed Placement. Software: Practice
and Experience, 21:1129–1164, 1991.
[7] Alan Gibbons. Algorithmic graph theory. Cambridge University Press, 1985.
[8] Carl Hierholzer. Ueber die möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu
umfahren. Mathematische Annalen, 6:30–32, 1873.
[9] Andreas M. Hinz, Sandi Klavºar, and Sara S. Zemlji£. A survey and classification of Sierpi«ski-type graphs.
Discrete Applied Mathematics, 217:565–600, 2017.
[10] John E. Hopcroft and Richard M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs.
SIAM Journal on Computing, 2:225–231, 1973.
[11] Yifan Hu. Efficient and High Quality Force-Directed Graph Drawing. Mathematica Journal, 10:37–71, 2005.
[12] Yifan Hu and Jennifer Scott. A Multilevel Algorithm for Wavefront Reduction. SIAM Journal on Scientific
Computing, 23:1352–1375, 2001.
[13] Arthur B. Kahn. Topological sorting of large networks. Communications of the ACM, 5:558–562, 1962.
[14] Wendy Myrwold and Willian Kocay. Errors in graph embedding algorithms. Journal of Computer and System
Sciences, 77:430–438, 2011.
[15] Patric R. J. Östergård. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics,
120:197–207, 2002.
[16] Bor Plestenjak. An Algorithm for Drawing Planar Graphs. Software: Practice and Experience, 29:973–984,
1999.
[17] Angelika Steger and Nicholas C. Wormald. Generating random regular graphs quickly. Combinatorics Prob-
ability and Computing, 8:377–396, 1999.
[18] Robert E. Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1:146–160,
1972.
[19] Robert E. Tarjan. Applications of path compression on balanced trees. Journal of the ACM, 26:690–715, 1979.
[20] Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all
maximal cliques and computational experiments. Theoretical Computer Science, 363:28–42, 2006.
[21] W. T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, s3-13:743–767, 1963.
[22] John Q. Walker II. A nodepositioning algorithm for general trees. Software: Practice and Experience,
20:685–705, 1990.
[23] E. Welch and S. Kobourov. Measuring Symmetry in Drawings of Graphs. Computer Graphics Forum,
36:341–351, 2017.
[24] Douglas B. West. Introduction to Graph Theory. Pearson Education, 2002.
85
Command Index
antiprism_graph .................. 18
complete_binary_tree ............... 14
complete_graph .................. 13
complete_kary_tree . . . . . . . . . . . . . . . . 14
cycle_graph .................... 12
digraph ....................... 10
graph ......................... 9
grid_graph ..................... 18
hypercube_graph .................. 16
interval_graph .................. 15
is_graphic_sequence ............... 15
kneser_graph .................... 15
lcf_graph ..................... 21
odd_graph ..................... 15
path_graph ..................... 13
petersen_graph . . . . . . . . . . . . . . . . . . 20
prism_graph .................... 18
sequence_graph . . . . . . . . . . . . . . . . . . 15
sierpinski_graph ................. 20
star_graph ..................... 17
torus_grid_graph ................. 18
trail ........................ 13
web_graph ..................... 17
wheel_graph .................... 17
87

Navigation menu