To most people, a graph is a visual representation of a data set, like a bar chart or an EKG. That’s not what this chapter is about.

In this chapter, a **graph** is an
abstraction used to model a system that contains discrete,
interconnected elements. The elements are represented by **nodes** (also called **vertices**), and the interconnections are
represented by **edges**.

For example, you could represent a road map with one node for each city and one edge for each road between cities; or you could represent a social network using one node for each person, with an edge between two people if they are “friends” and no edge otherwise.

In some graphs, edges have different lengths (sometimes called “weights” or “costs”). For example, in a road map, the length of an edge might represent the distance between two cities, the travel time, or the bus fare. In a social network, there might be different kinds of edges to represent different kinds of relationships: friends, business associates, and so on.

Edges may be **undirected**, if they
represent a relationship that is symmetric, or **directed**. In a social network, friendship is
usually symmetric: if *A* is friends with
*B*, then *B* is friends with
*A*. So you would probably represent friendship with
an undirected edge. In a road map, you would probably represent a
one-way street with a directed edge.

Graphs have interesting mathematical properties, and there is a
branch of mathematics called **graph
theory** that studies them.

Graphs are also ...

Start Free Trial

No credit card required