Graphs

Definition. A graph is a set of vertices and a collection of edges that each connect a pair of vertices.

Remarks.

• Also known as or emphasized by Undirected graph.
• Vertex is often called "node": For all graphs $G$, a node $v$ is equivalent to vertex $v$ for every $v$ in $V$

Tree

Definition. A tree is an acyclic connected graph. A disjoint set of trees is called a forest. A spanning tree of a connected graph is a subgraph that contains all of that graph's vertices and is a single tree. A spanning forest of a graph is the union of spanning trees of its connected components.

Directed graph

Definition. A directed graph (or digraph) is a set of vertices and a collection of directed edges. Each directed edge connects an ordered pair of vertices.

Remark. aka. Digraph

Directed acyclic graph

Definition. A directed acyclic graph is a digraph with no directed cycles.

Remark. aka. DAG

Bipartite graph

Definition. A graph $G = (V, E)$ is bipartite if its vertex set $V$ can be partitioned into two sets $X$ and $Y$ such that every edge has one end in $X$ and the other end in $Y$.

Properties

• If a graph $G$ is bipartite, then it cannot contain an odd cycle.

Common definitions among graphs and nomenclature

General

Definitions

• A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices).
• The length of a path or a cycle is its number of edges.

Odd cycle: a cycle of odd length.

Adjacency, Degree, and Subgraph

Adjacency: When there is an edge connecting two vertices, we say that the vertices are adjacent to one another and that the edge is incident to both vertices.

Degree of vertices: The degree of a vertex is the number of edges incident to it.

Subgraph: A subgraph is a subset of a graph's edges (and associated vertices) that constitutes a graph.

Undirected Context

Definition. A graph is connected if there is a path from every vertex to every other vertex in the graph. A graph that is not connected consists of a set of connected components, which are maximal connected subgraphs.

Definitions

• A path in a graph is a sequence of vertices connected by edges.
• A simple path is one with no repeated vertices.
• A cycle is a path with at least one edge whose first and last vertices are the same.

Directed Context

Definitions

• A directed path in a digraph is a sequence of vertices in which there is a (directed) edge pointing from each vertex in the sequence to its successor in the sequence.
• A directed cycle is a directed path with at least one edge whose first and last vertices are the same.
• A directed graph is strongly connected if, for every two vertices $u$ and $v$, there is a path from $u$ to $v$ and a path from $v$ to $u$.

Outdegree: the number of edges going from it.

Indegree: the number of edge going to it.

Mutually reachable: Two vertices $u$ and $v$ in a directed graph are mutually reachable if there is a path from $u$ to $v$ and also a path from $v$ to $u$. For example, a (directed) graph is strongly connected if every pair of vertices is mutually reachable.

Strong component: A strong component containing vertex $s$ is the set of all $v$ such that $s$ and $v$ are mutually reachable.

Reference(s)

• J. Kleinberg and É. Tardos, Algorithm Design. Pearson, 2006.
• R. Sedgewick and K. Wayne, Algorithms, 4th ed. Addison-Wesley, 2011.