Applied Graph Theory
- To give a broad overview of problems and some resolutions in Graph Theory. The aim is to provide students with sufficient knowledge for them to naturally pick the good model when facing a “real-life” problem in the future. After choosing the model, the students should be able to adapt state-of-the-art algorithms to the situation and thus provide a solution with justifications (exact algorithms, approximation algorithm, theoretical complexity of task).
- Understand what is GT and where it can be applied.
- Understand and apply results on trees.
- Understand and apply results on connectivity.
- Understand and apply results on flows.
- Understand results about colouring of graphs.
- Understand and apply results on Large Graphs.
- Graph Theory an IntroductionIntroduction to the basic concepts of a graph, notations, and famous families of graphs. Several methods of storing a graph in computer's memory are presented.
- Trees, and search algorithmsA core concept of a graph is the notion of spanning trees. They can be seen as a skeleton and appear everywhere. Different ways to build them yield trees with dierent properties. Chosing the right tree is important.
- Connectivity, reachabilityA highly connected network is a robust network. In this chapter we see connectivity issues in graphs.
- Flows in networksHow to efficiently convey things in a network with capacities on the arcs/edges? This is our main question in this chapter. We see the algorithm of Ford-Fulkerson, the dual problem of minimum cut, and their applications.
- Hard problems: colorings of graphsThe chromatic number of a graph is much harder to compute than its connectivity. We discuss this large field.
- Large graphs and social networksA glimpse at metrics and method used for approaching large graphs.