Graphs

A graph is an interesting and useful mathematical structure that can describe a network of connections between pairs of nodes. In a graph, we refer to the nodes as vertices, and the connections between pairs of vertices we call edges.


two drawings of the same graph

We can gain some intuition about the structure of a graph by drawing it as a collection of labeled dots (vertices) and connecting lines (edges). However, one should be aware that any given graph can be drawn in many different ways, as the graphic above demonstrates.

Graphs have many practical applications -- maps, web content, schedules, social networks, etc.

In some cases, one finds it natural to associate each connection with a direction -- such as a graph that describes traffic flow on a network of one-way roads. Here the edges are the roads themselves, while the vertices are the intersections and/or junctions between these roads. When each connection in a graph has a direction, we call the graph a digraph.

In other cases, it is more natural to associate with each connection some numerical "weight". Such graphs are called edge-weighted graphs. As an example, when describing a neural network, some neurons are more strongly linked than others. If the vertices of the graph represent the individual neurons, and edges represent connections between pairs of neurons, than the weight of an edge might measure the strength of the connection between two associated neurons.

Still other graphs might require both elements described above. Not surprisingly, such graphs are called edge-weighted digraphs. Appealing to economics this time for an example, note that a graph could be used to describe the flow of money between a group of individuals in a given time period. Using vertices to represent the individuals involved, two vertices could be connected if any money flowed from one to the other. The net amount of money that changed hands provides a weight for the edges of such a graph, and the direction of the connection could point towards the vertex that saw a net gain from the associated transactions.

Some Terminology

When there is an edge connecting two vertices, the vertices are said to be adjacent to one another and the edge is incident to both vertices. As examples, in the graph drawn below, vertices $3$ and $4$ are adjacent, while $1$ and $6$ are not. Edge d is incident to vertices $0$ and $6$, but is not incident to any other vertices.

Two edges that connect the same pair of vertices are called parallel, while an edge that connects a vertex to itself is called a loop. The degree of a vertex is the number of edges incident to that vertex, with loops counted twice. So, the degree of vertex $0$ in the graph below is $5$, while the degree of vertex $1$ in the same graph is $3$.

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

A path in a graph is a sequence of vertices connected by edges. A simple path is one with no repeated vertices. When the first and last vertices of a path (of at least one edge) are the same, we call the path a cycle. A simple cycle is a cycle with repeated vertices or edges (except the first and last vertices). An graph is said to be acyclic if it contains no cycles. The length of a path or cycle is its number of edges.

One vertex is said to be connected to another if there exists a path that contains them both. More generally, we say a graph is connected if there is a path from every vertex in the graph to every other vertex in the graph. Note, that graphs that are not connected necessarily consist of a set of connected components.