Share Description
We invite you to a fascinating journey into Graph Theory, a field that connects the elegance of painting with the rigour of mathematics; it is simple, but not uncomplicated. Graph Theory provides us with an easy way to graphically represent many major mathematical results, as well as insights into the deep theories that underpin them.
In this course, we'll look at how GPS systems find the shortest routes, how engineers design integrated circuits, how biologists assemble genomes, and why a political map can always be coloured with only a few colours. We will look at Ramsey Theory, which proves that complete disorder is impossible in a large system!
By the end of the course, we will have implemented an algorithm that finds the best way to assign students to schools. This algorithm, created by David Gale and Lloyd S. Shapley, was later honoured with the Nobel Prize in Economics.
We assume only basic math (e.g., you should know what a square is or how to add fractions), basic programming in Python (functions, loops, recursion), common sense, and curiosity as prerequisites. Our target audience includes anyone who works or plans to work in information technology, beginning with motivated high school students.
Syllabus :
1. What is a Graph?
- Airlines Graph
- Knight Transposition
- Seven Bridges of Königsberg
- What is a Graph?
- Graph Examples
- Graph Applications
- Vertex Degree
- Paths
- Connectivity
- Directed Graphs
- Weighted Graphs
- Paths, Cycles and Complete Graphs
- Trees
- Bipartite Graphs
2. CYCLES
- Handshaking Lemma
- Total Degree
- Connected Components
- Guarini Puzzle: Code
- Lower Bound
- The Heaviest Stone
- Directed Acyclic Graphs
- Strongly Connected Components
- Eulerian Cycles
- Eulerian Cycles: Criteria
- Hamiltonian Cycles
- Genome Assembly
3. Graph Classes
- Road Repair
- Trees
- Minimum Spanning Tree
- Job Assignment
- Bipartite Graphs
- Matchings
- Hall's Theorem
- Subway Lines
- Planar Graphs
- Euler's Formula
- Applications of Euler's Formula
4. Graph Parameters
- Map Coloring
- Graph Coloring
- Bounds on the Chromatic Number
- Applications
- Graph Cliques
- Cliques and Independent Sets
- Connections to Coloring
- Mantel's Theorem
- Balanced Graphs
- Ramsey Numbers
- Existence of Ramsey Numbers
- Antivirus System
- Vertex Covers
- König's Theorem
5. Flows and Matchings
- An Example
- The Framework
- Ford and Fulkerson: Proof
- Hall's theorem
- What Else?
- Why Stable Matchings?
- Mathematics and Real Life
- Basic Examples
- Looking For a Stable Matching
- Gale-Shapley Algorithm
- Correctness Proof
- Why The Algorithm Is Unfair
- Why the Algorithm is Very Unfair
