What is a Graph?-Warm-up
Airlines Graph
()
Knight Transposition
()
Seven Bridges of Königsberg
()
Slides
What is a Graph?-Why Graphs?
What is a Graph?
()
Graph Examples
()
Graph Applications
()
Slides
What is a Graph?-Basic Definitions
Vertex Degree
()
Paths
()
Connectivity
()
Directed Graphs
()
Weighted Graphs
()
Slides
What is a Graph?-Basic Graphs
Paths, Cycles and Complete Graphs
()
Trees
()
Bipartite Graphs
()
Slides
Glossary
Hint for Guarini's Puzzle
Cycles-Handshaking Lemma
Handshaking Lemma
()
Total Degree
()
Slides
Cycles-Connected Components
Connected Components
()
Guarini Puzzle: Code
()
Lower Bound
()
The Heaviest Stone
()
Directed Acyclic Graphs
()
Strongly Connected Components
()
Slides
Cycles-Eulerian and Hamiltonian Cycles
Eulerian Cycles
()
Eulerian Cycles: Criteria
()
Hamiltonian Cycles
()
Genome Assembly
()
Slides
Glossary
Graph Classes-Trees
Road Repair
()
Trees
()
Minimum Spanning Tree
()
Slides
Graph Classes-Bipartite Graphs
Job Assignment
()
Bipartite Graphs
()
Matchings
()
Hall's Theorem
()
Slides
Graph Classes-Planar Graphs
Subway Lines
()
Planar Graphs
()
Euler's Formula
()
Applications of Euler's Formula
()
Slides
Glossary
Graph Parameters-Graph Coloring
Map Coloring
()
Graph Coloring
()
Bounds on the Chromatic Number
()
Applications
()
Slides
Graph Parameters-Cliques and Independent Sets
Graph Cliques
()
Cliques and Independent Sets
()
Connections to Coloring
()
Mantel's Theorem
()
Slides
Graph Parameters-Ramsey Numbers
Balanced Graphs
()
Ramsey Numbers
()
Existence of Ramsey Numbers
()
Slides
Graph Parameters-Vertex Cover
Antivirus System
()
Vertex Covers
()
König's Theorem
()
Slides
Glossary
Flows and Matchings-Networks, Flows, and Cuts
An Example
()
The Framework
()
Ford and Fulkerson: Proof
()
Hall's theorem
()
What Else?
()
Slides
Flows and Matchings-Stable Matchings
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
()
Slides
The algorithm and its properties (alternative exposition)
Flows and Matchings-The Project: Programming Gale-Shapley Algorithm
Gale-Shapley Algorithm
Project Description
Glossary