Prufer Sequences¶

class sympy.combinatorics.prufer.Prufer(*args, **kw_args)[source]¶

The Prufer correspondence is an algorithm that describes the bijection between labeled trees and the Prufer code. A Prufer code of a labeled tree is unique up to isomorphism and has a length of n - 2.

Prufer sequences were first used by Heinz Prufer to give a proof of Cayley’s formula.

References

R79: http://mathworld.wolfram.com/LabeledTree.html

static edges(*runs)[source]¶

Return a list of edges and the number of nodes from the given runs that connect nodes in an integer-labelled tree.

All node numbers will be shifted so that the minimum node is 0. It is not a problem if edges are repeated in the runs; only unique edges are returned. There is no assumption made about what the range of the node labels should be, but all nodes from the smallest through the largest must be present.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer.edges([1, 2, 3], [2, 4, 5]) # a T
([[0, 1], [1, 2], [1, 3], [3, 4]], 5)

Duplicate edges are removed:

>>> Prufer.edges([0, 1, 2, 3], [1, 4, 5], [1, 4, 6]) # a K
([[0, 1], [1, 2], [1, 4], [2, 3], [4, 5], [4, 6]], 7)

next(delta=1)[source]¶

Generates the Prufer sequence that is delta beyond the current one.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> a = Prufer([[0, 1], [0, 2], [0, 3]])
>>> b = a.next(1) # == a.next()
>>> b.tree_repr
[[0, 2], [0, 1], [1, 3]]
>>> b.rank
1

See also

prufer_rank, rank, prev, size

property nodes¶

Returns the number of nodes in the tree.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).nodes
6
>>> Prufer([1, 0, 0]).nodes
5

prev(delta=1)[source]¶

Generates the Prufer sequence that is -delta before the current one.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> a = Prufer([[0, 1], [1, 2], [2, 3], [1, 4]])
>>> a.rank
36
>>> b = a.prev()
>>> b
Prufer([1, 2, 0])
>>> b.rank
35

See also

prufer_rank, rank, next, size

prufer_rank()[source]¶

Computes the rank of a Prufer sequence.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> a = Prufer([[0, 1], [0, 2], [0, 3]])
>>> a.prufer_rank()
0

See also

rank, next, prev, size

property prufer_repr¶

Returns Prufer sequence for the Prufer object.

This sequence is found by removing the highest numbered vertex, recording the node it was attached to, and continuing until only two vertices remain. The Prufer sequence is the list of recorded nodes.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).prufer_repr
[3, 3, 3, 4]
>>> Prufer([1, 0, 0]).prufer_repr
[1, 0, 0]

See also

to_prufer

property rank¶

Returns the rank of the Prufer sequence.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> p = Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]])
>>> p.rank
778
>>> p.next(1).rank
779
>>> p.prev().rank
777

See also

prufer_rank, next, prev, size

property size¶

Return the number of possible trees of this Prufer object.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer([0]*4).size == Prufer([6]*4).size == 1296
True

See also

prufer_rank, rank, next, prev

static to_prufer(tree, n)[source]¶

Return the Prufer sequence for a tree given as a list of edges where n is the number of nodes in the tree.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> a = Prufer([[0, 1], [0, 2], [0, 3]])
>>> a.prufer_repr
[0, 0]
>>> Prufer.to_prufer([[0, 1], [0, 2], [0, 3]], 4)
[0, 0]

See also

prufer_repr: returns Prufer sequence of a Prufer object.

static to_tree(prufer)[source]¶

Return the tree (as a list of edges) of the given Prufer sequence.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> a = Prufer([0, 2], 4)
>>> a.tree_repr
[[0, 1], [0, 2], [2, 3]]
>>> Prufer.to_tree([0, 2])
[[0, 1], [0, 2], [2, 3]]

See also

tree_repr: returns tree representation of a Prufer object.

References

R80: https://hamberg.no/erlend/posts/2010-11-06-prufer-sequence-compact-tree-representation.html

property tree_repr¶

Returns the tree representation of the Prufer object.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).tree_repr
[[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]
>>> Prufer([1, 0, 0]).tree_repr
[[1, 2], [0, 1], [0, 3], [0, 4]]

See also

to_tree

classmethod unrank(rank, n)[source]¶

Finds the unranked Prufer sequence.

Examples

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer.unrank(0, 4)
Prufer([0, 0])

Polyhedron

Subsets