GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Parameters

Options

Description

Details

Examples

Compatibility

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

withGraphTheory:

TGraph1,2,2,3

TGraph 1: a directed unweighted graph with 3 vertices and 2 arc(s)

(1)

IsArborescenceT

true

(2)

IsAntiArborescenceT

true

(3)

CGraph1,2,2,3,3,1

CGraph 2: a directed unweighted graph with 3 vertices and 3 arc(s)

(4)

IsArborescenceC

false

(5)

IsAntiArborescenceC

false

(6)

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

GGraph 3: a directed unweighted graph with 5 vertices and 4 arc(s)

(7)

IsArborescenceG

true

(8)

IsAntiArborescenceG

false

(9)

AGraph1,3,2,3

AGraph 4: a directed unweighted graph with 3 vertices and 2 arc(s)

(10)

IsArborescenceA

false

(11)

IsAntiArborescenceA

true

(12)

Compatibility

• 

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

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

• 

The GraphTheory[IsArborescence] and GraphTheory[IsAntiArborescence] commands were updated in Maple 2019.

• 

The root option was introduced in Maple 2019.

• 

For more information on Maple 2019 changes, see Updates in Maple 2019.

See Also

IsAcyclic

IsConnected

IsForest

IsTree

NumberOfEdges

NumberOfVertices