Stanford Lecture - Strong Components and Weak Components, Dr. Donald Knuth I 2024

The 28th annual Christmas lecture Thursday, December 5, 2024 A directed graph can often be best understood and used if we partition its vertices into separate components of various kinds. Most important are the strongly connected components, called “strong components” for short; and strong components are in turn partitioned into “weak components.” Two definitions of weak components have appeared in the literature of graph theory. One of them is rather weak and uninteresting, while the other is becoming more and more relevant and appreciated (see weak components revived). Basically, the strong components are the smallest clusters of vertices that you can shrink to a point and obtain a dag, a digraph with no oriented cycles. The weak components, correctly defined, are the smallest clusters that you can shrink to a point and obtain an oriented path. Dr. Knuth will discuss Robert Tarjan's beautiful algorithms for computing the strong and weak components of a given directed graph. (This will be fun because Dr. Knuth's personal favorite, among all of the algorithms of all kinds that he has encountered so far in his life, is Tarjan's method for discovering the strong components as it explores the graph.) Furthermore, if time permits, Dr. Knuth disclose the answer to the following riddle: In what major world city are shirts of size XL smaller than shirts of size L? See more from Don Knuth: https://online.stanford.edu/donald-e-knuth-lectures ► Check out our entire catalog of courses and programs: https://online.stanford.edu/explore