Web hosting control panel - 4.6.3 EVALUATION OF POWERS 461 If oi =
4.6.3 EVALUATION OF POWERS 461 If oi = oj + a,+ for more than one pair of indices (j, k), we choose a definite j and k for purposes of this construction. In general, all but the first vertex of such a directed graph will be at the head of exactly two arcs; however, this is not really an important property of the graph, because it conceals the fact that many different addition chains can be essentially equivalent. If a vertex has out-degree 1 (i.e., only one arc leading away), it is used in only one later step, hence the later step is essentially a sum of three inputs aj + ak + a, that might be computed either as (aj + ak) + a, or as aj + (ah + a,) or as ak + (ai + a,). These three choices are immaterial, but the addition-chain conventions force us to distinguish between them. We can avoid such redundancy by deleting any vertex whose out-degree is 1 and attaching the arcs from its predecessors to its successor. For example, the above graph would become (52) We can also delete any vertex whose out-degree is 0, except of course the final vertex a,., since such a vertex corresponds to a useless step in the addition chain. In this way every addition chain leads to a reduced directed graph that contains one source vertex (labeled 1) and one sink vertex (labeled n); every vertex but the source has in-degree 2 2 and every vertex but the sink has out-degree 2 2. Conversely, any such directed graph without oriented cycles corresponds to at least one addition chain, since we can topologically sort the vertices and write down d - 1 addition steps for each vertex of in-degree d > 0. The length of the addition chain, exclusive of useless steps, can be reconstructed by looking at the reduced graph; it is (number of arcs) - (number of vertices) + 1, (53) since deletion of a vertex of out-degree 1 also deletes one arc. We say that two addition chains are equivalent if they have the same reduced directed graph. For example, the addition chain 1, 2, 3, 6, 12, 15, 24, 39, 40, 79 is equivalent to the chain we began with, since it also leads to (52). This example shows that a non-star chain can be equivalent to a star chain. An addition chain is equivalent to a star chain if and only if its reduced directed graph can be topologically sorted in only one way. An important property of this graph representation has been pointed out by N. Pippenger: The label of each vertex is exactly equal to the number of oriented paths from the source to that vertex. Thus, the problem of finding an optimal addition chain for 72 is equivalent to minimizing the quantity (53) over all directed graphs that have one source vertex and one sink vertex and exactly n oriented paths from the source to the sink. This characterization has a surprising corollary, because of the symmetry of the directed graph. If we reverse the direction of all the arcs, the source and the
Note: If you are looking for best quality webspace to host and run your tomcat application check Vision personal web hosting services