A Path Entropy Function for Rooted Trees

ABSTRACT

The class of rooted trees or arborescences used for modeling hierarchical classification and indexing procedures is considered. An entropy function measuring the complexity of the paths from the root to the terminal vertices is defined. Upper and lower bounds are found for the values of this function, and it is shown to be additive with respect to a tree product operation defined here. The results are extended to the case when the terminal vertices are weighted, and the path entropy function is compared to the information function defined by C. Picard for questionnaires.

REFERENCES

• 1: BURC~E, W H. Sorting, trees and measures of order. Inform, a~d Contr. 1 (1958), 181-197.
• 2: JARDINE, N, AN~ S~BSON, It Mathematical Taxonomy. Wiley, London, 1971.
• 3: Gerard. Salton, Automatic Information Organization and Retrieval., McGraw Hill Text, 1968
• 4: PICARD, C. Th$~rze des Questionnaires, Gauthmr.Villars, Paris, 1965.
• 5: WATANABE, S. Knowing and Guessing. Wiley, New York, 1969,
• 6: ORE, O Theo, ry of Graphs. Amer Math So0., Providence, R.I., 1962.
• 7: BUSACKEa, R., ANn SAATY, T. L Finite Graphs and N~tworks. McGraw-Hill, New York, 1965.
• 8: :KHINOHIN, A. I Mathematieal Foundations of Information Theory. Dover, New York, 1957.
• 9: HARARV, F. On the group of composition of two graphs. Duke Math. J. ~9 (1959), 29-34.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Measurement, Performance, Theory