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