Голосарій курсу

Повне $m$-арне дерево, у якого всі листки на одному рівні, називають завершеним $m$-арним деревом.

Кореневе $m$-арне дерево з висотою $h$ називають збалансованим, якщо всі його листки на рівнях $h$ або $h-1$.

Неорієнтований граф називають зв’язним, якщо будь-які дві його вершини з’єднані шляхом.

Теорема. Нехай $G=(V,E)$ – неорієнтований граф з $m$ ребрами. Тоді $\sum_{v\in V} {deg(v)} =2m$.

Теорема. Нехай $G=(V,E)$ – орієнтований мультиграф, який має $m$ дуг. Тоді $\sum_{v\in V}{deg^{-}(v)}= \sum_{v\in V}{deg^{+}(v)}=m$.

Зваженим називають простий граф, кожному ребру $e$ якого приписано дійсне число $w(e)$. Це число називають вагою ребра  $e$ .

Зваженим орієнтованим графом називають орієнтований граф, кожній дузі $e$ якого приписано дійсне число $w(e)$. Це число називають вагою дуги $e$.