8: Graphs

A graph is a structure consisting of a set of vertices \(\{v_{1},v_{2},\dots ,v_{n}\}\) and a set of edges \(\{e_{1},e_{2},\dots ,e_{m}\}\). An edge is a pair of vertices \(\{v_{i},v_{j}\}\ i,j\in \{1..n\}\). The two vertices are called the edge endpoints. Graphs are ubiquitous in computer science. They are used to model real-world systems such as the Internet (each node represents a router and each edge represents a connection between routers); airline connections (each node is an airport and each edge is a flight); or a city road network (each node represents an intersection and each edge represents a block). The wireframe drawings in computer graphics are another example of graphs.

A graph may be either undirected or directed. Intuitively, an undirected edge models a "two-way" or "duplex" connection between its endpoints, while a directed edge is a one-way connection, and is typically drawn as an arrow. A directed edge is often called an arc. Mathematically, an undirected edge is an unordered pair of vertices, and an arc is an ordered pair. For example, a road network might be modeled as a directed graph, with one-way streets indicated by an arrow between endpoints in the appropriate direction, and two-way streets shown by a pair of parallel directed edges going both directions between the endpoints. You might ask, why not use a single undirected edge for a two-way street. There's no theoretical problem with this, but from a practical programming standpoint, it's generally simpler and less error-prone to stick with all directed or all undirected edges.

An undirected graph can have at most \(\left({\begin{array}{c}n+1\\2\end{array}}\right)\) edges (one for each unordered pair), while a directed graph can have at most \(n^{2}\) edges (one per ordered pair). A graph is called sparse if it has many fewer than this many edges (typically \(O(n)\) edges), and dense if it has closer to \(\Omega (n^{2})\) edges. A multigraph can have more than one edge between the same two vertices. For example, if one were modeling airline flights, there might be multiple flights between two cities, occurring at different times of the day.

A path in a graph is a sequence of vertices \(\{v_{i_{1}},v_{i_{2}},\dots ,v_{i_{k}}\}\) such that there exists an edge or arc between consecutive vertices. The path is called a cycle if \(v_{i_{1}}\equiv v_{i_{k}}\). An undirected acyclic graph is equivalent to an undirected tree. A directed acyclic graph is called a DAG. It is not necessarily a tree.

Nodes and edges often have associated information, such as labels or weights. For example, in a graph of airline flights, a node might be labeled with the name of the corresponding airport, and an edge might have a weight equal to the flight time. The popular game "Six Degrees of Kevin Bacon" can be modeled by a labeled undirected graph. Each actor becomes a node, labeled by the actor's name. Nodes are connected by an edge when the two actors appeared together in some movie. We can label this edge by the name of the movie. Deciding if an actor is separated from Kevin Bacon by six or fewer steps is equivalent to finding a path of length at most six in the graph between Bacon's vertex and the other actors vertex. (This can be done with the breadth-first search algorithm found in the companion Algorithms book. The Oracle of Bacon at the University of Virginia has actually implemented this algorithm and can tell you the path from any actor to Kevin Bacon in a few clicks[1].)