Graph Theory Unit

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.  A graph in this context is made up of vertices and edges. A main distinction is made between connected graphs and disconnected graphs. Graphs are one of the prime objects of study in Discrete Mathematics.

Graphs can be used to model many types of relations and processes in physical, biological, social and information systems.  In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation etc.  Graph theory is also used to study molecules in chemistry and physics.  Graph theory is widely used in sociology as a way, for example, to measure actors’ prestige or to explore rumor spreading, notably through the use of social network analysis software.

Leonhard Euler (1707 - 1783)

Johann Benedict Listing (1808 - 1882)

The paper written by Leonhard Euler on the Seven Bridges of Königsberg that was published in 1736 is regarded as the first paper in the history of graph theory.  More than one century after Euler’s paper was written, Johann Benedict Listing was introducing the concept of topology and Arthur Cayley was working with a particular class of graphs called trees.  Cayley’s work has many implications for theoretical chemistry.

Arthur Cayley (1821 - 1895)

Lecture Notes & Other Resources

TENTATIVE SCHEDULE FOR THE UNIT

Graph Theory - Introduction

-----MOVIE CLIP: Good Will Hunting
Will Hunting writes down Cayley's Tree Formula stating that the number of labeled trees on n nodes is n^n-2. Then he lists 8 different unlabeled trees with 10 nodes.

Permission Slip for Good Will Hunting

Graph Theory - Day 1
Introduction to Graph Theory (Graph, Vertex, Edge, Loop, Circuit)

Graph Theory Problems: The Three Utilities Problem and Santa Claus's House

Graph Theory - Day 2
Euler Paths & Circuits, Hamiltonian Paths & Circuits

Real-Life Examples of Networks

Graph Theory - Day 3
Hamiltonian Paths & Circuits - Continued

Graph Theory - Day 4
Spanning Trees and Kruskal's Algorithm

Graph Theory Unit Project

Graph Theory Summary of Definitions and Algorithms

Good Will Hunting Explained PDF/PowerPoint

-----VIDEO: The Problem in Good Will Hunting Explained - Numberphile

-----VIDEO: Who was the REAL Good Will Hunting?

---