Software Testing, 4th Edition

Chapter 4

Graph Theory for Testers

Graph theory is a branch of topology that is sometimes referred to as “rubber sheet geometry.” Curious, because the rubber sheet parts of topology have little to do with graph theory; furthermore, the graphs in graph theory do not involve axes, scales, points, and curves as you might expect. Whatever the origin of the term, graph theory is probably the most useful part of mathematics for computer science—far more useful than calculus—yet it is not commonly taught. Our excursion into graph theory will follow a “pure math” spirit in which definitions are as devoid of specific interpretations as possible. Postponing interpretations results in maximum latitude in interpretations later, much like well-defined abstract ...