What a Graph Is
What This Concept Is
A graph model specifies vertices, edges and interpretation. Directed edges are ordered; undirected edges connect unordered endpoint pairs. In a multigraph, edges need their own identities because different records can share endpoints. Declare isolated vertices explicitly: deriving vertices only from edges loses them. Weights, capacities, durations and probabilities are different quantities, even when represented by numbers.
In this module a walk can repeat vertices/edges; a simple path cannot repeat a vertex. A directed cycle includes a self-loop when loops are allowed. In an undirected multigraph two distinct parallel edges can form a two-edge cycle; the length-at-least-three rule applies to simple undirected graphs.
Why It Matters Here
Most correctness arguments are conditional on this model. An implementation that changes direction, merges parallel records or interprets missing edges as zero-weight edges can solve a different problem while returning plausible numbers.
Concrete Examples
Declare vertices 0 through 3 and records (0,1,5),(0,1,2),(1,2,0).
There are four vertices and three directed edge records. Vertex 3 is isolated;
the second parallel edge offers a cheaper route to 1; the zero-weight edge to 2
is present. A predecessor vertex alone does not identify which parallel edge was
used. Returning original edge IDs preserves an auditable route.
For undirected degree counting, a loop contributes two incidences, preserving sum(degrees)=2E. In a directed graph, each record contributes once to total indegree and once to total outdegree, including self-loops.
Common Confusion / Misconceptions
A path minimizing additive weights is not automatically a route maximizing reliability or minimizing its largest edge. With a reachable negative cycle, minimum-cost walks to some targets are unbounded; minimum simple paths are a different constrained problem. State whether repeated visits are allowed before interpreting a negative-cycle result.
How To Use It
Write a model card before choosing an algorithm: vertex domain, direction, edge identity, quantity/units, allowed signs, loops/duplicates, source/target, objective, output witness and empty/disconnected behavior. The lab uses integer IDs and exact integer arithmetic, with explicit unreachable/unbounded statuses.
Check Yourself
- Why does an edge list not reveal every isolated vertex?
- Why can parent vertices lose information in a multigraph?
- How does a loop contribute to undirected degree?
- When does forbidding repeated vertices change the optimization problem?
Mini Drill or Application
Model a one-way road network with parallel toll options and an isolated depot. Specify whether toll, travel time or hop count is optimized. Give a case where two choices yield different routes. Encode every physical edge once with a stable ID, then state the representation rule for an undirected version. See P1.
Read This Only If Stuck
Find graph definitions, multigraphs, paths, and modeling in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.