Trees

is_tree(g)

Returns true if g is a tree: that is, a simple, connected undirected graph, with nv-1 edges (nv = number of vertices). Trees are the minimal connected graphs; equivalently they have no cycles.

This function does not apply to directed graphs. Directed trees are sometimes called polytrees).

prufer_decode(code)

Returns the unique tree associated with the given (Prüfer) code. Each tree of size n is associated with a Prüfer sequence (a[1], ..., a[n-2]) with 1 ⩽ a[i] ⩽ n. The sequence is constructed recursively by the leaf removal algoritm. At step k, the leaf with smallest index is removed and its unique neighbor is added to the Prüfer sequence, giving a[k]. The decoding algorithm goes backward. The tree associated with the empty sequence is the 2-vertices tree with one edge. Ref: Prüfer sequence on Wikipedia

prufer_encode(g::SimpleGraph)

Given a tree (a connected minimal undirected graph) of size n⩾3, returns the unique Prüfer sequence associated with this tree.

Each tree of size n ⩾ 2 is associated with a Prüfer sequence (a[1], ..., a[n-2]) with 1 ⩽ a[i] ⩽ n. The sequence is constructed recursively by the leaf removal algoritm. At step k, the leaf with smallest index is removed and its unique neighbor is added to the Prüfer sequence, giving a[k]. The Prüfer sequence of the tree with only one edge is the empty sequence.

Ref: Prüfer sequence on Wikipedia