Week 1

In this first week of the course we began by going over the course information (which you can find on this website) We then went on to take a tour of graph theory by looking at some various questions which can be solved by translating the problem into a graph and making inferences -introducing the necessary definitions along the way:
The 7 bridges of Konigsberg is the problem which sparked graph theory was solved in the negative by L. Euler in 1736.
Matching problems in bipartite graphs:

  1. How does Uber find the closest driver to pick you up?
  2. If you want \(n\) women to find their optimal suitor from a group of \(n\) men, can this always be done?
  3. If you split a deck of 52 cards into 13 piles of 4, is it always possible to pick out the sequence ace,2..,J,Q,K using one card from each pile?
Coloring problems:

  1. How does UTSC make sure that it schedules classes while minimizing conflicts for students?
  2. How many people do you need to put in a room to garantee either 3 people all know each other or they don't? More generally, we defined the Ramsey number \(R(m,n)\) here and explained how difficult it is to compute
Connectivity and paths:
  1. How does a hacker use graph theory to shut down a website?
  2. How does a GPS find the shortest route to your destination (we mentioned Dijkstra' algorithm here)
We also went on to introduce the idea of a morphism as an assigment \(G\longrightarrow G'\) between two graphs that respects the structure. We introduced the idea of an isomorphism as two graphs which have the same inherent structure but can look quite different when drawn. A nice example of this was the pentagon, which is isomorphic to the pentagram if you 'bend' the nodes a little