Verifier Code

In graph theory , a designated examiner Code a result of which a labeled tree describes unambiguously. The code for a tree with nodes is of length and can be built using a simple iterative algorithm . Verifier codes were introduced by Heinz Prüfer in 1918 to prove the Cayley formula . ${\displaystyle n}$ ${\displaystyle n-2}$

algorithm

Examiner code from a tree

A validator code can be created from a tree by iteratively removing nodes until only two nodes remain. A tree with nodes is given . In step , the leaf with the smallest label is removed from the tree and the -th element of the validator code is set on the label of the only neighbor of the removed leaf. ${\displaystyle T}$ ${\displaystyle \{1,2,\ldots ,n\}}$ ${\displaystyle i}$ ${\displaystyle i}$

The code of a tree is obviously unique and has the length . ${\displaystyle n-2}$

Reconstruct a tree from an auditor code

The original tree from an examiner code can also be easily obtained.

To do this, go through the examiner code from left to right and write (in a list ) the smallest number below it, which is neither in nor in . This is connected to the current number in . The current number in is then deleted. These steps are repeated until there are no more items in . The -th element in is then connected to the -th element in by an edge. ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle i}$ ${\displaystyle p}$ ${\displaystyle i}$ ${\displaystyle b}$

However, you get a tree with only nodes. In order to get the -th node, one now connects the two numbers that are not contained in by another edge. ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle b}$

example

Examiner code from a tree

A labeled tree with examiner code 5, 5, 2, 2, 2

The algorithm presented above is applied to the image on the right. At the beginning, node 1 is the leaf with the smallest label, so this node is removed first and 5 is inserted as the first element in the auditor code. Then leaves 3 and 4 are removed from the tree and the sequence is expanded by 5 and 2. Since node 5 is now the smallest leaf, it is removed from the tree and 2 appended to the sequence. As the last node, node 6 is removed from the tree and 2 is appended to the sequence. The algorithm terminates because only two nodes (2 and 7) are left.

Tree from an examiner code

We use the validator code above . ${\displaystyle p=(5,5,2,2,2)}$

1. The smallest element that is not contained in or in is 1. The first 5 is thus connected in the tree with the 1, the 1 is added and the 5 is deleted. ${\displaystyle p}$ ${\displaystyle b=()}$ ${\displaystyle b}$
2. The smallest element that is not in or contained, the 3. It follows , and the 5 and 3 are connected in the tree by an edge. ${\displaystyle p=(5,2,2,2)}$ ${\displaystyle b=(1)}$ ${\displaystyle p=(2,2,2)}$ ${\displaystyle b=(1,3)}$
3. Next, 4 is the smallest element that isn't in or . It follows , and 2 and 4 are connected in the tree by an edge. ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle p=(2,2)}$ ${\displaystyle b=(1,3,4)}$
4. Next, 5 is the smallest element that isn't in or . There follows: , and the 2 and 5 are connected in the tree by an edge. ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle p=(2)}$ ${\displaystyle b=(1,3,4,5)}$
5. Next, 6 is the smallest element that isn't in or . There follows: , and the 2 and 6 are connected in the tree by an edge. ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle p=()}$ ${\displaystyle b=(1,3,4,5,6)}$
6. The tree with nodes is now complete. Since the auditor code has five digits, one node is still missing. This is obtained by connecting the two numbers that are not now included in (i.e. 2 and 7). ${\displaystyle n-1}$ ${\displaystyle b=(1,3,4,5,6)}$

application

The verifier code of a tree with nodes is a unique sequence of length with elements . Conversely, for a given validator code there is a length with elements from a clearly labeled tree. This can easily be shown using induction via . ${\displaystyle n}$ ${\displaystyle n-2}$ ${\displaystyle \{1,\ldots ,n\}}$ ${\displaystyle S}$ ${\displaystyle n-2}$ ${\displaystyle \{1,\ldots ,n\}}$ ${\displaystyle n}$

The direct consequence of this is that checker codes represent a bijection between the set of labeled trees with nodes and the set of sequences of length with elements . The latter set has the size , whereby the existence of the bijection proves the Cayley formula: There are labeled trees with nodes. ${\displaystyle n}$ ${\displaystyle n-2}$ ${\displaystyle \{1,\ldots ,n\}}$ ${\displaystyle n^{n-2}}$ ${\displaystyle n^{n-2}}$ ${\displaystyle n}$

The results can be generalized: A labeled tree is a spanning tree of a labeled complete graph . If appropriate restrictions are placed on the validator code, similar methods can be used to determine the number of spanning trees for complete bipartite graphs. If there is a complete bipartite graph with nodes up to in one partition and nodes up to in the other partition, then in is the number of labeled spanning trees . ${\displaystyle G}$ ${\displaystyle 1}$ ${\displaystyle k}$ ${\displaystyle k+1}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle k^{n-k-1}(n-k)^{k-1}}$

literature

• Heinz Prüfer: New proof of a theorem about permutations. In: Archives of Mathematics and Physics . Row 3, Vol. 27, 1918, pp. 742-744.

Web links

Commons : Verifier Code  - collection of images, videos and audio files