Graph Basics

1Introduction

This lecture defines graphs as representations of relationships between objects and develops adjacency, paths, distance, and connectivity as the concepts required for graph traversal.

In a road network, connectivity matters more than the shapes of intersections. In a communication network, reachability matters more than the appearance of devices. A graph extracts these relationships and allows structurally identical questions to be treated in a common language.

2Terms and definitions

A graph $$G=(V,E)$$G=(V,E) consists of a set $$V$$V of vertices and a set $$E$$E of edges. Vertices represent objects, while edges represent relationships between pairs of objects. An undirected graph in this lecture is a finite simple graph with

Thus it contains neither self-loops nor parallel edges.

For a directed graph, $$E\subseteq V\times V$$E\subseteq V\times V, and an edge $$(u,v)$$(u,v) is oriented from $$u$$u to $$v$$v. Unless stated otherwise, the remainder of this lecture considers finite simple undirected graphs.

Two vertices $$u,v$$u,v are adjacent when an edge directly joins them. The neighborhood of a vertex $$v$$v is

3Paths and distance

A sequence of vertices

is a walk of length $$k$$k when $$\{v_{i-1},v_i\}\in E$$\{v_{i-1},v_i\}\in E for every $$i=1,\dots ,k$$i=1,\ldots,k. It is a path when $$v_0,\dots ,v_k$$v_0,\ldots,v_k are distinct. If a walk from $$s$$s to $$v$$v exists, deleting cycles yields a path, and $$v$$v is reachable from $$s$$s.

In an unweighted graph, the distance $$d(s,v)$$d(s,v) is the minimum length of a path from $$s$$s to $$v$$v. If no path exists, set $$d(s,v)=\mathrm{\infty }$$d(s,v)=\infty. Here, “unweighted” means that every edge counts as one step.

4Connectivity

An undirected graph is connected when a path exists between every pair of vertices. A disconnected graph decomposes into connected components, each consisting of vertices that are mutually reachable.

For example, if

then $$a,b,c$$a,b,c form one connected component, while $$d$$d forms a component by itself. Moreover, $$d(a,c)=2$$d(a,c)=2.

5Representations

An adjacency list stores $$N\left(v\right)$$N(v) for each vertex $$v$$v. If the graph has $$\left|V\right|$$|V| vertices and $$\left|E\right|$$|E| edges, all adjacency lists of an undirected graph contain $$2\left|E\right|$$2|E| entries in total, because every edge appears once at each endpoint.

An adjacency matrix numbers the vertices and records edge existence in matrix entries. It supports fast edge-existence queries but requires space proportional to the square of the number of vertices. Adjacency lists are suitable for sparse graphs; adjacency matrices are candidates for dense graphs or workloads dominated by edge-existence queries.

6Connection to traversal

A graph traversal starts at a vertex, examines adjacent vertices in a specified order, and enumerates reachable vertices. Vertices, edges, adjacency, paths, and distance as defined here form the input and claims of DFS and BFS.

7Summary

• A graph $$G=(V,E)$$G=(V,E) represents objects as vertices and relationships as edges.
• A path is a sequence of distinct adjacent vertices, and unweighted distance is the number of edges in a shortest path.
• Connectivity is defined by reachability between every pair of vertices.
• Adjacency lists and adjacency matrices represent the same graph with different computational tradeoffs.