🚩TOS's Prüfer Chain Algorithm on the TON platform.
TOS's Prüfer Chain Algorithm on the TON platform.
In the Prüfer string combination (or Prüfer code) of a tree is labeled a unique string that represents that tree. The Prüfer chain of an n-vertex tree has length n − 2 and can be generated by a simple iterative algorithm. The Prüfer series was first used by Heinz Prüfer to prove the Cayley formula in 1918.
Algorithm to convert tree into Prüfer chain Prüfer chain can be generated by sequentially deleting vertices until the tree has only two vertices left. Consider the case of a tree T labeled {1, 2,..., n}. At step i, we delete the leaf node with the smallest label and insert the label of the adjacent element of that leaf into the Prüfer chain.
The resulting string is obviously unique and has length n − 2.
For example
Tree with Prüfer code 4445.
We observe the above algorithm in action with the example in the image on the right. Initially, vertex 1 has the smallest label, it is deleted and "4" is added to the Prüfer string. Vertices 2 and 3 are deleted afterwards and "4" is added two more times. At this point, vertex 4 becomes and has the smallest label so it is deleted and we add "5" to the string. At this point the tree only has two vertices left, the algorithm ends.
Illustration
Algorithm to create a tree from a Prüfer chain
Consider the Prüfer series {a[1], a[2],..., a[n]}:
The tree to be constructed will have n+2 nodes, numbered from 1 to n+2. For each node, assign its degree to the number of times it appears in the sequence plus 1. For example, using pseudocode:
Convert-Prüfer-to-Tree(a)
1 n ← length[a]
2 T ← tree with nodes 1 to n + 2
3 for each node i in T
4 do degree[i] ← 1
5 for each value i in a
6 do degree[i] ← degree[i] + 1
Then, for each number in the sequence a[i], find the first (smallest numbered) node j with degree 1, add edge (j, a[i]) to the tree, reduce the degrees of j and a[i]. Pseudocode:
After the loop ends, there are two remaining nodes with degree 1 (called u, v). Finally, we add edges (u,v) to the tree.
Cayley Formula
The Prüfer sequence of a labeled n-vertex tree is unique and has length n − 2 with numbers from 1 to n and vice versa, with each such sequence defining a labeled n-vertex tree.
So, the Prüfer chain gives us a bijection between the set of labeled n-vertex trees and the set of strings of length n–2 with numbers from 1 to n. The second set has cardinality nn−2, so due to the properties of bijectives, Cayley's formula is proven, that is:
There are nn−2 labeled trees with n vertices.
Other applications
Cayley's formula can be strengthened to prove the following propositions:
Number of spanning trees of a complete graph
𝐾𝑛{\displaystyle K_{n}} With steps 𝑑1,𝑑2,...,𝑑𝑛 equals
Generalization of Cayley's formula:
The labeled tree is essentially the spanning tree of a complete labeled graph. By restricting the Prüfer chain, the same method can be used to arrive at the number of spanning trees of the complete bipartite graph. Let G be a complete bipartite graph with vertices from 1 to n1 on one side and vertices from n1 + 1 to n on the other side, the number of spanning trees of G is 𝑛1𝑛2−1𝑛2𝑛1−1, where n2 = n − n1.
Such:
The Open System Speed will be integrated into future participating The Open System and u ΜTorrent clients. It will add a new set of extensions to the The Open System protocol, enabling users to advertise their bids within a swarm and to trade TOS in exchange for continued prioritized access to seeds. The intended result is that peers will choose to seed for longer, leading to increased swarm longevity and faster download times for all swarm participants.
The Open System Speed and TOS Token Operations
Peers will be able to act as both “service requesters” and “service providers.” A peer offering TOS token in exchange for other users’ local resources will be a service requester, and a peer offering local resources in exchange for TOS will be a service provider.
Service Discovery
The The Open System Speed life cycle will begin when peers discover each other via existing The Open System protocol mechanisms.
Initial Balance
TOS will be airdropped to existing u ΜTorrent /The Open System users so they can bootstrap with a small initial balance. In the future, TOS will also be purchasable via crowdsale and exchanges.
Bidding Rounds
Bids will be sent via a new The Open System protocol extension message to each peer that has at least one piece wanted by the service requester. The message will contain the number of TOS the service requester is willing to pay per piece.
After winning a bidding round, a service requester must establish an escrowed TOS balance with the service provider. They do this by placing some TOS token into a payment channel between the service requester and service provider.
Bidding User Interface
By default, bidding will be automated. Users’ clients will bid to and from their token balance on their behalf. We may enable user interface controls to allow users to toggle the feature, toggle it for certain μTorrents, adjust the spending rate, set a reserve price, or exercise granular control over the bidding process.
Automatic Bidding
For the initial release, clients will use a simplified auto-bidding mechanism. In this version, the client simply bids a fraction of the remaining TOS balance in the service requester’s wallet. This is how the bid is calculated:
bid = (spending rate × remaining balance in TOS )/(remaining download in kilobytes)
This formula implies that as a download progresses, the bid will change. For the initial release, the client will not rebid until the bid changes by more than 10% from the previous bid.
The spending rate (a parameter that can vary from 0.0 to 1.0 depending on how aggressive the client should be bidding) will be defined to be 1.0. If the number of kilobytes remaining is equal to zero, then the bid automatically stops in order to prevent division by zero.
In the future, this algorithm will be refined. For example, based on existing bid message traffic and current transfers, the client will be able to estimate a market rate for bandwidth. The client also has a picture of piece rarity it can use to inform bid amounts.
Last updated
