GENERATING FUNCTIONS OF ABSTRACT GRAPHS WITH APPLICATIONS,
Abstract
This report is concerned with the concept, properties, and application of generating functions of abstract graphs. Many practical problems can be handled in a unified manner using these techniques, for example: code, generation, path enumeration, shift register sequences, sampled data systems, discrete Markov processes, and certain connectivity considerations in automata. The generating function of a graph is a function of the complex variable z which has the property that interesting attributes of the graph can be extracted from it by numerical operations. The generating function can be written as a standard rational function of z, and the denominator is called the characteristic function of the graph. This latter function, interesting in its own right, can also be obtained independently. The computation of the generating function involves either matrix inversions or application of formulas that take into account the topological characteristics of the graph. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 24, 1964
- Accession Number
- AD0607254
Entities
People
- C. V. Ramamoorthy
- D. W. Tufts
Organizations
- Harvard University