Graph Theory

A graph is a collection of vertices and edges. An edge is a connection between two vertices. Graphs model real-world relationships: a computer network has PCs connected by cables, an airline map has cities connected by routes.

Terminology

Vertex (node): a point in the graph
Edge: a connection between two vertices
Undirected graph: edges have no direction. An edge between A and B means you can travel either way.
Directed graph (digraph): edges have direction. An edge from A to B does not mean there is one from B to A.
Path: a list of vertices where each successive pair is connected by an edge. For example, FGHE is a path from F to E.
Simple path: a path with no vertex repeated. FGHEG is not a simple path.
Connected graph: there is a path from every vertex to every other vertex. A graph that is not connected is made up of connected components.
Cycle: a path that is simple except the first and last vertex are the same. Any vertex in the cycle may be listed first. By convention, list the start/end vertex twice: HEGH, not HEG.
Complete graph: every pair of vertices is connected by an edge.
Sparse graph: relatively few edges present (roughly fewer than $V lo g V$ ).
Dense graph: relatively few edges missing.

Directed graphs

In a directed graph, edge $x y$ can be used in a path from $x$ to $y$ but not necessarily from $y$ to $x$ . Edges with arrows on both ends indicate an edge in each direction, essentially making an undirected edge.

A directed graph with no cycles is called a DAG (directed acyclic graph).

Trees and forests

A graph with no cycles is called a tree. There is only one path between any two nodes in a tree. A tree with $N$ vertices contains exactly $N - 1$ edges.

A group of disconnected trees is called a forest.

A weighted graph has a numerical weight (cost) associated with each edge. For example, in an airline graph, cities are vertices and the weight of each edge might be the distance between them.

A spanning tree of a graph is a subgraph that contains all the vertices and forms a tree. A minimal spanning tree can be found for weighted graphs to minimize the total cost across the network.

Adjacency matrices

A graph can be represented as an $N \times N$ matrix. Label rows and columns for each vertex. Place a 1 in cell $(i, j)$ for each edge from vertex $i$ to vertex $j$ , and 0 everywhere else.

Example: For a directed graph with edges ${A B, A D, B C, D B}$ :

    A  B  C  D
A [ 0  1  0  1 ]
B [ 0  0  1  0 ]
C [ 0  0  0  0 ]
D [ 0  1  0  0 ]

Cell $(i, j) = 1$ means there is a direct path from vertex $i$ to vertex $j$ .

Counting paths of a given length

To count paths of length exactly $p$ from vertex $i$ to vertex $j$ , trace the graph: enumerate every sequence of $p$ edges that starts at $i$ and ends at $j$ , with no edge repeated within a path.

Example: Directed graph with edges ${A B, A D, B C, D B}$ . How many paths of length 2 go from A to C?

From A you can go to B (via AB) or D (via AD). Now extend one more step:

A → B → ? B’s outgoing edge is BC, so A → B → C ✓
A → D → ? D’s outgoing edge is DB, so A → D → B ✗ (ends at B, not C)

Only one 2-step path from A to C: A → B → C. Answer: 1.

Counting cycles

ACSL asks you to count distinct cycles in a directed graph. A cycle visits no vertex more than once except the start/end vertex.

Strategy: By inspection, trace all paths from each vertex back to itself. List each cycle starting from any of its vertices (any starting point is valid). Avoid counting the same cycle twice.

Example: Directed graph with vertices ${A, B, C, D, E}$ and edges ${A B, B A, B C, C D, D C, D B, D E}$

By inspection, the cycles are: ABA, BCDB, and CDC. Total: 3 cycles.

Common mistakes

Directed vs undirected confusion. In a directed graph, edge $A B$ does not imply $B A$ . Check the arrows.
Missing edges from the adjacency matrix. Read every row carefully before drawing the graph.
Wrong path length. A path of length 2 uses exactly 2 edges. Count edges, not vertices.
Counting duplicate cycles. HEGH and EHGE describe the same cycle. Any vertex may be listed first.

Contest strategy

Draw the graph. Always. Even if the problem gives an adjacency matrix.
For path-counting problems: list all outgoing edges from the start, extend each one step at a time, count only paths that reach the target in exactly the required length.
For cycle counting: be systematic and check each vertex as a potential start.
Typical ACSL problems: count cycles, count paths of length $p$ , draw a graph from its adjacency matrix, or write the adjacency matrix for a drawn graph.