Chapter
Definition and calculation of complexity in graph theory
1:46:03 - 1:52:01 (05:58)
The complexity of a component in graph theory is the number of edges minus the number of vertices, with a cyclic component having a complexity of zero.
Clips
Students at Berkeley supervised by Dick Karp observed a unique phenomenon as they simulated the random evolution of graphs, where there was almost always a single component with a loop, and all loops stayed connected to that one with high probability.
1:46:03 - 1:47:33 (01:30)
Summary
Students at Berkeley supervised by Dick Karp observed a unique phenomenon as they simulated the random evolution of graphs, where there was almost always a single component with a loop, and all loops stayed connected to that one with high probability.
ChapterDefinition and calculation of complexity in graph theory
Episode#219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life
PodcastLex Fridman Podcast
This podcast explores the rumored loops in the universe which turned out to be almost true.
1:47:33 - 1:48:51 (01:18)
Summary
This podcast explores the rumored loops in the universe which turned out to be almost true. There's a short interval of time when separate loops exist, but they join together pretty quickly.
ChapterDefinition and calculation of complexity in graph theory
Episode#219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life
PodcastLex Fridman Podcast
The speaker explains the complexity of a component in graph theory and how it evolves as loops are introduced.
1:48:51 - 1:50:28 (01:36)
Summary
The speaker explains the complexity of a component in graph theory and how it evolves as loops are introduced.
ChapterDefinition and calculation of complexity in graph theory
Episode#219 – Donald Knuth: Programming, Algorithms, Hard Problems & the Game of Life
PodcastLex Fridman Podcast
The complexity of a graph is measured by the number of edges it has.
1:50:28 - 1:52:01 (01:32)
Summary
The complexity of a graph is measured by the number of edges it has. As the complexity increases, the number of loops in the graph also increases, creating additional edges over vertices. While the evolution of most graphs proceeds from a cycle to a bicycle, there is a certain probability that it will instead move to two different cycles.