Graph Theory - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

GraphTheory

A substantial effort was put into Graph Theory for Maple 2024, including new commands for graph computation and generation.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$

New commands

These commands are new for Maple 2024:

AllGraphs

The new AllGraphs command returns an iterator with which one can step through all graphs matching a particular set of criteria, such as vertex count or edge count. It is also possible to cause the Iterator to return only connected graphs or only graphs which are not isomorphic to a graph previously returned by this Iterator.

 >
 ${\mathrm{iterator}}{≔}\left[\right]$ (1.1.1)
 > $\mathrm{iterator}:-\mathrm{getNext}\left(\right)$
 ${\mathrm{Graph 1: an undirected graph with 3 vertices and 0 edge\left(s\right)}}$ (1.1.2)
 > $\mathrm{iterator}:-\mathrm{getNext}\left(\right)$
 ${\mathrm{Graph 2: an undirected graph with 3 vertices and 1 edge\left(s\right)}}$ (1.1.3)
 > $\mathrm{iterator}:-\mathrm{getNext}\left(\right)$
 ${\mathrm{Graph 3: an undirected graph with 3 vertices and 2 edge\left(s\right)}}$ (1.1.4)

Condensation

The new command Condensation computes the condensation of a given (directed) graph.

The condensation of a graph G is a graph C whose vertices correspond to the strongly connected components of G.  The condensation C will have an arc from u to v whenever there is an arc from the strongly connected component of G corresponding to u to the strongly connected component of G corresponding to v.

 >
 ${T}{≔}{\mathrm{Graph 4: a directed graph with 4 vertices and 5 arc\left(s\right)}}$ (1.2.1)
 >
 ${C}{≔}{\mathrm{Graph 5: a directed graph with 3 vertices and 2 arc\left(s\right)}}$ (1.2.2)
 >
 $\left[\begin{array}{cc}{\mathrm{PLOT}}{}\left({\mathrm{...}}\right)& {\mathrm{PLOT}}{}\left({\mathrm{...}}\right)\end{array}\right]$ (1.2.3)

FindAsteroidalTriple and IsAsteroidalTripleFree

The new command FindAsteriodalTriple searches for an asteroidal triple in the given graph.  The related new command IsAsteroidalTripleFree returns true when the given graph does not contain an asteroidal triple.

An asteroidal triple for a graph G is a triple $\left(u,v,w\right)$ of non-adjacent vertices of G such that for each pair from the triple, there exists a path between them that does not intersect the third vertex or any of its neighbors.

 >
 ${\mathrm{C6}}{≔}{\mathrm{Graph 6: an undirected graph with 6 vertices and 6 edge\left(s\right)}}$ (1.3.1)
 > $\mathrm{DrawGraph}\left(\mathrm{C6},\mathrm{size}=\left[200,200\right]\right)$
 > $\mathrm{FindAsteroidalTriple}\left(\mathrm{C6}\right)$
 $\left[{1}{,}{3}{,}{5}\right]$ (1.3.2)

IsArchimedeanGraph

The new command IsArchimedeanGraph tests whether a given graph is an Archimedean graph.

The Archimedean graphs are those graphs which form the skeletons of the Archimedean solids. The Archimedean solids comprise 13 convex polyhedra whose faces are regular polygons and whose vertices are all symmetric to each other, but which are not Platonic solids (polyhedra whose faces are identical).

 >
 ${\mathrm{true}}$ (1.4.1)

IsDominatingSet

The new command IsDominatingSet tests whether a set is a dominating set for a given graph.

A dominating set of a graph G is a subset S of the vertices of G, with the condition that every vertex in G must either be an element of S or the neighbor of an element of S.

 >
 ${\mathrm{P5}}{≔}{\mathrm{Graph 7: an undirected graph with 5 vertices and 4 edge\left(s\right)}}$ (1.5.1)
 >
 ${\mathrm{S3}}{≔}\left\{{1}{,}{3}{,}{5}\right\}$ (1.5.2)
 >
 ${\mathrm{true}}$ (1.5.3)

MinCut

The new MinCut command works per the Max-Flow Min-Cut Theorem and uses the flow output to compute a cut-set. The EdgeConnectivity and VertexConnectivity commands have been updated to use MinCut so that they can now also return cut-sets.

 >
 ${\mathrm{MG}}{≔}{\mathrm{Graph 8: an undirected graph with 7 vertices and 9 edge\left(s\right)}}$ (1.6.1)
 >
 ${\mathrm{mf}}{,}{\mathrm{flowM}}{≔}{2}{,}\left[{?}\right]$
 ${i}$ (1.6.2)

The MinCut command will call MaxFlow by default but can reuse the flow matrix if MaxFlow has been called already.

 >
 $\left\{\left\{{3}{,}{7}\right\}{,}\left\{{4}{,}{7}\right\}\right\}$ (1.6.3)
 > $\mathrm{EdgeConnectivity}\left(\mathrm{MG},\mathrm{output}=\mathrm{cutset}\right);$
 $\left\{\left\{{3}{,}{5}\right\}\right\}$ (1.6.4)
 >
 $\left\{{3}\right\}$ (1.6.5)

MoralGraph

The moral graph of a directed graph G is a graph M with the same vertices as G but with all directed edges made undirected, and with the property that whenever two directed edges in G share a destination vertex, then their source vertices are connected in M.

The new command MoralGraph constructs the moral graph given a directed graph.

 >
 ${\mathrm{DG}}{≔}{\mathrm{Graph 9: a directed graph with 7 vertices and 7 arc\left(s\right)}}$ (1.7.1)
 > $\mathrm{NumberOfEdges}\left(\mathrm{DG}\right)$
 ${7}$ (1.7.2)
 >
 ${\mathrm{MG}}{≔}{\mathrm{Graph 10: an undirected graph with 7 vertices and 9 edge\left(s\right)}}$ (1.7.3)
 > $\mathrm{NumberOfEdges}\left(\mathrm{MG}\right)$
 ${9}$ (1.7.4)
 > $\mathrm{SetVertexPositions}\left(\mathrm{MG},\mathrm{GetVertexPositions}\left(\mathrm{DG}\right)\right)$
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{DrawGraph}~\left(⟨\mathrm{DG}|\mathrm{MG}⟩\right)\right)$

RelationGraph

The RelationGraph command constructs a graph on a given vertex list in which an edge is present in the graph whenever a particular Boolean predicate on its two vertices is true.

 >
 ${\mathrm{RG}}{≔}{\mathrm{Graph 11: an undirected graph with 16 vertices and 79 edge\left(s\right)}}$ (1.8.1)
 > $\mathrm{DrawGraph}\left(\mathrm{RG}\right)$

In this example, the neighborhood of the element 5 will be all those vertices whose values are coprime with 5:

 >
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{6}{,}{7}{,}{8}{,}{9}{,}{11}{,}{12}{,}{13}{,}{14}{,}{16}\right]$ (1.8.2)

WienerIndex

The WienerIndex command computes the Wiener index on a given graph. The Wiener index of a graph is the sum of the lengths of the shortest paths between all pairs of vertices in the graph.

 >
 ${G}{≔}{\mathrm{Graph 12: an undirected graph with 20 vertices and 20 edge\left(s\right)}}$ (1.9.1)
 > $\mathrm{WienerIndex}\left(G\right)$
 ${40}$ (1.9.2)

New functionality for existing commands

Distance and ShortestPath

The Distance and ShortestPath commands now use the edge weights of a weighted matrix. They both have a new option ignoreweights to compute the distance or shortest path in the underlying unweighted graph.

 >
 ${\mathrm{W6}}{≔}{\mathrm{Graph 13: a directed weighted graph with 6 vertices and 6 arc\left(s\right)}}$ (2.1.1)
 >
 >
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}\right]$ (2.1.2)
 >
 ${5}$ (2.1.3)
 >
 $\left[{1}{,}{6}\right]$ (2.1.4)
 >
 ${1}$ (2.1.5)
 MaxFlow The MaxFlow command now works on all graphs.  It now treats an unweighted graph as a graph with all edge weights equal to 1, or to the edge multiplicity for multigraphs.

The SpecialGraphs subpackage now includes commands for all the Archimedean graphs, as well as the Möbius ladder graph and the Wagner graph.

Archimedean Graphs

The Archimedean graphs are those graphs which form the skeletons of the Archimedean solids.  The Archimedean solids comprise 13 convex polyhedra whose faces are regular polygons and whose vertices are all symmetric to each other, but which are not Platonic solids (polyhedra whose faces are identical). They were first enumerated by Archimedes.

The new command IsArchimedeanGraph tests whether a given graph is an Archimedean graph.

The following new commands generate each of the Archimedean graphs.

Archimedean solid

Degree

Vertices

Edges

Command

2-D

3-D

truncated tetrahedon

3

12

18

 >
 ${G}{≔}{\mathrm{Graph 14: an undirected graph with 12 vertices and 18 edge\left(s\right)}}$ (3.1.1)



 > $\mathrm{DrawPlanar}\left(G,\mathrm{showlabels}=\mathrm{false}\right)$
 >

cuboctahedron

4

12

24

 >
 ${\mathrm{letters}}{≔}\left[{"A"}{,}{"B"}{,}{"C"}{,}{"D"}{,}{"E"}{,}{"F"}{,}{"G"}{,}{"H"}{,}{"I"}{,}{"J"}{,}{"K"}{,}{"L"}\right]$ (3.1.2)
 >
 ${G}{≔}{\mathrm{Graph 15: an undirected graph with 12 vertices and 24 edge\left(s\right)}}$ (3.1.3)
 >
 >

truncated cube

3

24

36

 >
 ${G}{≔}{\mathrm{Graph 16: an undirected graph with 24 vertices and 36 edge\left(s\right)}}$ (3.1.4)
 > $\mathrm{DrawPlanar}\left(G,\mathrm{showlabels}=\mathrm{false}\right)$
 >

truncated octahedron

3

24

36

 >
 ${G}{≔}{\mathrm{Graph 17: an undirected graph with 24 vertices and 36 edge\left(s\right)}}$ (3.1.5)
 > $\mathrm{DrawPlanar}\left(G,\mathrm{showlabels}=\mathrm{false}\right)$
 >

small rhombicuboctahedron

4

24

48

 >
 ${G}{≔}{\mathrm{Graph 18: an undirected graph with 24 vertices and 48 edge\left(s\right)}}$ (3.1.6)
 > $\mathrm{DrawPlanar}\left(G,\mathrm{showlabels}=\mathrm{false}\right)$
 >

great rhombicuboctahedron
(also called truncated cuboctahedron)

3

48

72

 >
 ${G}{≔}{\mathrm{Graph 19: an undirected graph with 48 vertices and 72 edge\left(s\right)}}$ (3.1.7)
 > $\mathrm{DrawPlanar}\left(G,\mathrm{showlabels}=\mathrm{false}\right)$
 >

snub cube

5

24

60

 >
 ${G}{≔}{\mathrm{Graph 20: an undirected graph with 24 vertices and 60 edge\left(s\right)}}$ (3.1.8)
 > $\mathrm{DrawPlanar}\left(G,\mathrm{showlabels}=\mathrm{false}\right)$
 >

Icosidodecahedron

4

30

60

 >
 ${G}{≔}{\mathrm{Graph 21: an undirected graph with 30 vertices and 60 edge\left(s\right)}}$ (3.1.9)
 > $\mathrm{DrawPlanar}\left(G,\mathrm{showlabels}=\mathrm{false}\right)$
 >

truncated dodecahedron

3

60

90

 >
 ${G}{≔}{\mathrm{Graph 22: an undirected graph with 60 vertices and 90 edge\left(s\right)}}$ (3.1.10)
 > $\mathrm{DrawPlanar}\left(G,\mathrm{showlabels}=\mathrm{false}\right)$
 >

truncated icosahedron

3

60

90

 >
 ${G}{≔}{\mathrm{Graph 23: an undirected graph with 60 vertices and 90 edge\left(s\right)}}$ (3.1.11)
 > $\mathrm{DrawPlanar}\left(G,\mathrm{showlabels}=\mathrm{false}\right)$
 >

small rhombicosidodecahedron

4

60

120

 >
 ${G}{≔}{\mathrm{Graph 24: an undirected graph with 60 vertices and 120 edge\left(s\right)}}$ (3.1.12)
 > $\mathrm{DrawPlanar}\left(G,\mathrm{showlabels}=\mathrm{false}\right)$
 >

great rhombicosidodecahedron
(also called truncated icosidodecahedron)

3

120

180

 >
 ${G}{≔}{\mathrm{Graph 25: an undirected graph with 120 vertices and 180 edge\left(s\right)}}$ (3.1.13)
 >
 >

snub dodecahedron

5

60

150

 >
 ${G}{≔}{\mathrm{Graph 26: an undirected graph with 60 vertices and 150 edge\left(s\right)}}$ (3.1.14)
 >
 >

Möbius ladder graph and Wagner graph

The Möbius ladder graph on  vertices may be understood visually as the ladder graph on the same vertices, with the addition of two edges: one connecting the left-hand side of the "op rung to the right-hand side of the bottom rung, and one connecting the right-hand side of the top rung to the left-hand side of the bottom rung.

 >
 ${\mathrm{ML3}}{≔}{\mathrm{Graph 27: an undirected graph with 6 vertices and 9 edge\left(s\right)}}$ (3.2.1)
 >

The Wagner graph is a 3-regular graph which is a particular instance of an Möbius ladder graph on 8 vertices.

 >
 ${\mathrm{WG}}{≔}{\mathrm{Graph 28: an undirected graph with 8 vertices and 12 edge\left(s\right)}}$ (3.2.2)
 >