InfiniBand networks use destination based routing: when a switch receives a 
packet, it uses the destination address carried in the packet header to
determine the out-going port to forward the packet. As a result, for each 
destination address, only one out-going link can be used. This limits the 
network traffic engineering capability. For example, consider the following
network 

                     0
                    / \
                   /   \
                  1     2
                   \   /
                    \ /
                     3
                    / \
                   /   \
                  4     5

It is impossible to use one address for node 0 to realize two paths:
4->3->1->0 and 5->3->2->0. With one address, there can be only one out-going
port from node 3. To alleviate this problem, InfiniBand allows multiple 
addresses to be assigned to each node: the two paths can then be realized by 
two addresses. Whenever two paths have a split in a node, two different 
addresses must be assigned to the two paths. 

Given a topology and a set of paths (to one destination), (1) 
design an algorithm to decide the number of addresses that are required to 
realize the set of paths (your algorithm must be better than the trivial 
scheme of allocating one address for each path), (2) design an efficient 
algorithm to decide the smallest number of addresses required to realize 
the paths and provide a proof that your algorithm actually does that. 

Consider the following example:

                  1
                 / \
                /   \
               /     \
              2       3
              |\     /|
              | \   / |
              |  \ /  |
              |   4   |
              |  / \  |
              | /   \ |
              |/     \|               
              5       6
             / \     / \
            7   8   9  10

The smallest number of addresses needed for the following four paths is 2,
one for p0 and p3 and the other one for p1 and p2.
 
p0 = 7->5->2->1
p1 = 8->5->4->3->1
p2 = 9->6->3->1
p3 = 10->6->4->2->1