Graphs

A graph is an abstract data type that can be used to represent complex, non-linear relationships between objects. A graph consists of nodes (also called vertices) that are connected by edges (also called arcs). Graphs have a lot of key terms:

• When two nodes are connected by an edge, they are called neighbours

• The degree of a node is the number of other nodes that it is connected to (i.e. the number of neighbours that it has)

• A loop is an edge that connects a node to itself

• A path is a sequence of nodes that are connected by edges

• A cycle is a closed path, i.e. a path that starts and ends at the same node (and no node is visited more than once)

Graphs are often shown as diagrams, with circles used to represent the nodes, and lines (or arrows) used to represent the edges. This is possible only for very small data sets. In real life, a graph can have many thousands of nodes

A graph can be used to represent a wide variety of complex data relationships. For example:

• Social networking: the nodes could be individual people. An edge could represent that two people are acquaintances.

• Transport networks: the nodes could be towns. An edge could represent that a train line connects two towns.

• The internet: the nodes could be routers. An edge could represent that two routers are connected.

• The World Wide Web: the nodes could be webpages. An edge could represent that the pages are linked.

There are many more complex areas where graphs can be used, for example in modelling chemical compounds, electrical circuits, and gene mapping.

More information can be recorded if a graph is directed and/or weighted. In the examples that follow, you will focus on an application where a graph is used to model some information about towns in East Anglia. This type of data could be used in a direction-finding GPS application on a smartphone.