Начнём знакомство с графами с самыми простыми с точки зрения их структуры графами --- корневыми деревьями.
Напомним, деревом называется связный граф без циклов.
Дерево с отмеченной вершиной — корнем — называется корневым деревом.
В отличие от обычных деревьев, корневые обычно рисуют корнем к верху.
Итак, отмеченную вершину называют корнем.
Как известно, в дереве между любыми двумя вершинами существует ровно один путь.
Возьмём любую вершину и соединим её путём с корнем.
Все вершины в этом пути, кроме исходной, называются её предками (ancestor).
Вершина, следующая в этом пути за исходной, называются её родителем (parent).
Корень — это единственная вершина в дереве, у которой нет ни родителей, ни предков вообще.
На этой картинке Grace, Alice и Jake являются предками Luca, Caitlin и Jake — предками Ben.
Jake является общим предком Luca и Ben (а заодно и общим предком вообще всех вершин).
Если вершина А является предком вершины Б, то Б называется потомком (descendant) А.
Для данной вершины А множеством её потомков являются все вершины, не совпадающие с А, путь из которых к корню проходит через А.
Аналогично, если вершина А — родитель вершины Б, то вершина Б называется сыновьей (child) для А.
Здесь уже всё понятно, у каждой вершины, кроме корня, есть единственный родитель.
Luca — единственный потомок Grace.
У Caitlin четыре потомка — Ben, Megan, Eva и Harry.
И наконец у Sean нет потомков.
Вершины, у которых общий родитель, называются братьями (sibling).
И наконец вершины, у которых нет потомков, называются листьями.