GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/GraphPower

GraphTheory

  

GraphPower

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

GraphPower(G, k)

Parameters

G

-

unweighted graph

k

-

positive integer

Description

• 

GraphPower returns the kth power graph of a given graph which may be directed or undirected. In the kth power graph, two vertices are connected if there exists a path of length at most k in the original graph.

• 

The algorithm adds powers the adjacency matrix of G and removes any multiple edges.

Examples

withGraphTheory:

PPathGraph5

PGraph 1: an undirected unweighted graph with 5 vertices and 4 edge(s)

(1)

EdgesP

1,2,2,3,3,4,4,5

(2)

DrawGraphP,style=circle

P2GraphPowerP,2

P2Graph 2: an undirected unweighted graph with 5 vertices and 7 edge(s)

(3)

EdgesP2

1,2,1,3,2,3,2,4,3,4,3,5,4,5

(4)

DrawGraphP2

P3GraphPowerP,3

P3Graph 3: an undirected unweighted graph with 5 vertices and 9 edge(s)

(5)

EdgesP3

1,2,1,3,1,4,2,3,2,4,2,5,3,4,3,5,4,5

(6)

DrawGraphP3

See Also

AdjacencyMatrix

Diameter

ShortestPath