Graph Algorithms II
R. Balakrishnan, Sriraman Sridharan · Discrete Mathematics · 2019
In this chapter, another navigation process in a graph called Breadth-First Search(BFS) is studied. Two applications are presented: Testing if a graph is geodetic and finding a maximum matching. Then relation between matrices and bipartite graphs are studied. Birkhoff-von-neumann theorem concerning the decomposition of bistochastic matrices is proved. Finally, we present Kuhn-Munkres algorithm for finding optimal assignment of personnels to jobs(maximum weighted matching problem).