Graph Theory Package For Giac/Xcas Graphtheory User Manual
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 87
| Download | |
| Open PDF In Browser | View PDF |
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 . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Creating undirected graphs . . . . . . . . . . . . . .
2.1.2. Creating directed graphs . . . . . . . . . . . . . . .
2.1.3. Creating vertices . . . . . . . . . . . . . . . . . . . .
2.1.4. Creating edges and arcs . . . . . . . . . . . . . . . .
2.1.5. Creating paths and trails . . . . . . . . . . . . . . .
2.1.6. Specifying adjacency or weight matrix . . . . . . .
2.2. Promoting to directed and undirected graphs . . . . . .
2.2.1. Converting edges to pairs of arcs . . . . . . . . . .
2.2.2. Assigning weight matrix to an unweighted graph
2.3. Cycle and path graphs . . . . . . . . . . . . . . . . . . . .
2.3.1. Cycle graphs . . . . . . . . . . . . . . . . . . . . . . .
2.3.2. Path graphs . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3. Trails of edges . . . . . . . . . . . . . . . . . . . . . .
2.4. Complete graphs . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1. Complete graphs with multiple vertex partitions
2.4.2. Complete trees . . . . . . . . . . . . . . . . . . . . . .
2.5. Sequence graphs . . . . . . . . . . . . . . . . . . . . . . . .
2.5.1. Creating graphs from degree sequences . . . . . .
2.5.2. Validating graphic sequences . . . . . . . . . . . . .
2.6. Intersection graphs . . . . . . . . . . . . . . . . . . . . . .
2.6.1. Interval graphs . . . . . . . . . . . . . . . . . . . . . .
2.6.2. Kneser graphs . . . . . . . . . . . . . . . . . . . . . .
2.7. Special graphs . . . . . . . . . . . . . . . . . . . . . . . . .
2.7.1. Hypercube graphs . . . . . . . . . . . . . . . . . . . .
2.7.2. Star graphs . . . . . . . . . . . . . . . . . . . . . . . .
2.7.3. Wheel graphs . . . . . . . . . . . . . . . . . . . . . . .
2.7.4. Web graphs . . . . . . . . . . . . . . . . . . . . . . . .
2.7.5. Prism graphs . . . . . . . . . . . . . . . . . . . . . . .
2.7.6. Antiprism graphs . . . . . . . . . . . . . . . . . . . .
2.7.7. Grid graphs . . . . . . . . . . . . . . . . . . . . . . . .
2.7.8. Sierpi«ski graphs . . . . . . . . . . . . . . . . . . . .
2.7.9. Generalized Petersen graphs . . . . . . . . . . . . .
2.7.10. LCF graphs . . . . . . . . . . . . . . . . . . . . . . .
2.8. Isomorphic copies of graphs . . . . . . . . . . . . . . . . .
2.8.1. Creating an isomorphic copy of a graph . . . . . .
2.8.2. Permuting graph vertices . . . . . . . . . . . . . . .
2.8.3. Relabeling graph vertices . . . . . . . . . . . . . . .
2.9. Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.9.1. Extracting subgraphs . . . . . . . . . . . . . . . . . .
2.9.2. Induced subgraphs . . . . . . . . . . . . . . . . . . .
2.9.3. Underlying graphs . . . . . . . . . . . . . . . . . . .
2.10. Operations on graphs . . . . . . . . . . . . . . . . . . . .
2.10.1. Graph complement . . . . . . . . . . . . . . . . . .
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . 9
. . 9
. 10
. 10
. 10
. 11
. 11
. 12
. 12
. 12
. 12
. 12
. 13
. 13
. 13
. 13
. 14
. 15
. 15
. 15
. 15
. 15
. 15
. 16
. 16
. 17
. 17
. 17
. 18
. 18
. 18
. 20
. 20
. 21
. 22
. 22
. 22
. 22
. 23
. 23
. 23
. 24
. 24
. 24
4
Table of contents
2.10.2. Seidel switching . . . . . .
2.10.3. Transposing graphs . . . .
2.10.4. Union of graphs . . . . . .
2.10.5. Disjoint union of graphs .
2.10.6. Joining two graphs . . . .
2.10.7. Power graphs . . . . . . . .
2.10.8. Graph products . . . . . .
2.10.9. Transitive closure graph .
2.10.10. Line graph . . . . . . . . .
2.10.11. Plane dual graph . . . . .
2.11. Random graphs . . . . . . . . . .
2.11.1. Random general graphs .
2.11.2. Random bipartite graphs
2.11.3. Random trees . . . . . . . .
2.11.4. Random planar graphs . .
2.11.5. Random regular graphs .
2.11.6. Random tournaments . . .
2.11.7. Random ow networks . .
2.11.8. Randomizing edge weights
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
24
25
25
26
26
26
27
28
30
30
31
31
32
32
33
34
35
35
35
3. Modifying graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
3.1. Modifying vertices of a graph . . . . . . . . .
3.1.1. Adding and removing single vertices .
3.2. Modifying edges of a graph . . . . . . . . . .
3.2.1. Adding and removing single edges . .
3.2.2. Accessing and modifying edge weights
3.2.3. Contracting edges . . . . . . . . . . . . .
3.2.4. Subdividing edges . . . . . . . . . . . . .
3.3. Using attributes . . . . . . . . . . . . . . . . .
3.3.1. Graph attributes . . . . . . . . . . . . .
3.3.2. Vertex attributes . . . . . . . . . . . . .
3.3.3. Edge attributes . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
37
37
37
37
38
38
39
40
40
40
41
. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ...
43
4. Import and export
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.1. Importing graphs . . . . . . . . . . . .
4.1.1. Loading graphs from dot les . .
4.1.2. The dot le format overview . .
4.2. Exporting graphs . . . . . . . . . . . .
4.2.1. Saving graphs in dot format . .
4.2.2. Saving graph drawings in LATEX
5. Graph properties
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
43
43
43
44
44
44
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.1. Basic properties . . . . . . . . .
5.1.1. Listing vertices and edges
5.1.2. Vertex degrees . . . . . . .
5.1.3. Vertex adjacency . . . . .
5.1.4. Edge incidence . . . . . . .
5.2. Algebraic properties . . . . . . .
5.2.1. Adjacency matrix . . . . .
5.2.2. Weight matrix . . . . . . .
5.2.3. Incidence matrix . . . . . .
5.2.4. Characteristic polynomial
5.2.5. Graph spectrum . . . . . .
5.2.6. Seidel spectrum . . . . . .
5.2.7. Integer graphs . . . . . . .
.. .. .
.. .. .
.. .. .
.. .. .
.. .. .
format
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
47
47
48
49
50
50
51
51
52
53
53
54
Table of contents
5
5.3. Connectivity . . . . . . . . . . . . . . . . . . . . . .
5.3.1. Vertex connectivity . . . . . . . . . . . . . . .
5.3.2. Connected and biconnected components .
5.3.3. Graph rank . . . . . . . . . . . . . . . . . . . .
5.3.4. Articulation points . . . . . . . . . . . . . . .
5.3.5. Strongly connected components . . . . . . .
5.3.6. Edge connectivity . . . . . . . . . . . . . . . .
5.4. Trees . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1. Tree graphs . . . . . . . . . . . . . . . . . . . .
5.4.2. Forest graphs . . . . . . . . . . . . . . . . . . .
5.4.3. Height of a tree . . . . . . . . . . . . . . . . .
5.4.4. Lowest common ancestor of a pair of nodes
5.5. Distance . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1. Vertex distance . . . . . . . . . . . . . . . . .
5.5.2. All-pairs vertex distance . . . . . . . . . . . .
5.5.3. Diameter of a graph . . . . . . . . . . . . . .
5.5.4. Girth of a graph . . . . . . . . . . . . . . . . .
5.6. Acyclic graphs . . . . . . . . . . . . . . . . . . . . .
5.6.1. Checking if a graph is acyclic . . . . . . . .
5.6.2. Topological sorting . . . . . . . . . . . . . . .
5.6.3. st ordering . . . . . . . . . . . . . . . . . . . .
5.7. Vertex matching . . . . . . . . . . . . . . . . . . . .
5.7.1. Maximum matching . . . . . . . . . . . . . .
5.7.2. Maximum matching in bipartite graphs . .
5.8. Cliques . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8.1. Clique graphs . . . . . . . . . . . . . . . . . .
5.8.2. Triangle-free graphs . . . . . . . . . . . . . .
5.8.3. Maximal cliques . . . . . . . . . . . . . . . . .
5.8.4. Maximum clique . . . . . . . . . . . . . . . . .
5.8.5. Minimum clique cover . . . . . . . . . . . . .
5.9. Vertex coloring . . . . . . . . . . . . . . . . . . . . .
5.9.1. Greedy coloring . . . . . . . . . . . . . . . . .
5.9.2. Minimal coloring . . . . . . . . . . . . . . . .
5.9.3. Chromatic number . . . . . . . . . . . . . . .
5.9.4. k-coloring . . . . . . . . . . . . . . . . . . . . .
5.10. Edge coloring . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
54
54
55
56
56
56
57
57
57
58
58
58
59
59
59
59
59
60
60
60
61
61
61
62
63
63
63
63
64
65
66
66
66
68
69
70
6. Traversing graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
6.1. Walks and tours . . . . . . . . . . . . . . . .
6.1.1. Eulerian graphs . . . . . . . . . . . . .
6.1.2. Hamiltonian graphs . . . . . . . . . . .
6.2. Optimal routing . . . . . . . . . . . . . . . .
6.2.1. Shortest paths in unweighted graphs
6.2.2. Cheapest paths in weighted graphs .
6.2.3. Traveling salesman problem . . . . .
6.3. Spanning trees . . . . . . . . . . . . . . . . .
6.3.1. Constructing a spanning tree . . . . .
6.3.2. Minimal spanning tree . . . . . . . . .
6.3.3. Counting all spanning trees . . . . . .
.
.
.
.
.
.
.
.
.
.
.
71
71
71
71
71
72
72
72
72
72
72
7. Visualizing graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
7.1. Drawing graphs by using various methods
7.1.1. Overview . . . . . . . . . . . . . . . . .
7.1.2. Drawing disconnected graphs . . . .
7.1.3. Spring method . . . . . . . . . . . . . .
7.1.4. Drawing trees . . . . . . . . . . . . . .
75
75
75
76
78
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
7.1.5. Drawing planar graphs . . . .
7.1.6. Circular graph drawings . . .
7.2. Custom vertex positions . . . . . .
7.2.1. Setting vertex positions . . .
7.2.2. Generating vertex positions .
7.3. Highlighting parts of a graph . . .
7.3.1. Highlighting vertices . . . . .
7.3.2. Highlighting edges and trails
7.3.3. Highlighting subgraphs . . .
Table of contents
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
79
80
81
81
81
82
82
83
84
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
Command Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
Chapter 1
Introduction
1.1. Overview
This document contains an overview of the graph theory commands built in the Giac/Xcas software, 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 rst 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 rst 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. HarriesWong graph: harries-wong
11. Heawood graph: heawood
9
10
Constructing graphs
12. Herschel graph: herschel
13. Icosahedral graph: icosahedron
14. Levi graph: levi
15. Ljubljana graph: ljubljana
16. McGee graph: mcgee
17. MöbiusKantor 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 dierent 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 speci ed inside a set so that it can be distinguished from a (adjacency or
weight) matrix. If only a set of edges/arcs is speci ed, 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.
2.1 General graphs
11
> graph(%{[a,b],[b,c],[a,c]%})
an undirected unweighted graph with 3 vertices and 3 edges
Edge weights may also be speci ed.
> 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 speci ed rst.
> 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 n vertices 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 ]n of 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; 1g is 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 n vertices will be created and i-th and j-th vertex will be connected i 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
12
Constructing graphs
List of vertex labels can be speci ed 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 rst specify the list of n vertices and the set of edges,
followed by a square matrix A of order n. Then for every edge fi; j g or arc (i; j) the element
aij of A is assigned as its weight. Other elements of A are 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 jV j. Every edge fi; j g 2 E is replaced with the pair
of arcs (i; j) and (j ; i). If matrix A is speci ed, aij and a ji 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 A of order jV j. If the matrix speci cation is omitted, a square matrix
of ones is assumed. Then a copy of G is returned where each edge/arc (i; j) 2 E gets aij assigned
as its weight. If G is an undirected graph, it is assumed that A is 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.
2.4 Complete graphs
13
cycle_graph accepts a positive integer n or a list of distinct vertices as its only argument and
returns the graph consisting of a single cycle through the speci ed vertices in the given order. If n
is speci ed it is assumed to be the desired number of vertices, in which case they will be created
and labeled with the rst n integers (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
4
1
3
2
> 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 n or a list of distinct vertices as its only argument and
returns a graph consisting of a single path through the speci ed vertices in the given order. If n
is speci ed it is assumed to be the desired number of vertices, in which case they will be created
and labeled with the rst n integers (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 speci ed 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.
14
Constructing graphs
If complete_graph is called with a single argument, a positive integer n or a list of distinct vertices,
it returns the complete graph with the speci ed vertices. If integer n is speci ed, it is assumed that
it is the desired number of vertices and they will be created and labeled with the rst n integers
(starting from 0 in Xcas mode and from 1 in Maple mode).
If a sequence of positive integers n1; n2; :::; nk is 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
4
1
3
2
> 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
3
1
4
2
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 speci ed depth use the command complete_kary_tree.
complete_kary_tree accepts k and 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
2.6 Intersection graphs
15
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 L of positive integers as its only argument and, if L represents a
graphic sequence, the corresponding graph G with jLj vertices 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 G is constructed in O(jLj2 log 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 L of positive integers as its only argument and returns true if
there exists a graph G(V ; E) with degree sequence fdeg v: v 2 V g equal to L and 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.
16
Constructing graphs
kneser_graph accepts two positive integers n 20 and k as its arguments and returns the Kneser
graph K(n; k). The latter is obtained by setting all k-subsets of a set of n elements 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 n and k. Note that
the number of vertices in K(n; k) is equal to nk .
> 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 = d for d > 1.
odd_graph accepts a positive integer d 8 as its only argument and returns d-th odd graph
K(2 d + 1; d). Note that the odd graphs with d > 8 will 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 n as its only argument and returns the hypercube
graph of dimension n on 2n vertices. The vertex labels are strings of binary digits of length n.
Two vertices are joined by an edge if and only if their labels dier 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)
2.7 Special graphs
17
> 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 n as 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 n as 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 a and b as its arguments and returns the web graph with
parameters a and 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
18
Constructing graphs
> 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 n as 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 n as its only argument and returns the antiprism
graph with parameter n, which is constructed from two concentric cycles of n vertices 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.
2.7 Special graphs
19
grid_graph accepts two positive integers m and n as its arguments and returns the m by n grid
on m n vertices, 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 oppposite 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 m and n as its arguments and returns the m by 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)
20
Constructing graphs
2.7.8. Sierpi«ski graphs
The command sierpinski_graph is used for creating Sierpi«ski-type graphs Skn and STkn [9].
sierpinski_graph accepts two positive integers n and k as its arguments (and optionally the
symbol triangle as the third argument) and returns the Sierpi«ski (triangle) graph with parameters n and k.
The Sierpi«ski triangle graph STkn is obtained by contracting all non-clique edges in Skn. 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, ST3n is 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, n and 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 ofin Schlä i notationan inner star polygon fn; kg and an outer regular
polygon fng such that the n pairs of corresponding vertices in inner and outer polygons are
connected with edges. For k = 1 the prism graph of order n is 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
2.7 Special graphs
21
> 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öbiusKantor 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
8 9
7
2
15
10
14
11
6
3
1312
5
4
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 notation2.2.
lcf_graph takes one or two arguments, a list L of nonzero integers, called jumps, and optionally
a positive integer n, called exponent (by default, n = 1). The command returns the graph on n jLj
vertices obtained by iterating the sequence of jumps n times.
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.
22
Constructing graphs
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 constructing 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 jV j, and returns the copy of graph G with 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 L of length
jV j containing all vertices from V in a certain order, and returns a copy of G with vertices
rearranged as speci ed 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 L of vertex
labels, and returns the copy of G with 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)
2.9 Subgraphs
23
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: G and 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 G induced by set of vertices L V , use the command induced_subgraph.
induced_subgraph accepts two arguments G and L and returns the subgraph of G formed by all
edges in E which 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))
24
Constructing graphs
2.9.3. Underlying graphs
For every graph G(V ; E) there is an undirected and unweighted graph U (V ; E 0), called the
underlying graph of G, where E 0 is obtained from E by dropping edge directions.
To construct U use the command underlying_graph which accepts G as its only argument. The
result is obtained by copying G and 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 ; E c) of G, where E c is 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
4
1
3
2
> G:=graph_complement(C5)
an undirected unweighted graph with 5 vertices and 5 edges
> draw_graph(G)
0
4
1
3
2
2.10.2. Seidel switching
The command seidel_switch is used for Seidel switching in graphs.
2.10 Operations on graphs
25
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 G in which, for each vertex v 2 L, 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
4
1
3
2
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 ;
E 0) of G where E 0 = f(j ; i): (i; j) 2 E g, i.e. returns the copy of G with the directions of all edges
reversed.
Note that reverse_graph is de ned for both directed and undirected graphs, but gives meaningful
results only for directed graphs.
GT is also called the transpose graph of G because adjacency matrices of G and GT are 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 [ [ Vk and 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)
26
Constructing graphs
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 v 2 Vk and all edges with
strings k:e where e 2 Ek and calling the graph_union
command subsequently.
As all vertices and
P
P
edges are labeled dierently, it follows jV j = nk=1 jVk j and jE j = nk=1 jEk j.
> 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 G and H as its arguments and returns the graph which is obtained
by connecting all the vertices of G to all vertices of H. The vertex labels in the resulting graph
are strings of the form 1:u and 2:v where u is a vertex in G and v is 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)
2:0
1:1
1: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 Gk of G with vertices V such that v; w 2 V are connected with an edge if and only if
there exists a path of length at most k in G.
The graph Gk is constructed from its adjacency matrix Ak which is obtained by adding powers of
the adjacency matrix A of G:
Ak =
k
X
i=1
Ak:
2.10 Operations on graphs
The above sum is obtained by assigning Ak A and repeating the instruction Ak
k ¡ 1 times, so exactly k matrix multiplications are required.
27
(Ak + I) A for
> 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 Gn of the input graphs. The Cartesian
product G(V ; E) = G1 G2 is the graph with list of vertices V = V1 V2, labeled with strings v1:v2
where v1 2 V1 and v2 2 V2, such that (u1:v1,u2:v2)2E if and only if u1 is adjacent to u2 and v1 = v2
or u1 = u2 and v1 is 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)
28
Constructing graphs
> 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 Gn of the input graphs. The tensor product
G(V ; E) = G1 G2 is the graph with list of vertices V = V1 V2, labeled with strings v1:v2 where
v1 2 V1 and v2 2 V2, such that (u1:v1,u2:v2)2E if and only if u1 is adjacent to u2 and v1 is 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 2 V are connected by an edge (arc) e = vw 2 E 0 if and only if there exists a (directed)
path from v to w in G.
2.10 Operations on graphs
29
transitive_closure accepts one or two arguments, the input graph G and optionally the option
weighted=true (or simply weighted) or the option weighted=false (which is the default). The
command returns the transitive closure T of the input graph G. If G is a digraph, then T is also a
digraph. When weighted=true is speci ed, the graph T is weighted such that the weight of edge
v w 2 E 0 is equal to the length (or weight, if G is weighted) of the shortest path from v to w in 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 G is unweighted. Therefore T is constructed
in at most O(jV j3) time if weighted=true resp. O(jV j jE j) 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))
30
Constructing graphs
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 G as its only argument and returns the line graph L(G) with
jE j distinct vertices, one vertex for each edge in E. Two vertices v1 and v2 in L(G) are adjacent if
and only if the corresponding edges e1; e2 2 E have a common endpoint. The vertices in L(G) are
labeled with strings in form v-w, where e = vw 2 E.
> 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 biconnected planar graph.
plane_dual accepts one argument, the input graph G(V ; E) or the list F of faces of a planar
embedding of G, and returns the graph H with faces of G as 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 de ned for multigraphs2.3. By the strict de nition,
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 simpli ed de nition suitable
for simple graphs is used.
The algorithm runs in O(jV j2) 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 D has six vertices. Also, every face obviously
shares an edge with exactly four other faces, so the degree of each vertex in D is equal to 4.
> D:=plane_dual(H)
2.3. See https://en.wikipedia.org/wiki/Dual_graph for the strict de nition of plane dual graph.
2.11 Random graphs
31
an undirected unweighted graph with 6 vertices and 12 edges
> draw_graph(D,spring)
A graph isomorphic to D is obtained when passing a list of faces of H to 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 rst argument is a positive
integer n or a list of labels L of length n. The second argument is a positive real number p < 1 or
a positive integer m. The command returns a random (di)graph on n vertices (using elements of
L as vertex labels) in which each edge/arc is inserted with probability p or which contains exactly
m edges/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)
32
Constructing graphs
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 rst argument is either a positive integer
n or a list of two positive integers a and b. The second argument is either a positive real number
p < 1 or a positive integer m. The command returns a random bipartite graph on n vertices (or
with two partitions of sizes a and b) in which each possible edge is present with probability p (or
m edges 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 n as its only argument and returns a random tree generated
on n nodes (i.e. inserts n ¡ 1 edges in the initially empty graph).
> T:=random_tree(30)
an undirected unweighted graph with 30 vertices and 29 edges
2.11 Random graphs
33
> 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 L of length
n), a positive real number p < 1 and optionally an integer k 2 f0; 1; 2; 3g (by default, k = 1). The
command returns a random k-connected planar graph on n vertices (using elements of L as vertex
labels).
The result is obtained by rst 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(jV j) if k = 0, O(jV j2) if k 2 f1; 2g and O(jV j3)
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)
34
Constructing graphs
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 L of
length n) and a nonnegative integer d. Optionally, the option connected may be speci ed as the
third argument, indicating that the generated graph must be 1-connected (by default no restriction
is made). The command creates n vertices (using elements of L as vertex labels) and returns a
random d-regular (connected) graph on these vertices.
Note that a d-regular graph on n vertices 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 d not growing so quickly with n the probability distribution converges to uniformity.
The runtime of the algorithm is negligible for n 6 100. 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.
2.11 Random graphs
35
> 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)
15
11
9
13
2
14 0
4
7
12
10
6
8
5
1
3
2.11.6. Random tournaments
The command random_tournament is used for generating random tournaments. A tournament of
order n is 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 L of length n) as its only argument and
returns a random tournament on n vertices. If L is speci ed, 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 ow 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 rst 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
m resp. n. The command operates such that for each edge e 2 E, its weight is chosen uniformly
from the real interval [a; b) or from the set of integers lying between m and n, including both m
and n. After assigning weights to all edges, the modi ed copy of G is returned.
36
Constructing graphs
> 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)
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 v or a list
of labels L, and returns the graph G 0 (V [ fvg; E) or G 00 (V [ L; E) if a list L is 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 G won'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 v or a
list of labels L, and returns the graph
G 0 (V n fv g; fe 2 E: e is not incident to v g)
or, if L is given,
G 00 (V n L; fe 2 E: e is not incident to any v 2 Lg):
If any of the speci ed 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
38
Modifying graphs
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 G with the speci ed
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 speci ed 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 e 2 E and the
new weight w, which may be any number. It returns the modi ed copy of G.
The command get_edge_weight accepts two arguments, a weighted graph G(V ; E) and an edge
or arc e 2 E. 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) 2 E, and
merges w and v into a single vertex, deleting the edge e. The resulting vertex inherits the label of
v. The command returns the modi ed graph G 0 (V n fwg; E 0).
> K5:=complete_graph(5)
an undirected unweighted graph with 5 vertices and 10 edges
> contract_edge(K5,[1,2])
3.2 Modifying edges of a graph
39
an undirected unweighted graph with 4 vertices and 6 edges
To contract a set fe1; e2; :::; ek g E of 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 K5 is 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
4
1
3
2
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 E and optionally a positive integer r (which defaults to 1). Each of the speci ed
edges/arcs will be subdivided with exactly r new 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
13
5
14
4
1
9
6
11
12
8
3
7
10
2
40
Modifying graphs
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
modi ed 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 G and a sequence or list of graph attributes in form
tag=value where tag is any string. Alternatively, attributes may be speci ed as a sequence of two
lists [tag1,tag2,...] and [value1,value2,...]. The command sets the speci ed values to the
indicated attribute slots, which are meant to represent some global properties of the graph G, and
returns the modi ed copy of G.
The previously set graph attribute values can be fetched with the command get_graph_attribute
which accepts two arguments: a graph G and 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 G for which the values are set, use the list_graph_attributes
command which takes G as its only argument.
To discard a graph attribute, use the discard_graph_attribute command. It accepts two arguments: a graph G and a sequence or list of tags to be cleared, and returns the modi ed copy of G.
Two tags are normally being used by the CAS commands: directed and weighted, so it is not advisable 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 modi ed 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 v 2 V and a sequence or list
of attributes in form tag=value where tag is any string. Alternatively, attributes may be speci ed
as a sequence of two lists [tag1,tag2,...] and [value1,value2,...]. The command sets the
speci ed values to the indicated attributes of the vertex v and returns the modi ed copy of G.
3.3 Using attributes
41
The previously set attribute values for v can be fetched with the command get_vertex_attribute
which accepts three arguments: G, v and 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 v for which the values are set, use the list_vertex_attributes command
which takes two arguments, G and v.
The discard_vertex_attribute command is used for discarding attribute(s) assigned to some
vertex v 2 V . It accepts three arguments: G, v and a sequence or list of tags to be cleared, and
returns the modi ed 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 dierent 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")
root
2
11
0
1
3
7
12
6
13
14
4
8
9
10
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 modi ed 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 e 2 E and a sequence or list
of attributes in form tag=value where tag is any string. Alternatively, attributes may be speci ed
as a sequence of two lists [tag1,tag2,...] and [value1,value2,...]. The command sets the
speci ed values to the indicated attributes of the edge/arc e and returns the modi ed copy of G.
42
Modifying graphs
The previously set attribute values for e can be fetched with the command get_edge_attribute
which accepts three arguments: G, e and 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 e for which the values are set, use the list_edge_attributes command
which takes two arguments, G and e.
To discard attribute(s) assigned to e call the discard_edge_attribute command, which accepts
three arguments: G, e and a sequence or list of tags to be cleared, and returns the modi ed 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 dierent 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
7
4
8
9
5
10 11
6
12 13
14
Chapter 4
Import and export
4.1. Importing graphs
4.1.1. Loading graphs from dot les
The command import_graph is used for importing a graph from text le in dot format4.1.
import_graph accepts a string filename as its only argument and returns the graph constructed
from instructions written in the le filename or undef on failure. The passed string should contain
the path to a le in dot format. The le 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 speci ed.
If a relative path to the le is speci ed, 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 le 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 le format overview
Giac has some basic support for dot language4.3. Each dot le 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 les to avoid a certain confusion between dierent
le 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 de nition see https://www.graphviz.org/doc/info/lang.html.
43
44
Import and export
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 dierentiate between simple graphs (strict) and multigraphs (nonstrict). 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 V2 ::: Vk [attributes]? edges and trails
graph [attributes]
graph attributes
Here, attributes is a comma-separated list of tag-value pairs in form tag=value, 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 speci ed, each
vertex from that set is connected to the neighbor operands. Every speci ed 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 le which de nes 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 LATEX format.
4.2.1. Saving graphs in dot format
export_graph accepts two mandatory arguments, a graph G and a string filename, and writes G
to the le speci ed by filename, which must be a path to the le, 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 le 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 LATEX format
When calling the export_graph command, an optional third argument in form latex[=]
may be given. In that case the drawing of G (obtained by calling the draw_graph command) will
be saved to the LATEX le 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.
4.2 Exporting graphs
45
For example, let us create a picture of the Sierpi«ski sieve graph of order n = 5, i.e. the graph ST35.
> 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 LATEX le obtained by exporting a graph is easily converted into an EPS le, 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 le, 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 le 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 les. The above two commands can be combined in a simple shell script
which takes the name of the exported le (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.
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
Fig. 4.1. drawing of the Sierpi«ski graph
b
b
b
b
b
b
ST35
b
b
b
b
b
b
b
b
b
b
using LATEX and PSTricks
4.4. Alternatively, a PSTricks picture from the body of the .tex le can be copied to some other LATEX document.
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 V in the same order in which they were created.
edges accepts one or two arguments, a graph G(V ; E) and optionally the identi er weights. The
command returns the set of edges E (in a non-meaningful order). If weights is speci ed, each edge
is paired with the corresponding weight (in this case G must 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 v 2 V , and returns the
cardinality of the set fw 2 V : (v; w) 2 E g, i.e. the number of vertices in V which 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) 2 E resp. the number of arcs (v; w) 2 E, where w 2 V .
> G:=graph(trail(1,2,3,4,1,5,6,7,1,8,9,4))
47
48
Graph properties
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 v 2 V , 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 V in the same order as returned by the command vertices. If G is 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 2 V . The
command returns true if uv 2 E and false otherwise.
For digraphs, there is the similar command has_arc with the same input syntax. Note, however,
that the order of vertices u and v matters 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
5.1 Basic properties
49
> 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 rst, mandatory argument is the input graph
G(V ; E). The second, optional argument is a vertex v 2 V . The command returns the list of
neighbors of v in G if v is 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 v in 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 optionally a vertex v 2 V , and returns the list Lv containing all vertices w 2 V for which v w 2 E
resp. wv 2 E. If v is omitted, the list of lists Lv for every v 2 V is 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)
7
8
6
4
1
2
3
5
> 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.
50
Graph properties
incident_edges accepts two argument, the input graph G(V ; E) and a vertex v 2 V or a list of
vertices L V . The command returns the list of edges e1; e2; :::; ek 2 E which have v as one of its
endpoints.
Note that edge directions are ignored when G is 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; :::; vn g.
adjacency_matrix accepts the input graph G as its only argument and returns the square matrix
A = [ai j ] of order n such that, for i; j = 1; 2; :::; n,
ai j =
1, if the set E contains edge/arc vi v j ,
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
> transpose(A)==A
B
B
B
B
B
B
@
0
1
1
1
1
0
1
0
1
1
0
1
1
1
0
0
1
1
1
1
0
0
1
1
1
0
1
1
0
1
0
1
1
1
1
0
1
C
C
C
C
C
C
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
5.2 Algebraic properties
51
> draw_graph(D)
1
3
5
6
2
4
7
8
> A:=adjacency_matrix(D)
0
> transpose(A)==A
B
B
B
B
B
B
B
B
B
B
@
0
0
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
C
C
C
C
C
C
C
C
C
C
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; :::; vn g.
weight_matrix accepts the input graph G as its only argument and returns the square matrix
M = [mi j] of order n such that mij equals zero if vi and v j are not adjacent and the weight of the
edge/arc vi v j otherwise, 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
@
0
1
0
0
0
1
0
2
0
4
0
2
0
0
0
0
0
0
0
3
0
4
0
3
0
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; :::; vn g and E = fe1; e2; :::;
em g, as its only argument and returns the n m matrix B = [bi j ] such that, for all i = 1; 2; :::; n
and j = 1; 2; :::; m,
1; if the vertex vi is incident to the edge e j ,
bij =
0; otherwise
52
Graph properties
if G is undirected resp.
bij =
if G is directed.
8
<
1; if the vertex vi is the head of the arc e j ,
¡1; if the vertex vi is the tail of the arc e j ,
:
0; otherwise
> 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
1
B 1
B
@ 0
0
1
0
1
0
1
0
0
1
0
1
1
0
0
1
0
1
1
0
0 C
C
1 A
1
> 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
5
2
4
3
> 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 ¡1 0 0 0 1 0 0 0
1 0 ¡1 ¡1 0 0 0 1 0
0 0 1 0 ¡1 0 0 0 1
0 0 0 1 1 ¡1 ¡1 0 0
0 1 0 0 0 0 1 ¡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 optionally a value or symbol x. The command returns p(x), where p is 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)
5.2 Algebraic properties
53
x3 ¡ 2 x
> 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 G as its only argument and returns the list in which
every element is an eigenvalue of the adjacency matrix of G paired with its multiplicity.
> C5:=cycle_graph(5)
C5: an undirected unweighted graph with 5 vertices and 5 edges
> gs:=graph_spectrum(C5)
0
> p:=charpoly(C5,x)
> expand(roots(p))==expand(gs)
1
2
1
p
B
C
5 ¡1
B
2 C
B
C
B p2
C
@ ¡ 5¡1
A
2
2
x5 ¡ 5 x3 + 5 x ¡ 2
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 ¡ 2 A paired with its multiplicity. Here J is
all-one n n matrix, I is the identity matrix of order n, A is the adjacency matrix of G and n = jV j.
> G:=graph("clebsch")
an undirected unweighted graph with 16 vertices and 40 edges
> seidel_spectrum(G)
¡3 10
5 6
> P:=graph("petersen")
an undirected unweighted graph with 10 vertices and 15 edges
54
Graph properties
> 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 G as its only argument. The return value is true if
G is 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.
G is connected or 1-connected if for every pair v; w 2 V there exists a path with endpoints u and
v in G or in the underlying graph of G if the latter is directed.
G is biconnected or 2-connected if it remains connected after removing a vertex from G.
G is 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- rst search (see [7] and [18]). Both
algorithms run in O(jV j + jE j) time. The algorithm for checking 3-connectivity is quite simple but
less e cient: it works by choosing a vertex v 2 V and checking if the subgraph induced by V n fv g
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(jV j jE j).
> 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])
5.3 Connectivity
55
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; :::; Vk g of V such that the subgraph Gi G
induced by Vi is 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 G are easily obtained by depth- rst search in O(jV j + jE j) time. To
nd 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)
8
14
3
9
7
13
0
4
10
12
11
6
5
2
1
> H:=graph(trail(1,2,3,4,2),trail(4,5,6,7,5))
an undirected unweighted graph with 7 vertices and 8 edges
56
Graph properties
> draw_graph(H)
1
7
2
6
3
5
4
> 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 jV j ¡ k where k is the number of connected components of
the spanning subgraph of G with 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 v 2 V is an articulation point of G if the subgraph H G
induced by V n fvg is disconnected.
The articulation points of G are found by depth- rst serach in O(jV j + jE j) 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 H is strongly connected if for each pair (v; w) of distinct
vertices in H there is a (directed) path from v to w in H.
5.4 Trees
57
strongly_connected_components accepts the input graph G(V ; E) as its only argument and
returns the minimal partition fV1; V2; :::; Vk g of V such that the subgraph Gi G induced by Vi is
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(jV j + jE j) 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 G is strongly
connected. It accepts G as its only argument and returns true if G has 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
3
2
> 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 jV j = jE j + 1 and G is connected.
is_tree accepts the input graph G as its only argument and returns true if G is a tree and false
otherwise.
The only expensive step in the algorithm is determining whether G is connected. The condition
jV j = jE j + 1 is checked rst, hence the algorithm runs in O(jV j) time.
> is_tree(complete_binary_tree(3))
true
> is_tree(cycle_graph(5))
false
58
Graph properties
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 G as its only argument and returns true if G is a forest and
false otherwise.
The only expensive step in the algorithm is the decomposition of G to connected components.
Therefore the algorithm runs in O(jV j + jE j) 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 speci ed
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 r 2 V , which is
used as the root node. The command returns the height of G with respect to r.
The strategy is to start a depth- rst search from the root node and look for the deepest node.
Therefore the algorithm runs in O(jV j) 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 r 2 V . There are two possibilities for specifying the nodes to operate on: either the
nodes u; v 2 V are 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 ; vi 2 V and ui =
/ vi for i = 1; 2; :::; k, is given as the
third argument. The command returns the LCA of u and v or the list containing LCA of every
pair of nodes ui ; vi for i = 1; 2; :::; k.
The strategy is to use Tarjan's o ine LCA algorithm [19]. The implementation is simple and
uses the disjoint-set (union- nd) data structure. It runs in nearly linear time.
5.5 Distance
59
In the following example, the algorithm e ciency is tested on a large random tree with 10000 nodes.
The lowest common ancestors for the list L cotaining 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 v 2 V called the
source and a vertex w 2 V called the target, or a list L V of target vertices. The command returns
the distance between v and w as the number of edges in a shortest path from v to 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 G is de ned 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- rst search from each vertex of the input graph. The runtime is
therefore O(jV jjE j).
> G:=graph("petersen")
an undirected unweighted graph with 10 vertices and 15 edges
> girth(G)
60
Graph properties
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 G is
acyclic and false otherwise.
The algorithm attempts to nd topological order for its vertices. If that succeeds, the graph is
acyclic, otherwise not. The algorithm runs in O(jV j + jE j) 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 nding 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 G in a particular order: a vertex u precedes a vertex v if u v 2 E, i.e. if there is an arc
from u to 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 nds the required ordering by applying
Kahn's algorithm [13], which runs in O(jV j + jE j) 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)
5.7 Vertex matching
61
true
> topologic_sort(G)
[c; a; b; d]
5.6.3. st ordering
The command st_ordering is used for nding 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 s 2 V called
the source, a vertex t 2 V called the target or sink such that st 2 E and optionally an unassigned
identi er D. The command returns the permutation which de nes a particular order of vertices
in V . That ordering de nes the orientation for each edge e 2 E, which causes G to become acyclic
with a single source s and sink t. The ordering de ned by is the topological ordering of the
resulting digraph. If the optional argument D is given, the digraph is stored to it.
The orientation of e = u v 2 E is determined by the ordinals n and m of its endpoints u and v,
respectively, which are assigned by the permutation . If n < m, then u is the head and v is the
tail of the corresponding arc, and vice versa otherwise.
Note that the input graph G has a st-orientation if and only if G is biconnected. Furthermore, if
the latter is true, a st-orientation can be computed for any pair s; t 2 V such that st 2 E.
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(jV j + jE j) time, to nd 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
d
c
5.7. Vertex matching
5.7.1. Maximum matching
The command maximum_matching is used for nding 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; :::; em 2 E such that ei and ej are not adjacent (i.e. have no common endpoints) for all
1 6 i < j 6 m, under condition that m is maximal. Edges ek for k = 1; :::; m represent the matched
pairs of vertices in G.
62
Graph properties
The command applies Edmonds' blossom algorithm5.1 [4], which nds maximum matching in
O(jV j2 jE j) 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 G as its only argument
and returns a sequence containing two elements: the size of the maximum matching and the list
¡p
of edges connecting matched pairs of vertices. The algorithm runs in O
jV j jE j time.
> 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.
5.8 Cliques
63
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 G is 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 G as its only argument and returns true if G is trianglefree and false otherwise.
The strategy is to check whether tr (A3) = 0, where A is 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 A is 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 V to it. To count all maximal
cliques in a graph one can use the clique_stats command.
clique_stats accepts G as 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 ( rst) and
the number nk > 0 of 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 k or an interval m .. n with integer bounds. In the rst case only the
number of k-cliques for the given k is returned; in the second case, only cliques with cardinality
between m and n (inclusive) are counted.
64
Graph properties
The strategy used to nd all maximal cliques is a variant of the algorithm of Bron and Kerbosch
as described in [20]. Its worst-case running time is O(3jV j/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
> G:=random_graph(100,0.5)
B
B
B
B
B
B
@
3
4
5
6
7
8
14
185
370
201
47
5
1
C
C
C
C
C
C
A
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
1
5 153444
@ 6 18486 A
7 355
1.218 sec
5.8.4. Maximum clique
The largest maximal clique in the graph G(V ; E) is called maximum clique. The command maximum_clique can be used to nd one in the given graph.
maximum_clique accepts the graph G as its only argument and returns maximum clique in G
as a list of vertices. The clique may subsequently be extracted from G using the command
induced_subgraph.
The strategy used to nd 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))
5.8 Cliques
65
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; :::; Ck g of cliques in
G such that for every v 2 V there exists i 6 k such that v 2 Ci. In Giac, such cover can be obtained
by calling the clique_cover command.
clique_cover accepts graph G as 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 k is less or equal to the given integer is set. If no such cover is found, clique_cover returns
empty list.
The strategy is to nd the minimal vertex coloring in the complement Gc of G (note that these
two graphs share the same set of vertices). Each set of equally colored vertices in Gc corresponds
to a clique in G. Therefore, the color classes of Gc map to the elements C1; :::; Ck of the minimal
clique cover in G.
There is a special case in which G is triangle-free, which is treated separately. Such a graph G
contains only 1- and 2-cliques; in fact, every clique cover in G consists of a matching M together
with the singleton cliques (i.e. the isolated vertices which remain unmatched). The total number
of cliques in the cover is equal to jV j ¡ jM j, hence to nd the minimal cover one just needs to nd
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 nd minimal clique cover in the truncated icosahedral graph it su ces to nd 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 ve, but not with three cliques.
> clique_cover(graph("petersen"),3)
[]
> clique_cover(graph("petersen"),5)
66
Graph properties
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 v 2 V a positive integer.
Each integer represents a distinct color. The key property of a graph coloring is that the colors
of adjacent vertices must dier from one another. Two dierent colorings of G may use dierent
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 jV j may be passed as the second argument. Vertices are colored one by one in the order
speci ed by p (or in the default order if p is 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, dierent choices of permutation p produce dierent colorings. The total number of
dierent colors may not be the same each time. The complexity of the algorithm is O(jV j + jE j).
> 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 dierent 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 rst 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 G is 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 modi ed copy of G.
5.9 Vertex coloring
67
value
1
2
3
4
5
6
7
color
red
green
yellow
blue
magenta
cyan
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 branchand-bound method with speci c branch/backtrack techniques [3]. Lower and upper bounds for the
number of colors n are obtained by nding a maximal clique (n cannot be lower than its cardinality)
and by using the heuristic proposed by Brélaz in [1] (which will use at least n colors), 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 di cult ones) one may
have to wait for several minutes, even hours, and sometimes for a practically in nite time. Note that
MVCP is a NP-hard problem, which means that no polynomial (i.e. e cient) algorithm is known.
In the following example, the Grotzsch graph is colored with minimal number of colors by rst
nding 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 nding an optimal coloring in G is equivalent to nding the minimal clique
cover in its complement Gc.
First, a random graph G with 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/
68
Graph properties
Next, all maximal cliques in Gc are counted using the clique_stats command.
> S:=clique_stats(graph_complement(G))
0
1
3 5
B 4 66 C
B
C
B 5 238 C
B
C
@ 6 89 A
7 3
> n:=sum(col(S,1))
401
To obtain the minimal coloring, a naive algorithm must check P
if a combination
of 2; 3; :::; 8 maximal
8
cliques forms a cover in Gc. In the worst case it will check k=2 nk combinations, 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 dierent graphs of exactly the same size (but which do not share the
same edge structure) may take quite dierent 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
d
10 k vertices and edge density 10 for k = 1; 2; :::; 7 and 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 chromatic 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 identi er 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 G of the graph G in 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 G found by the algorithm.
The strategy is call minimal_vertex_coloring in the case of exact computation. When approximating 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 G is usually very fast, but the dierence between the bounds grows with jV j.
Unless the input graph is sparse enough, the algorithm slows down considerably for jV j > 40.
5.9 Vertex coloring
number of vertices
10
20
30
40
50
69
0.1
0.0008892
0.0014682
0.0021163
0.0252134
0.130089
0.2
0.0010818
0.00378
0.0173315
0.177707
1.83819
edge density
0.3
0.4
0.0006116
0.0005825
0.0038329
0.0077918
0.0372468
0.111016
0.626175
1.67746
17.3564
120.181
0.5
0.0006331
0.0067932
0.143657
2.31473
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 k colors.
is_vertex_colorable accepts two or three arguments: the input graph G(V ; E), a positive integer
k and optionally an unassigned identi er. The command returns true if G can be colored using
at most k colors and false otherwise. If an identi er is given, a coloring using at most k colors is
stored to it as a list of vertex colors, in the order of vertices(G).
The strategy is to rst 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 nd the chromatic number G using k as 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)
70
Graph properties
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 G by utilizing the
next command line is simpler, but requires much more time.
> chromatic_number(G)
6
92.7 sec
5.10. Edge coloring
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 nding Eulerian trails in such graphs.
is_eulerian accepts one or two arguments, the input graph G(V ; E) and optionally an unassigned
identi er T , and returns true if G is Eulerian and false otherwise. If T is given, the corresponding
Eulerian trail is stored to it.
The graph G is 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
e 2 E must 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 nding an Eulerian path [8]. It works by
covering one cycle at a time in the input graph. The required time is O(jE j).
> 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 nd the shortest path between two vertices in an undirected unweighted graph.
shortest_path accepts three arguments: a graph G(V ; E), the source vertex s 2 V and the target
vertex t 2 V or a list T of target vertices. The shortest path from source to target is returned. If more
targets are speci ed, the list of shortest paths from the source to each of these vertices is returned.
The strategy is to run breadth- rst traversal on the graph G starting from the source vertex s.
The complexity of the algorithm is therefore O (jV j + jE j).
> G:=graph("dodecahedron")
an undirected unweighted graph with 20 vertices and 30 edges
> shortest_path(G,1,16)
[1; 6; 11; 16]
71
72
Traversing graphs
> 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
6
15
11
5
2
16
20
10
7
17
19
14
12
18
13
9
4
8
3
6.2.2. Cheapest paths in weighted graphs
The command dijkstra is used to nd 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 s 2 V and optionally a vertex t 2 V or list T of vertices in V . It returns the cheapest path
from s to t or, if more target vertices are given, the list of such paths to each target vertex t 2 T ,
computed by Dijkstra's algorithm in O(jV j2) time. If no target vertex is speci ed, all vertices in
V n fsg are assumed to be targets.
A cheapest path from s to t is represented with a list [[v1,v2,...,vk],c] where the rst element
consists of path vertices with v1 = s and vk = t, while the second element c is 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 G and optionally
a vertex r 2 V . It returns the spanning tree T of G rooted in r or, if none is given, in the rst
vertex in the list V , obtained by depth- rst traversal in O(jV j + jE j) 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(jE j log jV j) 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 n of mutually dierent spanning trees in G.
6.3 Spanning trees
73
The strategy is based on Theorem 2.2.12 (Matrix Tree Theorem) in [24], page 86. First the adjacency matrix A and the degree sequence of G are obtained. Then the matrix B = ¡ A is
computed, where is the diagonal matrix of order jV j corresponding to . The last row and the
last column of B are popped out, yielding the matrix C of order jV j ¡ 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
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 rst one being the graph G(V ; E). This
command assigns 2D or 3D coordinates to each vertex v 2 V and produces a visual representation
of G based 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 G using 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 G keeping the vertex partitions separated
circle[=L] or convexhull[=L]: draw the graph G by setting the hull vertices from list
L V (assuming L = V by 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 xed
planar or plane: draw the planar graph G using a force-directed algorithm
plot3d: draw the connected graph G as if the spring option was enabled, but with vertex
positions in 3D instead of 2D
any unassigned identi er 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 speci ed. 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 speci ed, the algorithm rst checks if the graph G is 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 speci ed.
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
76
Visualizing graphs
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 speci ed, 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 xv is the vector
representing the position of the vertex v 2 V , the total force Fv applied to v is equal to
Fv =
X
w2V nfvg
¡
X
C K2
(xv ¡ xw) +
2
kxv ¡ xw k
w2N (v)
kxv ¡ xw k
(xv ¡ xw);
K
where N (v) is the set of neighbors of v and C, K are certain positive real constants (actually, K
may be any positive number, it aects 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 rst 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 signi cantly 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 re ecting symmetries 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
expensiveup to O(jV j7) when using the symmetry measure of Purchase [23], for examplethe
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).
7.1 Drawing graphs by using various methods
77
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
78
Visualizing graphs
> 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)
z
x
y
7.1.4. Drawing trees
When the tree[=r] option is speci ed and the input graph G is a tree (and r 2 V ), it is drawn using
a fast but simple node positioning algorithm inspired by the well-known algorithm of Walker [22],
using the rst 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 subtrees 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 re ection of a tree is the re ected
drawing of the original tree.
The algorithm implemented in Giac generally satis es 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- rst search and laying out
each level subsequently, starting from the deepest one and climbing up to the root node. In the
end, another depth- rst traversal is made, shifting the sub-trees horizontally to avoid intersections
between their edges. The algorithm runs in O(jV j) time and uses the minimum of horizontal space
to draw the tree with respect to the speci ed root node r.
For example, the following command line produces the drawing of a random tree on 100 nodes.
> draw_graph(random_tree(100))
7.1 Drawing graphs by using various methods
79
7.1.5. Drawing planar graphs
The algorithm implemented in Giac which draws planar graphs uses augmentation techniques
to extend the input graph G to a graph G 0, which is homeomorphic to some triconnected graph,
by adding temporary edges. The augmented graph G 0 is 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 xed somewhere
the boundary of a convex polygon. In addition, to produce a more exible 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 xed, 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 G is decomposed into
biconnected components called blocks using the depth- rst 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 B1 and B2, connected by an articulation
point (cut vertex). The temporary edge (shown in blue) is added to join B1 and B2 into 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 k and l such that 1 6 k < l ¡ 1 < n and either vk vl 2 E, in which case
the edge vk vl is 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¡1 are 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.
temp. edge
B1
chord
f
vl
vk
B2
Fig. 7.1. joining two blocks
f
Fig. 7.2. a chorded face
g
Fig. 7.3. two adjacent faces
This method of drawing planar graphs operates in O(jV j2) 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 dierent 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.
80
Visualizing graphs
> 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 attenedmaking the
two triangular faces invisibleif 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 in ating
themselves to become convex), causing them to merge eventually.
In the following example the input graph G is connected but not biconnected (it has two articulation points). It is obtained by removing a vertex from the Sierpi«ski triangle graph ST33. Note
that the syntax mode is set to Xcas in this example, so the rst 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 V is a set of vertices in G, uses the
following strategy. First, positions of the vertices from L are xed so that they form a regular
polygon on the unit circle. Other vertices, i.e. all vertices from V n L, are placed in origin. Then
an iterative force-directed algorithm [16], similar to Tutte's barycentric method, is applied to
obtain the nal 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 S42 is 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])
7.2 Custom vertex positions
81
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 L of positions to be
assigned to vertices in order of vertices(G). The positions may be complex numbers, lists of coordinates or points (geometrical objects created with the command point). set_vertex_positions
returns the copy G 0 of G with the given layout stored in it.
Any subsequent call to draw_graph with G 0 as an argument and without specifying the drawing
style will result in displaying vertices at the stored coordinates. However, if a drawing style is
speci ed, the stored layout is ignored (although it stays stored in G 0).
> 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 G by using the draw_graph command with
the additional argument P which should be an unassigned identi er. After the layout is obtained,
it will be stored to P as a list of positions (complex numbers for 2D drawings or points for 3D
drawings) for each vertex in order of vertices(G).
82
Visualizing graphs
This feature combines well with the set_vertex_positions command, as when one obtains the
desired drawing of the graph G by 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 G as 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 P contains 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 xed, 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 speci ed 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 v 2 V or a list
L V of vertices and optionally the new color (or a list of colors) for the selected vertices (the
default color is green). It returns a modi ed copy of G in which the speci ed vertices are colored
with the speci ed color.
> G:=graph("dodecahedron")
an undirected unweighted graph with 20 vertices and 30 edges
> L:=maximum_independent_set(G)
7.3 Highlighting parts of a graph
83
[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 e or a list of edges
L and optionally the new color (or a list of colors) for the selected edges (the default color is red).
It returns a modi ed copy of G in which the speci ed edges are colored with the speci ed 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 V or a
list [L1,L2,...,Lk] of such lists (each list represents the vertices of the corresponding trail) and
optionally a positive integer c or a list of positive integers [c1,c2,...,ck]. The command returns
the copy of G in which edges between consecutive vertices in L are highlighted with color c (by
default red) or the trail represented by Li is highlighted with color ci for i = 1; 2; :::; k.
Note that a trail can cross itself, which means that the elements of L are 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]))
84
Visualizing graphs
1
6
15
5
11
2
20
16
10
19
7
17
14
12
18
13
9
8
4
3
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 S of G
or a list of subgraphs of G and optionally the new colors for edges and vertices of the selected
subgraph(s), respectively. It returns a modi ed copy of G with the selected subgraph(s) colored
as speci ed.
> 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)
Bibliography
[1] Daniel Brélaz. New Methods to Color the Vertices of a Graph. Communications of the ACM, 22:251256, 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 344353. Springer-Verlag Berlin Heidelberg, 2002.
[3] Isabel M. Díaz and Paula Zabala. A Branch-and-Cut Algorithm for Graph Coloring. Discrete Applied Mathematics, 154:826847, 2006.
[4] Jack Edmonds. Paths, Trees, and Flowers. In Gessel I. and GC. Rota, editors, Classic Papers in Combinatorics,
pages 361379. Birkhäuser Boston, 2009. Modern Birkhäuser Classics.
[5] Shimon Even and Robert E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2:339344,
1976.
[6] T. M. J. Fruchterman and E. M. Reingold. Graph Drawing by Force-Directed Placement. Software: Practice
and Experience, 21:11291164, 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:3032, 1873.
[9] Andreas M. Hinz, Sandi Klavºar, and Sara S. Zemlji£. A survey and classi cation of Sierpi«ski-type graphs.
Discrete Applied Mathematics, 217:565600, 2017.
[10] John E. Hopcroft and Richard M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs.
SIAM Journal on Computing, 2:225231, 1973.
[11] Yifan Hu. E cient and High Quality Force-Directed Graph Drawing. Mathematica Journal, 10:3771, 2005.
[12] Yifan Hu and Jennifer Scott. A Multilevel Algorithm for Wavefront Reduction. SIAM Journal on Scienti c
Computing, 23:13521375, 2001.
[13] Arthur B. Kahn. Topological sorting of large networks. Communications of the ACM, 5:558562, 1962.
[14] Wendy Myrwold and Willian Kocay. Errors in graph embedding algorithms. Journal of Computer and System
Sciences, 77:430438, 2011.
[15] Patric R. J. Östergård. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics,
120:197207, 2002.
[16] Bor Plestenjak. An Algorithm for Drawing Planar Graphs. Software: Practice and Experience, 29:973984,
1999.
[17] Angelika Steger and Nicholas C. Wormald. Generating random regular graphs quickly. Combinatorics Probability and Computing, 8:377396, 1999.
[18] Robert E. Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1:146160,
1972.
[19] Robert E. Tarjan. Applications of path compression on balanced trees. Journal of the ACM, 26:690715, 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:2842, 2006.
[21] W. T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, s3-13:743767, 1963.
[22] John Q. Walker II. A nodepositioning algorithm for general trees. Software: Practice and Experience,
20:685705, 1990.
[23] E. Welch and S. Kobourov. Measuring Symmetry in Drawings of Graphs. Computer Graphics Forum,
36:341351, 2017.
[24] Douglas B. West. Introduction to Graph Theory. Pearson Education, 2002.
85
Command Index
antiprism_graph . . .
complete_binary_tree
complete_graph . . .
complete_kary_tree .
cycle_graph . . . . .
digraph . . . . . . . .
graph . . . . . . . . .
grid_graph . . . . . .
hypercube_graph . . .
interval_graph . . .
is_graphic_sequence
kneser_graph . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
14
13
14
12
10
. 9
18
16
15
15
15
lcf_graph . . . .
odd_graph . . . .
path_graph . . . .
petersen_graph .
prism_graph . . .
sequence_graph .
sierpinski_graph
star_graph . . . .
torus_grid_graph
trail . . . . . . .
web_graph . . . .
wheel_graph . . .
87
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
15
13
20
18
15
20
17
18
13
17
17
Source Exif Data:
File Type : PDF File Type Extension : pdf MIME Type : application/pdf PDF Version : 1.4 Linearized : No Page Count : 87 Title : Graph theory package for Giac/Xcas Creator : TeXmacs 1.99.6 Producer : TeXmacs 1.99.6 + Hummus 3.9EXIF Metadata provided by EXIF.tools