11Graph Theory328–387Chapter overviewOverviewIntroduction to Graph Theory328Graph Theory Concepts329graph storage330DFS (Graph Theory)331BFS (Graph Theory)345Directed Acyclic Graph346Topological Sorting354Steiner Trees355Node Splitting361Cycle Counting Problems362Minimum Cycle3632-SAT364Eulerian Graph365Hamiltonian graph366Bipartite graph367Planar graphs368Chordal Graphs369Graph Coloring382Prüfer Sequence383Matrix-Tree Theorem384The LGV Lemma385Maximum Clique Search Algorithm386Dominator Tree387Random walks on graphsTree Problems332Tree Basics333Tree Diameter334Center of a Tree335Tree Centroid336Lowest Common Ancestor337Heavy-light Decomposition338DSU on Tree339Virtual Tree340Tree divide and conquer341Dynamic Centroid Decomposition342AHU Algorithm343Tree Hashing344Random Walks on TreesShortest Path Problems347Shortest paths348Difference Constraints349k-th Shortest Path350Congruence Shortest PathSpanning Tree Problems351Minimum spanning tree352Directed minimum spanning tree353Minimum Diameter Spanning TreeConnectivity356Strongly Connected Components357Biconnected Components358Articulation Points and Bridges359Round-Square Tree360Vertex and Edge ConnectivityNetwork Flows370Introduction to Network Flows371Max Flow372Minimum cut373Minimum-cost flow374Flow with Lower and Upper Bounds375Stoer–Wagner AlgorithmGraph Matching376Graph matching377Maximum Bipartite Matching378Maximum-Weight Bipartite Matching379Blossom algorithm and general-graph matching380Maximum-weight matching in general graphs381Stable Matching