Graph theory started in 1735 with Euler’s proof that no path could lead a person over all seven bridges of the Prussian town of Königsberg without at least one bridge being crossed twice. Our study of Euler’s theorem in Section 6.1 allows us to introduce such concepts as paths, Euler paths and connectedness for graphs. Section 6.2 uses matrices over semirings to characterize the connectivity of graphs. Finally, Section 6.3 applies these connectivity matrices to analyze the reachability problem for automata, and then returns to a theme initiated in Section 2.3, showing that a language is accepted by a finite-state acceptor iff it can be built up from finite sets by a finite number of applications of the operations of union, dot, and star.

Unable to display preview. Download preview PDF.

Authors and Affiliations

1. Department of Computer and Information Science, University of Massachusetts, Amherst, MA, 01003, USA

   Michael A. Arbib & Robert N. Moll

2. Department of Mathematics, Boston University, Boston, MA, 02215, USA

   A. J. Kfoury

Reprints and permissions

© 1981 Springer-Verlag New York Inc.

Policies and ethics