普鲁弗序列

class sympy.combinatorics.prufer.Prufer(*args, **kw_args)

Prufer对应是一种描述标号树与Prufer码之间双射的算法。标记树的Prufer码在同构上是唯一的，其长度为n-2。

Prufer序列首先由heinzprufer用来证明Cayley公式。

工具书类

[R93]

https://mathworld.wolfram.com/LabeledTree.html

static edges(*runs)

返回一个边的列表和给定运行中连接标记为整数的树中的节点的节点数。

所有节点号都将被移动，以使最小节点为0。如果边在管路中重复，这不是问题；只返回唯一的边。对于节点标签的范围没有任何假设，但是从最小到最大的所有节点都必须存在。

实例

>>> 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)

删除重复边：

>>> 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)

生成大于当前序列的delta的Prufer序列。

实例

>>> 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

参见

prufer_rank, rank, prev, size

property nodes

返回树中的节点数。

实例

>>> 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)

在当前序列之前生成-delta的Prufer序列。

实例

>>> 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

参见

prufer_rank, rank, next, size

prufer_rank()

计算普鲁弗序列的秩。

实例

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

参见

rank, next, prev, size

property prufer_repr

返回Prufer对象的Prufer序列。

这个序列是通过移除编号最高的顶点，记录它所附加到的节点来找到的，并继续下去，直到只剩下两个顶点为止。Prufer序列是记录节点的列表。

实例

>>> 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]

参见

to_prufer

property rank

返回Prufer序列的秩。

实例

>>> 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

参见

prufer_rank, next, prev, size

property size

返回此Prufer对象可能的树数。

实例

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

参见

prufer_rank, rank, next, prev

static to_prufer(tree, n)

返回树的Prufer序列，其中 n 是树中的节点数。

实例

>>> 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]

参见

prufer_repr

返回Prufer对象的Prufer序列。

static to_tree(prufer)

返回给定Prufer序列的树（作为边的列表）。

实例

>>> 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]]

参见

tree_repr

返回Prufer对象的树表示形式。

工具书类

[R94]

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

property tree_repr

返回Prufer对象的树表示形式。

实例

>>> 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]]

参见

to_tree

classmethod unrank(rank, n)

找到未排列的Prufer序列。

实例

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