Combinatorics

Graph Theory

• Fundamentals of Graph Theory
  • Graph Notations
  • Walk and Path Notations
  • Graph Operations
  • Graph Isomorphisms
  • Eulerian Trails
• Search in Graph Theory
  • Search Forests
  • Search Colorings and Timestamps
  • The Topological Sort Problem
  • Kosaraju's SCC Algorithm
  • Tarjan's Cut Vertex / Edge Algorithms
  • Tarjan's SCC Algorithm
• The Shortest Path Problems
  • Fundamental Theorem of Shortest Path Problem
  • Bellman-Ford SSSP Algorithm
  • Dijkstra's SSSP Algorithm
  • Shortest Path Problem in DAG
  • Matrix Exponentiation Based APSP Algorithm
  • Floyd-Warshall APSP Algorithm
  • Johnson's APSP Algorithm
• Matchings in Bipartite Graphs
  • Characterization of Maximum Matchings
  • König-Egerváry Theorem
  • The Hungarian Algorithm
  • Hopcroft-Karp Algorithm
• The Network Flow Problem
  • Characterization of Maximum Flows
  • Ford-Fulkerson Method
  • Edmonds-Karp Algorithm
• k-Connectivity of Graphs
  • k-Connectivity of Graphs
  • Biconnectivity of Graphs
  • Menger's Theorem
• Happy "Tree" Friends
  • Cayley's Formula and Prüfer Sequences
  • Minimum Spanning Tree Problem
  • Center of Graphs and Trees
  • Kirchhoff's Matrix-Tree Theorem

Matroid Theory

• Fundamentals of Matroid Theory
  • Independent Sets and Bases
  • Rank Function
  • Dependent Sets and Circuits
  • Span Function
  • Dual Matroids (The Non-Topological Part)
  • Matroid Isomorphisms
• Matroid Intersection Theorem
  • Construction of Exchange Graphs
  • The Main Theorem
  • König-Egerváry Theorem from Matroid Theory
  • Matroid Union Theorem
  • Weighted Matroid Intersection