查看“︁普吕弗序列”︁的源代码

在[[图论]]中，[[标号树]]的'''普吕弗序列'''（{{lang-en|Prüfer sequence}}）是由树唯一地产生的[[序列]]。''n''[[顶点 (图论)|顶点]]的标号树有长''n'' − 2的普吕弗序列，可以从一个简单的迭代算法得到。普吕弗序列在1918年首先由[[海因茨·普呂弗]]用来证明[[凯莱公式]]。

== 算法 ==
一棵树要得到普吕弗序列，方法是逐次去掉树的[[顶点 (图论)|顶点]]，直到剩下两个顶点。考虑树''T''，其顶点为{1, 2, ..., ''n''}。在第''i''步，去掉标号最小的叶，并把普吕弗序列的第''i''项设为这叶的邻顶点的标号。

一棵树的序列明显是唯一的，而且长为''n'' − 2。

[[File:Tree graph.svg|right|frame|这棵标号树有普吕弗序列{4,4,4,5}。]]

== 例子 ==
把上述算法用在右图标号树。第一步，[[顶点 (图论)|顶点]]1是最小标号的叶，因此首先去掉，普吕弗序列首项是"4"，接着去掉顶点2和3，"4"两次加进序列。顶点4现在是叶，去掉后剩下2个顶点，所以把"5"加进序列后结束。树的序列是{4,4,4,5}。

== 復原算法 ==
从一个普吕弗序列，可以求得一棵树有这一普吕弗序列。

设这普吕弗序列长''n'' − 2。首先写出数1至''n''。第一步，找出1至''n''中没有在序列中出现的最小数。把标号为这数的[[顶点 (图论)|顶点]]和标号为序列首项的顶点连起来，并把这数从1至''n''中删去，序列的首项也删去。接着每一步以1至''n''中剩下的数和餘下序列重复以上步骤。最后当序列用完，把1至''n''中最后剩下的两数的顶点连起来。

== 应用 ==
一棵树的序列明显地是唯一的，但比较不明显的是，一个长为''n''−2且每项都在1至''n''之间的序列''S''，有唯一的标号树以''S''为普吕弗序列。这个结果可以对''n''用[[数学归纳法]]证明。

从这结果立刻可知，普吕弗序列给出长''n''−2的序列和有''n''[[顶点 (图论)|顶点]]的标号树之间的[[一一映射]]。长''n''−2的序列共有''n''<sup>''n''−2</sup>个，这样就证明了凯莱公式，就是''n''顶点的标号树共有''n''<sup>''n''−2</sup>棵。

这个结果可以推广：一棵标号树实际上是标号[[完全图]]的一棵[[生成树]]。对普吕弗序列加以限制。类似的方法可以得到标号完全[[二部图]]的生成树总数。若''G''是完全二部图，一部分的顶点标号1到''n''<sub>1</sub>，另一部分的顶点标号''n''<sub>1</sub> + 1到''n''。''G''的标号生成树总数为<math>n_{1}^{n_2-1} n_{2}^{n_1-1}</math>，其中''n''<sub>2</sub> = ''n'' − ''n''<sub>1</sub>。

== 参考 ==
* {{Journal reference | title=Neuer Beweis eines Satzes über Permutationen | journal=Arch. Math. Phys. | year=1918 | volume=27 | pages=742-744|url=|issue=|doi=|others=|page=|pmid=|author=Prüfer, H.}}

[[Category:图论]]
[[Category:序列]]