GraphPower - Maple Help

GraphTheory

 GraphPower
 construct graph power of a graph

 Calling Sequence GraphPower(G, k)

Parameters

 G - unweighted graph k - positive integer

Description

 • GraphPower returns the kth graph power of a given graph. This is a graph in which two vertices are connected if there exists a path of length at most k in the original graph.
 • The input graph G may be directed or undirected.
 • The algorithm adds powers of the adjacency matrix of G and removes any multiple edges.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $P≔\mathrm{PathGraph}\left(5\right)$
 ${P}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 5 vertices and 4 edge\left(s\right)}}$ (1)
 > $\mathrm{Edges}\left(P\right)$
 $\left\{\left\{{1}{,}{2}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{3}{,}{4}\right\}{,}\left\{{4}{,}{5}\right\}\right\}$ (2)
 > $\mathrm{DrawGraph}\left(P,\mathrm{style}=\mathrm{circle}\right)$
 > $\mathrm{P2}≔\mathrm{GraphPower}\left(P,2\right)$
 ${\mathrm{P2}}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 5 vertices and 7 edge\left(s\right)}}$ (3)
 > $\mathrm{Edges}\left(\mathrm{P2}\right)$
 $\left\{\left\{{1}{,}{2}\right\}{,}\left\{{1}{,}{3}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{2}{,}{4}\right\}{,}\left\{{3}{,}{4}\right\}{,}\left\{{3}{,}{5}\right\}{,}\left\{{4}{,}{5}\right\}\right\}$ (4)
 > $\mathrm{DrawGraph}\left(\mathrm{P2}\right)$
 > $\mathrm{P3}≔\mathrm{GraphPower}\left(P,3\right)$
 ${\mathrm{P3}}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 5 vertices and 9 edge\left(s\right)}}$ (5)
 > $\mathrm{Edges}\left(\mathrm{P3}\right)$
 $\left\{\left\{{1}{,}{2}\right\}{,}\left\{{1}{,}{3}\right\}{,}\left\{{1}{,}{4}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{2}{,}{4}\right\}{,}\left\{{2}{,}{5}\right\}{,}\left\{{3}{,}{4}\right\}{,}\left\{{3}{,}{5}\right\}{,}\left\{{4}{,}{5}\right\}\right\}$ (6)
 > $\mathrm{DrawGraph}\left(\mathrm{P3}\right)$