Gain insights into key graph algorithms, including depth-first search, shortest paths, and flow networks. Explore their applications and foundational role in advanced computing disciplines.

This technology-agnostic course will teach you about many classical graph algorithms essential for a well-rounded software engineer. 

You will begin with an introduction to the running-time analysis of algorithms and the representation and structure of graphs. You’ll cover the depth-first search algorithm and its many applications, like detecting cycles, topological sorting, and identifying cut-vertices and strongly connected components. You will then cover algorithms for finding shortest paths and minimum spanning trees. You’ll also learn about the Ford-Fulkerson algorithm and its use in finding a maximum flow and minimum cut in networks. Moreover, you will adapt it to find maximum matchings and minimum vertex covers in bipartite graphs. Finally, you will learn about the Gale-Shapley algorithm for finding stable matchings.

The material in this course serves as a basis for other advanced algorithms, like parallel and distributed algorithms, and has many diverse applications in other computing disciplines.

Mastering Graph Algorithms

# Matchings and related terminology

A **matching** $M$ of an undirected graph $G$ is any collection of its edges that have no end-vertex in common. In other words, each edge in $M$ uniquely pairs or matches two vertices. We refer to the number of edges in a matching $M$ as the **size of the matching** $M$.
 
If a vertex appears as an end-vertex of an edge in $M$, we say it is **matched** by $M$. Otherwise, we say it is **unmatched** by $M$. Some examples of matchings in graphs are shown in the set of slides below.

 


Introduction

Review: Asymptotic Notation and Math Prerequisites

Working with Graphs

Depth-First Search and Applications

Prelude: Shortest Paths

Single-source Shortest Paths in Weighted Digraphs

All Pairs Shortest Paths

Minimum Spanning Tree

Flows

Matchings and Vertex Covers

Conclusion

Matchings

Matchings and related terminology