Graphs: Ruining the Travelling Salesman's Day Since 1930

Graphs are one of the most widely used abstractions in computer science. By representing systems as nodes connected by edges, they provide a powerful way to model relationships between objects and reason about complex problems in a structured way.

This talk explores the fundamentals of graphs and graph algorithms. It looks at how graphs are represented in software, examines core algorithms such as breadth-first search, depth-first search, and shortest path methods, and discusses classic optimisation problems including the Travelling Salesman Problem.

It also touches on an important theme in theoretical computer science: why some problems can be solved efficiently while others quickly become computationally difficult.

In this talk, the following are covered:

• What graphs are and why they appear so often in computer science
• Common ways to represent graphs in software
• Graph traversal algorithms such as breadth-first search and depth-first search
• Shortest path algorithms and their applications
• Classic optimisation problems including the Travelling Salesman Problem
• Why some graph problems are computationally difficult