18.095 Lecture Notes - Lecture 8: Bipartite Graph, Graph Matching, Lattice Path
Document Summary
How many ways are there to tile a chessboard. Enumerating tilings by hand is hopeless but there is an easier way. Counting vertex-disjoint lattice path systems: 3 traveling salespeople start in 3 origin cities (a, b, c). Astonishing fact: vertex-disjoint path systems are counted by a determinant. Reformulate the tiling problem as a graph matching problem. To the n x n chessboard we can associate a graph with n vertices. Each tiling of the board corresponds to a perfect matching of the graph. Perfect matching: a subset of the edges such that each vertex is connected to precisely 1 edge. Write down a matrix whose permanent counts graph matchings. Bipartite graph: a graph whose vertices can be partitioned into two subsets (colors) t and p such that all graph edges run from t to p, never within t or within ps. The bipartite adjacency matrix will help us count graph matchings.
