Определение 1. Связный граф без циклов называется деревом.

Определение 2. Вершина дерева, имеющая степень 1, называется висячей.

По аналогии с генеалогическими деревьями вводятся родовые понятия для вершин.

Пример.

 

 

 

 

 

 

 

Вершина x₁ называется корневой, пути от нее называются ветвями. Вершина x₂ называется родительской по отношению к вершинам x₄, x₅, x₆ и прародительской по отношению к вершинам x₈, x₉. Вершины x₂ и x₃ называются дочерними к вершине x₁.

Теорема. Дерево с n вершинами имеет n-1 ребро.