7. Graph Theory#

Graphs! Not plots, as in Plots of functions. Nor is it “graph of a function”.

A graph is one of the most foundational and useful data structures in computer science. If there’s two things in discrete mathematics to take into the rest of your computer science studies it is induction and graphs.

../_images/graph1.svg

Fig. 7.1 A graph with 5 vertices and 6 edges.#

In their simplest form, a graph is nothing more than vertices (nodes, dots, circles, squares, shapes), connected by edges (lines between vertices).

Graphs are incredibly useful in practice and have countless applications. To name just a few:

  • Computers in a network (e.g. the internet)

  • Destinations in a transport network (e.g. bus stops, airports)

  • Social connections (e.g. friends on Facebook)

  • Semantic and conceptual connections (e.g. fish is “related” to ocean)

  • Components of a software system (e.g. classes, modules, libraries)

In this chapter we will explore graphs as mathematical objects, their properties, how to encode graphs on computers, and their applications in practice.