Graph Terminology

He offered a bet that we could name any person among earth’s one and a half billion inhabitants and through at most five acquaintances, one of which he knew personally, he could link to the chosen one.

— Frigyes Karinthy, Láncszemek1

The following presentation is loosely based on the first chapters of Graph Theory by Reinhard Diestel and Digraphs by Bang-Jensen and Gutin, and on the appendixes of Introduction to Algorithms by Cormen et al. (Note that the terminology and notation may differ between books; it is not completely standardized.) If you think it seems like there’s a lot to remember and understand, you probably ...

Get Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.