Example Worksheet - Maple Help

All Products Maple MapleSim

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : Example Worksheet

The GraphTheory Package

This worksheet demonstrates some features of the GraphTheory package. It is presented in a tutorial format.

>	$restart &colon;$ $with (GraphTheory) &colon;$

Creating Graphs

The main command for creating an undirected graph is the Graph command. For a directed graph the main command is the Digraph command. For both commands, you may specify the vertices in an ordered list. The vertices may be integers, symbols, or strings. By using strings, you can affix any text that you want for the vertex labels.
The DrawGraph command with its size option is used to display a small plot of the each of the example graphs. More detail on DrawGraph will be given in the "Drawing Graphs" section below.

>	$G__1 ≔ Graph ([a, b, c]) &semi; DrawGraph (G__1, size = [200, 200])$

$G__1 ≔ Graph 1: an undirected graph with 3 vertices and 0 edge(s)$

>	$Vertices (G__1)$

$[a, b, c]$

(1.1)

>	$H__1 ≔ Digraph ([1, 2, 3]) &semi; DrawGraph (H__1, size = [200, 200])$

$H__1 ≔ Graph 2: a directed graph with 3 vertices and 0 arc(s)$

>	$Vertices (H__1)$

$[1, 2, 3]$

(1.2)

>	$T__1 ≔ Graph ([0:0, 0:1, 1:0, 1:1])$

$T__1 ≔ Graph 3: an undirected graph with 4 vertices and 0 edge(s)$

(1.3)

>	$Vertices (T__1)$

$[0:0, 0:1, 1:0, 1:1]$

(1.4)

You may specify the numberof vertices, $n$ , in which case they are labeled 1,2,..., $n$ .

>	$G__2 ≔ Graph (4) &semi; DrawGraph (G__2, size = [200, 200])$

$G__2 ≔ Graph 4: an undirected graph with 4 vertices and 0 edge(s)$

>	$Vertices (G__2)$

$[1, 2, 3, 4]$

(1.5)

Inserting edges

You may insert edges into an undirected graph one at a time using the AddEdge command. Each edge should be input as a set of two vertices.

You can also specify more than one edge at a time in a set.

>	$G__3 ≔ Graph (4)$

$G__3 ≔ Graph 5: an undirected graph with 4 vertices and 0 edge(s)$

(1.1.1)

>	$AddEdge (G__3, \{1, 2\}) &semi;$ $AddEdge (G__3, \{\{2, 3\}, \{3, 4\}\})$

$Graph 5: an undirected graph with 4 vertices and 1 edge(s)$

$Graph 5: an undirected graph with 4 vertices and 3 edge(s)$

(1.1.2)

>	$DrawGraph (G__3, size = [200, 200])$

>	$Edges (G__3)$

$\{\{1, 2\}, \{2, 3\}, \{3, 4\}\}$

(1.1.3)

For a directed graph, use the AddArc command and input the edges as lists of vertices.

>	$H__2 ≔ Digraph (4)$

$H__2 ≔ Graph 6: a directed graph with 4 vertices and 0 arc(s)$

(1.1.4)

>	$AddArc (H__2, \{[1, 2], [2, 3], [3, 4]\})$

$Graph 6: a directed graph with 4 vertices and 3 arc(s)$

(1.1.5)

>	$DrawGraph (H__2, size = [200, 200])$

>	$Edges (H__2)$

$\{[1, 2], [2, 3], [3, 4]\}$

(1.1.6)

Using a set of edges

You may create an undirected graph with given edges by passing them in as a set where each edge is itself a set of two vertices. If the vertices are not specified explicitly, the vertices will be taken to be all vertices appearing in the set of edges. Thus, the previous graph G, which is a simple path, can be created by

>	$G__3 ≔ Graph (\{\{1, 2\}, \{2, 3\}, \{3, 4\}\})$

$G__3 ≔ Graph 7: an undirected graph with 4 vertices and 3 edge(s)$

(1.2.1)

>	$DrawGraph (G__3, size = [200, 200])$

>	$Vertices (G__3)$

$[1, 2, 3, 4]$

(1.2.2)

>	$AdjacencyMatrix (G__3) &semi;$

$[\begin{array}{c} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}]$

(1.2.3)

Similarly, the above previous directed graph H, which is a directed path, can be created by

>	$H__2 ≔ Digraph (\{[1, 2], [2, 3], [3, 4]\})$

$H__2 ≔ Graph 8: a directed graph with 4 vertices and 3 arc(s)$

(1.2.4)

>	$DrawGraph (H__2, size = [200, 200])$

>	$AdjacencyMatrix (H__2)$

$[\begin{array}{c} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array}]$

(1.2.5)

Using an adjacency matrix

The above graphs G and H can also be created from the adjacency matrix. If the vertices are not explicitly given in a list, then the vertex labels are taken to be integers 1,2,...,n where n is the dimension of the adjacency matrix.

>	$A__3 ≔ [\begin{array}{r} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}]$

$A__3 ≔ [\begin{array}{c} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}]$

(1.3.1)

>	$G__3 ≔ Graph (A__3)$

$G__3 ≔ Graph 9: an undirected graph with 4 vertices and 3 edge(s)$

(1.3.2)

>	$DrawGraph (G__3, size = [200, 200])$

>	$Vertices (G__3)$

$[1, 2, 3, 4]$

(1.3.3)

>	$Edges (G__3)$

$\{\{1, 2\}, \{2, 3\}, \{3, 4\}\}$

(1.3.4)

>	$B__2 ≔ [\begin{array}{r} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array}]$

$B__2 ≔ [\begin{array}{c} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array}]$

(1.3.5)

>	$H__2 ≔ Digraph ([a, b, c, d], B__2)$

$H__2 ≔ Graph 10: a directed graph with 4 vertices and 3 arc(s)$

(1.3.6)

>	$DrawGraph (H__2, size = [200, 200])$

>	$Vertices (H__2)$

$[a, b, c, d]$

(1.3.7)

>	$Edges (H__2) &semi;$

$\{[a, b], [b, c], [c, d]\}$

(1.3.8)

Using a list of neighbors

If G has n vertices, the input is a list of n lists of vertices.

>	$L__3 ≔ [[2], [1, 3], [2, 4], [3]]$

$L__3 ≔ [[2], [1, 3], [2, 4], [3]]$

(1.4.1)

>	$G__3 ≔ Graph (L__3)$

$G__3 ≔ Graph 11: an undirected graph with 4 vertices and 3 edge(s)$

(1.4.2)

>	$DrawGraph (G__3, size = [200, 200])$

>	$Edges (G__3)$

$\{\{1, 2\}, \{2, 3\}, \{3, 4\}\}$

(1.4.3)

>	$Neighbors (G__3)$

$[[2], [1, 3], [2, 4], [3]]$

(1.4.4)

For a directed graph, the list of neighbors need not be symmetric. Here is a directed cycle, i.e., the directed edges 1 to 2, 2 to 3, 3 to 4 and 4 to 1. This list corresponds to the list of "departures" of the graph.

>	$L__2 ≔ [[2], [3], [4], [1]]$

$L__2 ≔ [[2], [3], [4], [1]]$

(1.4.5)

>	$H__2 ≔ Digraph (L__2)$

$H__2 ≔ Graph 12: a directed graph with 4 vertices and 4 arc(s)$

(1.4.6)

>	$DrawGraph (H__2, size = [200, 200])$

>	$Neighbors (H__2)$

$[[2, 4], [1, 3], [2, 4], [1, 3]]$

(1.4.7)

>	$Arrivals (H__2)$

$[[4], [1], [2], [3]]$

(1.4.8)

>	$Departures (H__2)$

$[[2], [3], [4], [1]]$

(1.4.9)

Using trails

This is a convenient shorthand. The trail 1,2,3,4 represents the edges 1 to 2 to 3 to 4.

>	$T__4 ≔ Trail (1, 2, 3, 4, 1)$

$T__4 ≔ Trail (1, 2, 3, 4, 1)$

(1.5.1)

>	$G__4 ≔ Graph (T__4)$

$G__4 ≔ Graph 13: an undirected graph with 4 vertices and 4 edge(s)$

(1.5.2)

>	$DrawGraph (G__4, size = [200, 200])$

>	$Edges (G__4)$

$\{\{1, 2\}, \{1, 4\}, \{2, 3\}, \{3, 4\}\}$

(1.5.3)

>	$H__3 ≔ Digraph (Trail (a, b, c, d, c, b, a))$

$H__3 ≔ Graph 14: a directed graph with 4 vertices and 6 arc(s)$

(1.5.4)

>	$DrawGraph (H__3, size = [200, 200])$

>	$Edges (H__3)$

$\{[a, b], [b, a], [b, c], [c, b], [c, d], [d, c]\}$

(1.5.5)

Weighted edges

To create a weighted graph, use the weighted option.

>	$G__5 ≔ Graph (5, weighted)$

$G__5 ≔ Graph 15: an undirected weighted graph with 5 vertices and 0 edge(s)$

(1.6.1)

An undirected edge (u,v) of weight w is input in the form [{u,v},w].
For a directed edge from u to v with weight w, use [[u,v],w] instead.

>	$AddEdge (G__5, [\{1, 2\}, 2.3]) &semi;$ $AddEdge (G__5, [\{3, 4\}, 4.5])$

$Graph 15: an undirected weighted graph with 5 vertices and 1 edge(s)$

$Graph 15: an undirected weighted graph with 5 vertices and 2 edge(s)$

(1.6.2)

>	$DrawGraph (G__5, size = [300, 300])$

>	$AdjacencyMatrix (G__5)$

$[\begin{array}{c} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}]$

(1.6.3)

>	$WeightMatrix (G__5)$

$[\begin{array}{c} 0 & 2.3 & 0 & 0 & 0 \\ 2.3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4.5 & 0 \\ 0 & 0 & 4.5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}]$

(1.6.4)

The same graph can be created directly with

>	$G__6 ≔ Graph (5, \{[\{1, 2\}, 2.3], [\{3, 4\}, 4.5]\})$

$G__6 ≔ Graph 16: an undirected weighted graph with 5 vertices and 2 edge(s)$

(1.6.5)

An edge weight can be 0.

>	$AddEdge (G__6, [\{2, 3\}, 0.0])$

$Graph 16: an undirected weighted graph with 5 vertices and 3 edge(s)$

(1.6.6)

>	$DrawGraph (G__6, size = [200, 200])$

>	$Edges (G__6)$

$\{\{1, 2\}, \{2, 3\}, \{3, 4\}\}$

(1.6.7)

>	$AdjacencyMatrix (G__6)$

$[\begin{array}{c} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}]$

(1.6.8)

>	$WeightMatrix (G__6)$

$[\begin{array}{c} 0 & 2.3 & 0 & 0 & 0 \\ 2.3 & 0 & 0. & 0 & 0 \\ 0 & 0. & 0 & 4.5 & 0 \\ 0 & 0 & 4.5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}]$

(1.6.9)

Paths, cycles, and complete graphs

Paths and cycles can be created by using a trail. There are also two primitives for creating these because they are heavily used. There is also a primitive for creating complete graphs.

>	$P__1 ≔ PathGraph (4)$

$P__1 ≔ Graph 17: an undirected graph with 4 vertices and 3 edge(s)$

(1.7.1)

>	$DrawGraph (P__1, size = [200, 200])$

>	$Edges (P__1)$

$\{\{1, 2\}, \{2, 3\}, \{3, 4\}\}$

(1.7.2)

>	$C__1 ≔ CycleGraph (4)$

$C__1 ≔ Graph 18: an undirected graph with 4 vertices and 4 edge(s)$

(1.7.3)

>	$DrawGraph (C__1, size = [200, 200])$

>	$Edges (C__1)$

$\{\{1, 2\}, \{1, 4\}, \{2, 3\}, \{3, 4\}\}$

(1.7.4)

>	$K__4 ≔ CompleteGraph (4)$

$K__4 ≔ Graph 19: an undirected graph with 4 vertices and 6 edge(s)$

(1.7.5)

>	$DrawGraph (K__4, size = [200, 200])$

>	$Edges (K__4)$

$\{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}\}$

(1.7.6)

>	$IsPlanar (K__4)$

$true$

(1.7.7)

>	$K__3,3 ≔ CompleteGraph (3, 3)$

$K__3,3 ≔ Graph 20: an undirected graph with 6 vertices and 9 edge(s)$

(1.7.8)

>	$DrawGraph (K__3,3, size = [200, 200])$

>	$IsPlanar (K__3,3)$

$false$

(1.7.9)

Drawing Graphs

Here we just show some examples which illustrate the main options.
Further examples are given under the section "Special Graphs".

>	$G__10 ≔ Graph (9, \{\{1, 2\}, \{2, 3\}, \{3, 1\}, \{6, 7\}, \{7, 8\}\})$

$G__10 ≔ Graph 21: an undirected graph with 9 vertices and 5 edge(s)$

(2.1)

>	$DrawGraph (G__10)$

>	$H__7 ≔ Digraph (5, \{[1, 2], [2, 3], [3, 4], [2, 5]\})$

$H__7 ≔ Graph 22: a directed graph with 5 vertices and 4 arc(s)$

(2.2)

>	$DrawGraph (H__7, size = [300, 300])$

>	$DrawGraph (H__7, layout = circle)$

If you dislike the placement of the vertices, you can specify them as follows.

>	$SetVertexPositions (H__7, [[0, 0], [0.5, 0], [1.0, 0], [1.5, 0], [0.5, 1]])$

>	$DrawGraph (H__7)$

Or you can use the interactive layout method to set them interactively (click and drag the vertices on the plot below to customize the layout)

>	$DrawGraph (H__7, layout = interactive, layoutopts = [initial = tree])$

>	$GetVertexPositions (H__7)$

$[[0.0250000000, 0.0250000000], [0.0250000000, 0.9750000000], [0.5, 0.0250000000], [0.9750000000, 0.9750000000], [0.9750000000, 0.0250000000]]$

(2.3)

>	$PG ≔ SpecialGraphs :- PetersenGraph ()$

$PG ≔ Graph 23: an undirected graph with 10 vertices and 15 edge(s)$

(2.4)

The Petersen graph is very well known in graph theory. It is a non-planar graph. This is one of the standard drawings.

>	$DrawGraph (PG)$

The placement of the vertices is stored in the graph data structure.

>	$GetVertexPositions (PG)$

$[[0., 1.], [0.9510565163, 0.3090169944], [0.5877852522, −0.8090169944], [−0.5877852527, −0.8090169941], [−0.9510565163, 0.3090169944], [0., 0.6], [0.3526711513, −0.4854101966], [−0.5706339098, 0.1854101966], [0.5706339098, 0.1854101966], [−0.3526711516, −0.4854101965]]$

(2.5)

The "spring" method for drawing graphs will find other "symmetric" drawings of the Petersen graph. Try executing this a few times.

>	$DrawGraph (PG, layout = spring, redraw)$

The spring method works in 3-D

>	$DrawGraph (PG, layout = spring, dimension = 3)$

The spring method will work for moderately large graphs (graphs up to 1000 vertices).

>	$SB ≔ SpecialGraphs :- SoccerBallGraph ()$

$SB ≔ Graph 24: an undirected graph with 60 vertices and 90 edge(s)$

(2.6)

>	$DrawGraph (SB, layout = spring)$

For large weighted graphs the edge weights and edge labels may "clutter" the graph. You can turn these off.

>	$G__11 ≔ Graph (\{[\{a, b\}, 2], [\{b, c\}, 3], [\{c, d\}, 4], [\{d, b\}, 5]\})$

$G__11 ≔ Graph 25: an undirected weighted graph with 4 vertices and 4 edge(s)$

(2.7)

>	$DrawGraph (G__11)$

>	$DrawGraph (G__11, showweights = false)$

>	$DrawGraph (G__11, showlabels = false)$

	Exporting and Importing Graphs
	The commands ExportGraph and ImportGraph allow you to output one or more graphs to a file or read graphs from a file. Supported formats include `dimacs`, `dimacs_relaxed`, `combinatorica`, `edges`, `metapost`, `dot`, `graphml`, `gxl`, `leda`, `pajek`, `tgf`, `sparse6`, and `graph6`.

Graph Properties

There are lots of graph commands. Here we illustrate basic commands and how to accomplish various tasks.

Undirected graphs

>	$G__12 ≔ Graph (\{\{1, 2\}, \{2, 3\}, \{3, 1\}, \{3, 4\}, \{4, 5\}, \{5, 6\}\})$

$G__12 ≔ Graph 26: an undirected graph with 6 vertices and 6 edge(s)$

(4.1.1)

>	$DrawGraph (G__12)$

>	$IsConnected (G__12)$

$true$

(4.1.2)

>	$ConnectedComponents (G__12)$

$[[1, 2, 3, 4, 5, 6]]$

(4.1.3)

>	$IsBiconnected (G__12)$

$false$

(4.1.4)

>	$BiconnectedComponents (G__12)$

$[[5, 6], [4, 5], [3, 4], [1, 2, 3]]$

(4.1.5)

>	$AdjacencyMatrix (G__12)$

$[\begin{array}{c} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{array}]$

(4.1.6)

>	$Distance (G__12, 1, 6)$

$4$

(4.1.7)

>	$D__12 ≔ AllPairsDistance (G__12) &semi; D__12 [1, 6]$

$D__12 ≔ [\begin{array}{c} 0 & 1 & 1 & 2 & 3 & 4 \\ 1 & 0 & 1 & 2 & 3 & 4 \\ 1 & 1 & 0 & 1 & 2 & 3 \\ 2 & 2 & 1 & 0 & 1 & 2 \\ 3 & 3 & 2 & 1 & 0 & 1 \\ 4 & 4 & 3 & 2 & 1 & 0 \end{array}]$

$4$

(4.1.8)

>	$ArticulationPoints (G__12)$

$[3, 4, 5]$

(4.1.9)

>	$H__8 ≔ DeleteVertex (G__12, 3)$

$H__8 ≔ Graph 27: an undirected graph with 5 vertices and 3 edge(s)$

(4.1.10)

>	$IsConnected (H__8)$

$false$

(4.1.11)

>	$ConnectedComponents (H__8)$

$[[1, 2], [4, 5, 6]]$

(4.1.12)

>	$DrawGraph (H__8)$

>	$H__9 ≔ InducedSubgraph (G__12, [3, 4, 5])$

$H__9 ≔ Graph 28: an undirected graph with 3 vertices and 2 edge(s)$

(4.1.13)

>	$Vertices (H__9)$

$[3, 4, 5]$

(4.1.14)

>	$PG ≔ SpecialGraphs [PetersenGraph] ()$

$PG ≔ Graph 29: an undirected graph with 10 vertices and 15 edge(s)$

(4.1.15)

>	$DrawGraph (PG)$

>	$IsRegular (PG)$

$true$

(4.1.16)

>	$DegreeSequence (PG)$

$[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]$

(4.1.17)

>	$CliqueNumber (PG)$

$2$

(4.1.18)

>	$IsPlanar (PG)$

$false$

(4.1.19)

>	$IsHamiltonian (PG)$

$false$

(4.1.20)

>	$Girth (PG)$

$5$

(4.1.21)

>	$ChromaticNumber (PG)$

$3$

(4.1.22)

>	$OG ≔ SpecialGraphs :- OctahedronGraph ()$

$OG ≔ Graph 30: an undirected graph with 6 vertices and 12 edge(s)$

(4.1.23)

>	$IsEulerian (OG,' ogtrail')$

$true$

(4.1.24)

$ogtrail$

$Trail (1, 3, 2, 4, 1, 5, 2, 6, 3, 5, 4, 6, 1)$

(4.1.25)

Directed graphs

>	$M__1 ≔ Digraph (\{[1, 2], [2, 1], [1, 3], [2, 4], [2, 5], [4, 5], [5, 4]\})$

$M__1 ≔ Graph 31: a directed graph with 5 vertices and 7 arc(s)$

(4.2.1)

>	$DrawGraph (M__1, layout = spring)$

>	$IsConnected (M__1)$

$true$

(4.2.2)

>	$IsAcyclic (M__1)$

$false$

(4.2.3)

>	$IsStronglyConnected (M__1)$

$false$

(4.2.4)

>	$StronglyConnectedComponents (M__1)$

$[[3], [4, 5], [1, 2]]$

(4.2.5)

>	$AdjacencyMatrix (M__1)$

$[\begin{array}{c} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array}]$

(4.2.6)

>	$AllPairsDistance (M__1)$

$[\begin{array}{c} 0 & 1 & 1 & 2 & 2 \\ 1 & 0 & 2 & 1 & 1 \\ \infty & \infty & 0 & \infty & \infty \\ \infty & \infty & \infty & 0 & 1 \\ \infty & \infty & \infty & 1 & 0 \end{array}]$

(4.2.7)

Graph Attributes

You may attach arbitrary information to the graph as a whole, each vertex of the graph, and each edge of the graph. This is done using the attribute commands {Get/Set/List/Discard}{Graph/Vertex/Edge}Attribute(s).

>	$G__13 ≔ Graph (\{\{1, 2\}, \{2, 3\}, \{3, 4\}\})$

$G__13 ≔ Graph 32: an undirected graph with 4 vertices and 3 edge(s)$

(5.1)

>	$SetVertexAttribute (G__13, 2, friends = [1, 3])$

>	$ListVertexAttributes (G__13, 2)$

$[friends]$

(5.2)

>	$GetVertexAttribute (G__13, 2, friends)$

$[1, 3]$

(5.3)

>	$DiscardVertexAttribute (G__13, 2, friends)$

>	$ListVertexAttributes (G__13, 2)$

$[]$

(5.4)

>	$GetVertexAttribute (G__13, 2, friends)$

$FAIL$

(5.5)

Special Graphs and Random Graphs

The two packages SpecialGraphs and RandomGraphs must be loaded separately.

>	$with (SpecialGraphs) &colon;$

>	$PR ≔ PrismGraph (6)$

$PR ≔ Graph 33: an undirected graph with 12 vertices and 18 edge(s)$

(6.1)

>	$DrawGraph (PR)$

>	$with (RandomGraphs) &colon;$

>	$T__10 ≔ RandomTree (10)$

$T__10 ≔ Graph 34: an undirected graph with 10 vertices and 9 edge(s)$

(6.2)

>	$DrawGraph (T__10)$

As an example, we assign random integer edge weights to the prism graph G and run Kruskal's algorithm to compute the minimal spanning tree and highlight the graph with the minimal spanning tree.

>	$H__9 ≔ AssignEdgeWeights (PR, 1 .. 10)$

$H__9 ≔ Graph 35: an undirected weighted graph with 12 vertices and 18 edge(s)$

(6.3)

>	$DrawGraph (H__9)$

>	$T__9 ≔ MinimalSpanningTree (H__9)$

$T__9 ≔ Graph 36: an undirected weighted graph with 12 vertices and 11 edge(s)$

(6.4)

>	$HighlightEdges (H__9, Edges (T__9), stylesheet = [color = DodgerBlue, thickness = 3])$

>	$DrawGraph (H__9)$

As an example of a directed graph, we generate a weighted network on 10 vertices and compute the max flow through the network.

>	$N__1 ≔ RandomNetwork (10, 0.4, 0.2,' acyclic')$

$N__1 ≔ Graph 37: a directed graph with 10 vertices and 18 arc(s)$

(6.5)

>	$N__2 ≔ AssignEdgeWeights (N__1, 1 .. 10)$

$N__2 ≔ Graph 38: a directed weighted graph with 10 vertices and 18 arc(s)$

(6.6)

>	$DrawNetwork (N__2)$

>	$(mf, F) ≔ MaxFlow (N__2, 1, 10)$

$mf, F ≔ 4, [\begin{array}{c} 0 & 4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}]$

(6.7)

>	$N__3 ≔ MakeWeighted (N__1, F)$

$N__3 ≔ Graph 39: a directed weighted graph with 10 vertices and 18 arc(s)$

(6.8)

>	$DrawNetwork (N__3)$

Highlighting Vertices and Edges

>	$PG ≔ SpecialGraphs :- PetersenGraph ()$

$PG ≔ Graph 40: an undirected graph with 10 vertices and 15 edge(s)$

(7.1)

>	$IsVertexColorable (PG, 3,' colors')$

$true$

(7.2)

$colors$

$[[2, 5, 7, 10], [4, 6, 9], [1, 3, 8]]$

(7.3)

$HighlightVertex (PG, colors [1], stylesheet = [color = Blue, fontstyle = bold, shape = square, padding = 3]) &semi;$ $HighlightVertex (PG, colors [2], stylesheet = [color = Yellow, fontstyle = italic, shape = pentagon]) &semi; HighlightVertex (PG, colors [3], stylesheet = [color = Green, fontstyle = bold, shape = hexagon])$

>	$DrawGraph (PG)$

>	$DG ≔ SpecialGraphs :- DodecahedronGraph ()$

$DG ≔ Graph 41: an undirected graph with 20 vertices and 30 edge(s)$

(7.4)

>	$DrawGraph (DG)$

>	$IsHamiltonian (DG,' cycle')$

$true$

(7.5)

$cycle$

$[1, 2, 3, 4, 5, 10, 14, 9, 13, 8, 12, 7, 11, 16, 17, 18, 19, 20, 15, 6, 1]$

(7.6)

>	$HighlightTrail (DG, cycle, stylesheet = [color = Red, thickness = 2])$

>	$DrawGraph (DG)$

Return to Index for Example Worksheets

Download Help Document

Maple

Maple Add-Ons

MapleSim

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim

Maple

Powerful math software that is easy to use

Maple Add-Ons

MapleSim

Advanced System Level Modeling

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim