 GraphTheory - Maple Programming Help

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

GraphTheory

 IsArborescence
 test if a graph is an arborescence
 IsAntiArborescence
 test if a graph is an anti-arborescence

 Calling Sequence IsArborescence(G,opts) IsAntiArborescence(G,opts)

Parameters

 G - a directed graph opts - : (optional) root=true or root=false

Options

 • root : keyword option of the form root=true or root=false. This specifies whether the root vertex should be returned when the check is positive. The default is false.

Description

 • The IsArborescence function returns true if the input graph is an arborescence, and false otherwise.
 • The IsAntiArborescence function returns true if the input graph is an anti-arborescence, and false otherwise.

Details

 • A directed graph G is an arborescence if there is a single vertex u called the root such that for any other vertex v, there is exactly one path from u to v.
 • A directed graph G is an anti-arborescence if there is a single vertex v called the root such that for any other vertex u, there is exactly one path from u to v. An anti-arborescence is a graph whose reverse is an arborescence.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $T≔\mathrm{Graph}\left(\left\{\left[1,2\right],\left[2,3\right]\right\}\right)$
 ${T}{≔}{\mathrm{Graph 1: a directed unweighted graph with 3 vertices and 2 arc\left(s\right)}}$ (1)
 > $\mathrm{IsArborescence}\left(T\right)$
 ${\mathrm{true}}$ (2)
 > $\mathrm{IsAntiArborescence}\left(T\right)$
 ${\mathrm{true}}$ (3)
 > $C≔\mathrm{Graph}\left(\left\{\left[1,2\right],\left[2,3\right],\left[3,1\right]\right\}\right)$
 ${C}{≔}{\mathrm{Graph 2: a directed unweighted graph with 3 vertices and 3 arc\left(s\right)}}$ (4)
 > $\mathrm{IsArborescence}\left(C\right)$
 ${\mathrm{false}}$ (5)
 > $\mathrm{IsAntiArborescence}\left(C\right)$
 ${\mathrm{false}}$ (6)
 > $G≔\mathrm{Graph}\left(\left\{\left[1,2\right],\left[1,5\right],\left[2,3\right],\left[2,4\right]\right\}\right)$
 ${G}{≔}{\mathrm{Graph 3: a directed unweighted graph with 5 vertices and 4 arc\left(s\right)}}$ (7)
 > $\mathrm{IsArborescence}\left(G\right)$
 ${\mathrm{true}}$ (8)
 > $\mathrm{IsAntiArborescence}\left(G\right)$
 ${\mathrm{false}}$ (9)
 > $A≔\mathrm{Graph}\left(\left\{\left[1,3\right],\left[2,3\right]\right\}\right)$
 ${A}{≔}{\mathrm{Graph 4: a directed unweighted graph with 3 vertices and 2 arc\left(s\right)}}$ (10)
 > $\mathrm{IsArborescence}\left(A\right)$
 ${\mathrm{false}}$ (11)
 > $\mathrm{IsAntiArborescence}\left(A\right)$
 ${\mathrm{true}}$ (12)

Compatibility

 • The GraphTheory[IsArborescence] and GraphTheory[IsAntiArborescence] commands were introduced in Maple 2016.