MATH 3330: Applied Graph Theory

The development of the Internet and the World Wide Web has changed our outlook on the world. Science has followed suit with an increased emphasis on the study of networks. However, mathematicians have studied networks for over one hundred years. A network, to a mathematician, is a graph, and graph theory is a fertile research area on the cross-section of mathematics and computer science.

This course gives introduction to graph theory, with an emphasis on applications and modelling. The course is well suited for students doing a double major in Math and another subject such as Biology or Computer Science. It is also recommended for Science students with a strong interest in Math that want to take a third year Math elective. This course is a good choice for Math student that are considering a specialization in Graph Theory or Combinatorics, and for those that are aiming for a Math Education degree.

Note that, from next year, MATH 3330 (or CSCI 3110) will be a prerequisite for MATH 4330: Topics in Graph Theory.

Topics include:

• Paths, cycles and the concept of diameter: are all humans really connected by at most "six degrees of separation"?
• Shortest paths: What is the shortest way of routing packets through the Internet?
• Connectivity, strong connectivity, connected components: communities in social networks
• Connectivity and spanning trees: what is the minimum cost, or maximum reliability network needed to connect a set of servers?
• Minimum flow and maximum cut: how scheduling problems can be solved efficiently using graph theory
• Graph colouring: assigning radio frequencies in cellular networks
• Graph models: how graphs are used to model real-life networks such as ecological networks, the World Wide Web, the Internet, biological networks, and social networks.

• Instructor: Jeannette Janssen
• Time and place: TR 10:05-11:25, LSC 214