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

GraphTheory

 Diameter
 find the diameter of a graph

 Calling Sequence Diameter(G)

Parameters

 G - graph

Description

 • Diameter returns the maximum distance among all pairs of vertices in the graph G. If G is disconnected then the output is infinity.
 • For weighted graphs the edge weights are used to denote the distance accrued while traveling along each edge.  For unweighted graphs the length of each edge is assumed to be 1.
 • The strategy is to use the Floyd-Warshall all-pairs shortest path algorithm. See AllPairsDistance.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $P≔\mathrm{PetersenGraph}\left(\right)$
 ${P}{≔}{\mathrm{Graph 1: an undirected graph with 10 vertices and 15 edge\left(s\right)}}$ (1)
 > $\mathrm{Diameter}\left(P\right)$
 ${2}$ (2)
 > $C≔\mathrm{CycleGraph}\left(19\right)$
 ${C}{≔}{\mathrm{Graph 2: an undirected graph with 19 vertices and 19 edge\left(s\right)}}$ (3)
 > $\mathrm{Diameter}\left(C\right)$
 ${9}$ (4)
 > $G≔\mathrm{Graph}\left(\left\{\left[\left\{1,2\right\},0.2\right],\left[\left\{2,3\right\},0.3\right],\left[\left\{3,4\right\},0.4\right],\left[\left\{4,1\right\},1.1\right]\right\}\right)$
 ${G}{≔}{\mathrm{Graph 3: an undirected weighted graph with 4 vertices and 4 edge\left(s\right)}}$ (5)
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{Diameter}\left(G\right)$
 ${0.9}$ (6)

The distance between vertices 1 and 4 is maximal

 > $\mathrm{DijkstrasAlgorithm}\left(G,1,4\right)$
 $\left[\left[{1}{,}{2}{,}{3}{,}{4}\right]{,}{0.9}\right]$ (7)