1.2: Graph Theory

Last updated
Save as PDF

Page ID: 70852

Joy Morris
University of Lethbridge

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

When a mathematician talks about graph theory, she is not referring to the “graphs” that you learn about in school, that can be produced by a spreadsheet or a graphing calculator. The “graphs” that are studied in graph theory are models of networks.

Any network can be modeled by using dots to represent the nodes of the network (the cities, computers, cell phones, or whatever is being connected) together with lines to represent the connections between those nodes (the roads, wires, wireless connections, etc.). This model is called a graph. It is important to be aware that only at a node may information, traffic, etc. may pass from one edge of a graph to another edge. If we want to model a highway network using a graph, and two highways intersect in the middle of nowhere, we must still place a node at that intersection. If we draw a graph in which edges cross over each other but there is no node at that point, you should think of it as if there is an overpass there with no exits from one highway to the other: the roads happen to cross, but they are not connecting in any meaningful sense.

Example $\PageIndex{1}$

The following diagram:

$clipboard_e8adbc4710c224e190fc8e207ea02afbd.png$

is a graph.

Many questions that have important real-world applications can be modeled with graphs. These are not always limited to questions that seem to apply to networks. Some questions can be modeled as graphs by using lines to represent constraints or some other relationship between them (e.g. the nodes might represent classes, with a line between them if they cannot be scheduled at the same time, or some nodes might represent students and others classes, with a line between a student and each of the classes he or she is taking).

After studying graph theory in this course, you should be able to solve problems such as:

How can we find a good route for garbage trucks to take through a particular city?
Is there a delivery route that visits every city in a particular area, without repetition?
Given a collection of project topics and a group of students each of whom has expressed interest in some of the topics, is it possible to assign each student a unique topic that interests him or her?
A city has bus routes all of which begin and end at the bus terminal, but with different schedules, some of which overlap. What is the least number of buses (and drivers) required in order to be able to complete all of the routes according to the schedule?
Create a schedule for a round-robin tournament that uses as few time slots as possible.

Some of these questions you may only be able to answer for particular kinds of graphs.

Graph theory is a relatively “young” branch of mathematics. Although some of the problems and ideas that we will study date back a few hundred years, it was not until the 1930s that these individual problems were gathered together and a unified study of the theory of graphs began to develop.