Graphs

Understand the different types of graphs and their properties.

Graph

Formally, a simple graph is a pair of sets (V,E)(V,E), where VV is an arbitrary non-empty finite set, whose elements are called vertices or nodes, and EE is a set of pairs of elements of VV, which we call edges. In an undirected graph, the edges are unordered pairs or just sets of size two; we usually write uv{uv} instead of {u,v}\left\{ u, v \right\} to denote the undirected edge between uu and vv. In a directed graph, the edges are ordered pairs of vertices; we usually write uvu\rightarrow v instead of (u,v)(u, v) to denote the directed edge from uu to vv.

Following standard (but admittedly confusing) practice, we will also use VV to denote the number of vertices in a graph and EE to denote the number of edges. Thus, in any undirected graph, we have 0E(V2)0 ≤ E ≤ \binom{V}{2}, and in any directed graph, we have 0EV(V1)0 ≤ E ≤ V (V − 1).

The endpoints of an edge uvuv or uvu\rightarrow v are its vertices uu and vv. We distinguish the endpoints of a directed edge uvu\rightarrow v by calling uu the tail and vv the head.

The definition of a graph as a pair of sets forbids multiple undirected edges with the same endpoints or multiple directed edges with the same head and the same tail. (The same directed graph can contain both a directed edge uvu\rightarrow v and its reversal vuv\rightarrow u.) Similarly, the definition of an undirected edge as a set of vertices forbids an undirected edge from a vertex to itself. Graphs without loops and parallel edges are often called simple graphs; non-simple graphs are sometimes called multigraphs. Despite the formal definitional gap, most algorithms for simple graphs extend to multigraphs with little or no modification, and for that reason, we see no need for a formal definition here.

For any edge uvuv in an undirected graph, we call uu a neighbor of vv and vice versa, and we say that uu and vv are adjacent. The degree of a node is its number of neighbors. In directed graphs, we distinguish two kinds of neighbors. For any directed edge uvu\rightarrow v, we call uu a predecessor of vv, and we call vv a successor of uu. The in-degree of a vertex is its number of predecessors; the out-degree is its number of successors.

A graph G=(V,E)G^′ = (V^′,E^′) is a subgraph of G=(V,E)G = (V,E) if VVV^′ ⊆ V and EEE^′ ⊆ E. A proper subgraph of GG is any subgraph other than GG itself.

Walk and path

A walk in an undirected graph GG is a sequence of vertices, where each adjacent pair of vertices is adjacent in GG; informally, we can also think of a walk as a sequence of edges. A walk is called a path if it visits each vertex at most once. For any two vertices uu and vv in a graph GG, we say that vv is reachable from uu if GG contains a walk (and therefore a path) between uu and vv. An undirected graph is connected if every vertex is reachable from every other vertex. Every undirected graph consists of one or more components, which are its maximal connected subgraphs; two vertices are in the same component if, and only if, there is a path between them.

A walk is closed if it starts and ends at the same vertex; a cycle is a closed walk that enters and leaves each vertex at most once. An undirected graph is acyclic if no subgraph is a cycle; acyclic graphs are also called forests. A tree is a connected acyclic graph or, equivalently, one component of a forest. A spanning tree of an undirected graph GG is a subgraph that is a tree and contains every vertex of GG. A graph has a spanning tree if, and only if, it is connected. A spanning forest of GG is a collection of spanning trees, one for each component of GG.

Directed graphs require slightly different definitions. A directed walk is a sequence of vertices v0v1v2vlv_0 \rightarrow v_1\rightarrow v_2\rightarrow · · · \rightarrow v_l such that vi1viv_{i−1}\rightarrow v_i is a directed edge for every index ii; directed paths and directed cycles are defined similarly. Vertex vv is reachable from vertex uu in a directed graph GG if, and only if, GG contains a directed walk (and therefore a directed path) from uu to vv. A directed graph is strongly connected if every vertex is reachable from every other vertex. A directed graph is acyclic if it doesn’t contain a directed cycle; directed acyclic graphs are often called dags.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy