Connecting the Dots: Milestones in Graph Theory

Graph theory is the study of connections, as may be seen in the London Underground map with stations linked by rails, or a transportation network with cities linked by roads. Dating back to the 18th century, the subject increasingly took hold in the 20th century, developing rapidly from mainly recreational puzzles to a mainstream area of study with widespread applications and strong links to computer science.
This illustrated historical talk will survey this century of development.
A lecture recorded by Robin Wilson on 13 June 2023 at Barnard's Inn Hall, London
The transcript and downloadable versions of the lecture are available from the Gresham College website:
www.gresham.ac...
Gresham College has offered free public lectures for over 400 years, thanks to the generosity of our supporters. There are currently over 2,500 lectures free to access. We believe that everyone should have the opportunity to learn from some of the greatest minds. To support Gresham's mission, please consider making a donation: gresham.ac.uk/...
Website: gresham.ac.uk
Twitter: / greshamcollege
Facebook: / greshamcollege
Instagram: / greshamcollege

[@monicaaparecidaoliveira8063]

I learn a great deal with these lectures. Thank you Gresham College.

[@davecgriffith]

Great talk. Thanks for making these available!

[@barneylaurance1865]

Just started watching, surprised to see the claim / definition at the start that a graph with no cycles is a tree. I use the git version control system, which has a graph of versions of a software product, connected by "parent" relationships (e.g. version 1.0.0 may be the parent of version 1.0.1). That graph is generally described as a directed acyclic graph, but not a tree. It's the same as a "family tree". It's not a mathematical tree because branches can split and come back together - you can have multiple children, and you can also have children with your own relative (not taboo if it's a distant relative). Branches on a tree mostly don't come back together after they split apart.

[@roys4244]

Interesting points. There is a matter of Graph Theory terminology here. Graphs are defined as undirected, so the definition of tree given works. However, as you point out, for Directed Graphs the property "does not have a cycle" defines a DAG, and not a tree which is a special case. Also you point out that a family tree is not actually a tree!

[@jonaskoelker]

@@roys4244 > Graphs are defined as undirected, so the definition of tree given works. Only if the graph is connected. Every non-directed non-connected acyclic graph is a forest, not a tree.

[@bazsnell3178]

He might be a very clever guy with loads of academic qualifications, but a public speaker he sure ain't.

[@ctrl1961]

Don't get this comment. He seems cogent and interesting to me.

[@raebeesknees]

Disagree, He is charismatic, to the point, and funny. He does this all while painting a connected history. Great public speaker.