Learning outcomes

Develop mathematical understanding of graph theory as well as the ability to use graph theory for modeling purposes.

 

Goals

The course will introduce various real-life problems - such as Google's PageRank algorithm, finding the shortest path for a GPS system, assigning tasks to a group of people or machines, programming an AI to play chess, etc. - and will each time develop the mathematical concepts and theories behind these problems as well as the algorithms to solve them. Rigorous mathematical proofs of the properties and algorithms will be presented. The efficiency and complexity of the algorithms will also be studied.
 

Content

  • Basic definitions of graph theory, Eulerian graphs, Hamiltonian graphs
  • The different types of graphs, trees, planar graphs
  • Matrix notation of graphs, shortest path search, Dijkstra's algorithm
  • Cuts and connectivity, network robustness
  • Minimum weight spanning trees, algorithmic complexity
  • Min-max trees, construction of an artificial intelligence in game theory, alpha-beta pruning
  • Task assignment, couplings, covering graph
  • Edge coloring, Ramsey theory
  • Vertex coloring, chromatic polynomial, 4-color theorem
  • Centrality measures, Google Page Rank algorithm
  • Modeling a road transport network, Braess paradox
 

Assessment method

Details concerning the evaluation method are specified on the French language version of the descriptive sheet.
 

Sources, references and any support material

Syllabus on webcampus
 

Language of instruction

Français