Modelling with a graph

Vertices, edges and vocabulary

A universal model of relationships

A graph is a structure that connects objects to one another. Each object is a vertex (or node), and each link between two vertices is an edge. That's all — and yet this model describes a staggering number of situations:

Situation	Vertices	Edges
Social network	the people	"is friends with"
Road map	the cities	the roads
The Web	the pages	the hyperlinks
Metro	the stations	the line segments

Unlike a tree, a graph has neither root nor hierarchy: any vertex can be connected to any other, and there can even be cycles (loops).

        (A)------(B)
         |      / |
         |    /   |
         |  /     |
        (C)------(D)
                  |
                 (E)

Here A, B, C, D form a cycle: you can start from A and return to it without using the same edge twice.

Directed or undirected

An edge can be two-way (undirected) or one-way (directed, drawn with an arrow).

   Undirected :  A --- B      (friendship is mutual)

   Directed :    A --> B      (A follows B on a network,
                               but not necessarily the reverse)

A metro map is undirected (trains run both ways); a "who follows whom" network is directed.

Weighted: when edges carry a weight

Often, an edge carries a weight: a distance, a time, a cost. This is called a weighted graph.

        (A)--4--(B)
         |      /
         6    2
         |  /
        (C)

Finding the shortest path from A to B in such a graph (via A-B = 4, or via A-C-B = 6+2 = 8?) is one of the great problems of computer science.

The vocabulary to remember

Degree of a vertex: the number of edges touching it. In the first diagram, B has a degree of 3 (connected to A, C, D).
Neighbours of a vertex: the vertices directly connected to it.
Path: a sequence of edges leading from one vertex to another.
Cycle: a path that returns to its starting point.

In summary