Basic Digraph Models and Properties
Jay Yellen · Discrete mathematics and its applications · 2013
Harold N. Gabow, University of Colorado 10.1.1 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1175 10.1.2 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1177 10.1.3 Topological Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1180 10.1.4 Connectivity Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1185 10.1.5 DFS as a Proof Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1192 10.1.6 More Graph Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1193 10.1.7 Approximation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1201 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203 INTRODUCTION A search of a graph is a methodical exploration of all the vertices and edges. It must run in “linear time,” i.e., in one pass (or a small number of passes) over the graph. Even with this restriction, a surprisingly large number of fundamental graph properties can be tested and identified.