Analysis of Graphs by Connectivity Considerations

ABSTRACT

Discrete sequential systems, such as sampled data systems, discrete Markov processes, linear shift register generators, computer programs, sequential code generators, and prefixed comma-free codes, can be represented and studied in a uniform manner by directed graphs and their generating functions. In this paper the properties of the generating functions are examined from certain connectivity considerations of these graphs.

REFERENCES

• 1: CHEN, Y. C. AND WING, O. Connectivity of directed graphs. Proc. of Allerton Conf. 0 Circuit and System Theory, U. of Illinois, Sept. 1964.
• 2: HARIY, F. Some historical and intuitive aspects of graph theory. SiAM Rev. 2, 2 (1960), 123-131.
• 3: -- ET hL. Structural Models. John Wiley & Sons, New York, 1965.
• 4: Rosalind B. Marimont, A New Method of Checking the Consistency of Precedence Matrices, Journal of the ACM (JACM), v.6 n.2, p.164-171, April 1959 [doi>10.1145/320964.320973]
• 5: ----. Applications of graphs and Boolean matrices to computer programming. SIAM tgev. 2, 4 (1960), 259-268.
• 6: PROSSER R. Applications of Boolean matrices to tim analysis of flow diagrams. Proc, laastern Joint Comput. Conf. 1959. (Now available from Spartan Books, Washington, D .C.)
• 7: IAMAMOOItTIY, C.V. Doctoral thesis, ttarvard U., May 1964.
• 8: --. Representation and analysis of discrete systems using generating functions of abstract graphs. IEEE Int. Cony. Rec. 1965, Pt. 6.
• 9: --. Connectivity considerations of graphs representing discrete sequential systems. Trans. IEEE EC-I4 (Oct. 1965), 724-727.
• 10: --. A unitied approach for solving quantitative problems in discrete systems by generating functions of abstract graphs. Proc. IFIP Congr. 1965, Vol. 2, MacMillan Co., New York, 1965.
• 11: --- Transitions in multi-parameter multi-level discrete systems. IEEE Publ. 4C9, Proc. IEEE Syrup. on Signal Transmission and Processing, 1965.
• 12: --. Discrete Markov analysis of computer programs. Proc. ACM 20th Nat. Conf., 19(5, p p . 386-392.
• 13: - Signal coding for transmission and resolution by graph theoretic methods. Proc. First Annual IEEE Communications Cony., 1965, pp. 193-199.
• 14: ---- AND TUFTS, D.W. Reinforced comma-free codes. Cruft Lab. Rep. No. 480, Harvard U., ug. 1965; also Paper, IEEE Int. Symposium on Inf. Theory, 1966.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Measurement, Performance, Theory, Verification