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

GraphTheory

 IsReachable
 determine if there is a path between two vertices

 Calling Sequence IsReachable(G, u, v)

Parameters

 G - graph u, v - vertices of the graph

Description

 • IsReachable(G, u, v) returns a true when the vertex v is reachable from u in the graph G.
 • To produce an actual path (or directed path when G is directed) from u to v, use BellmanFordAlgorithm, DijkstrasAlgorithm, or ShortestPath.
 • To find all vertices reachable from u, use Reachable.

Definition

 • If G is an undirected graph, a vertex w is said to be reachable from a vertex v if there exists a path in G between v and w. This is true if and only if they are in the same connected component.
 • If G is a directed graph, a vertex w is said to be reachable from a vertex v if there exists a directed path in G from v to w.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{C6}≔\mathrm{CycleGraph}\left(6\right)$
 ${\mathrm{C6}}{≔}{\mathrm{Graph 1: an undirected graph with 6 vertices and 6 edge\left(s\right)}}$ (1)
 > $\mathrm{IsReachable}\left(\mathrm{C6},1,5\right)$
 ${\mathrm{true}}$ (2)
 > $\mathrm{ShortestPath}\left(\mathrm{C6},1,5\right)$
 $\left[{1}{,}{6}{,}{5}\right]$ (3)

With the following example we see that the reachability relation is not symmetric for directed graphs.

 > $\mathrm{DP4}≔\mathrm{Graph}\left(\left["A","B","C","D"\right],\left\{\left["A","B"\right],\left["B","C"\right],\left["C","D"\right]\right\}\right)$
 ${\mathrm{DP4}}{≔}{\mathrm{Graph 2: a directed graph with 4 vertices and 3 arc\left(s\right)}}$ (4)
 > $\mathrm{IsReachable}\left(\mathrm{DP4},"A","D"\right)$
 ${\mathrm{true}}$ (5)
 > $\mathrm{ShortestPath}\left(\mathrm{DP4},"A","D"\right)$
 $\left[{"A"}{,}{"B"}{,}{"C"}{,}{"D"}\right]$ (6)
 > $\mathrm{IsReachable}\left(\mathrm{DP4},"D","A"\right)$
 ${\mathrm{false}}$ (7)

Compatibility

 • The GraphTheory[IsReachable] command was introduced in Maple 2018.
 • For more information on Maple 2018 changes, see Updates in Maple 2018.