Graph theory

A graph represents objects as vertices and chosen relationships as edges. Intersections in a road network or states in a program can become vertices. Modeling starts by defining the edge meaning: adjacency, reachability, and dependency are different relationships. The graph structure does not independently decide which interpretation is appropriate to the problem.

References: [1]

Directed edges distinguish travel from one vertex toward another, while undirected edges express symmetric connections. Weights can encode costs, distances, or capacities. Minimizing the number of edges and minimizing total weight are different tasks, so the algorithm must match the direction, weight assumptions, and other properties of the graph being studied.

References: [2]

Traversal visits neighboring vertices to discover reachable structure. Depth-first and breadth-first methods advance differently; breadth-first layers correspond to minimum-edge distances in unweighted graphs. Tracking visited vertices handles cycles and prevents repeated expansion simply because several incoming paths lead to the same already encountered part of a graph.

References: [1]

Adjacency lists store neighbors, while matrices represent connections through indexed positions, with different access and storage costs. Connectivity usually does not depend on where a vertex is drawn on screen. Separating structure, representation, and visual layout preserves relationships across redesigned displays and supports appropriate processing methods as network size grows.

References: [2]