A graph is formally an ordered pair G = (V, E) of a vertex set and an edge set, and this material develops the vocabulary that classifies graphs by the kinds of edges they admit and by the structures traversal over them produces. Special edges — self loops (both endpoints the same vertex) and multi-edges (an edge occurring more than once) — define by their absence the simple graph, whose edge count is bounded by N(N−1) when directed and N(N−1)/2 when undirected, which in turn grounds the dense/sparse classification that governs the choice of storage representation. Traversal vocabulary layers walk, trail, and simple path, from which connectedness (strong and weak) and cycles, closed walks, simple cycles, and acyclic graphs including DAGs are defined; this belongs to graph theory as applied within data structures and algorithms in computer science.
A graph is formally an ordered pair G = (V, E) of a vertex set and an edge set, and this material develops the vocabulary that classifies graphs by the kinds of edges they admit and by the structures…