In the mathematical field of graph theory, a graph is akin to a network, having points (technical term: "vertices") and lines connecting points ("edges").
Example 1
Think about a social network—LinkedIn, say. If we think of each person as a point, we connect two points if they are connected on LinkedIn. What we have, then, is a graph, albeit a rather large one (approximately 530 million points as of January 2018).
Pare this down a little to something more manageable: your own personal network of contacts. In that network, how many "triangles" are there, that is, triples of people in which all three people know each other? Graph theory has a neat way to answer that question using a matrix associated to your network. Graph theory, then, has connections to linear algebra.
Example 2
We could depict all the roads in Alberta in the form of a graph. We represent intersections by points, and we represent stretches of road between intersections by lines. We could even go one step further and add distance information to the graph, describing how long the stretch of road is between any two intersections.
Modelling the road network in this stripped-down way, we're in a stronger position to answer questions such as:
- What is the shortest route between two given places in Alberta?
- If Carmen Rasmusen wanted to do a tour of Alberta, hitting the ten largest cities, what route would minimize the total distance she travelled?
- Is there a route she could take that would allow her to avoid passing through the same city twice?
Course topics
The topics to be covered in the course are not final until the course syllabus is released, but likely possibilities are:
- Basic types of graph
- Paths (journeys in which you never hit the same vertex twice)
- Cycles (journeys where you return to your start point but without hitting any other vertex twice)
- Trees ("connected" graphs that contain no cycles)
- Planarity (the subject of which graphs can be drawn in the plane without any edges crossing each other)
- Colouring (e.g., how many colours do we need in order to colour the vertices of a graph such that no two adjacent vertices have the same colour?)
- Digraphs (graphs in which each edge has a direction)