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

Петлі – ребра, які з’єднують вершину саму із собою.

Неорієнтований граф $H$ називають підграфом неорієнтованого графа $G=(V,E)$, якщо всі вершини графа $H$  належать $V$ , а всі його ребра належать $E$ .

Якщо $a$ – вершина дерева, то піддерево з коренем $a$  – це підграф, що містить $a$  та всі вершини – нащадки вершини $a$ , а також інцидентні їм ребра.

Нехай задано булеві функції $f(x)$ і  $g(x)$. 

Говорять, що функцію $h(x) = g(f(x))$ отримано підстановкою $f$ у $g$.

Дерево називають повним $m$-арним, якщо кожна його внутрішня вершина має точно $m$ синів. 

У разі $m=2$ дерево називають бінарним.

Повний граф з $n$ вершинами (позначають як $K_n$) – це граф, у якого будь-яку пару вершин з’єднано точно одним ребром.

Дводольний граф називають повним дводольним графом (позначають як $K_{m,n}$, де $m=|V_1|$, $n=|V_2|$), якщо кожну вершину з $V_1$ з’єднано ребром із кожною вершиною з $V_2$.

Граф $K_{1,n}$ називають зіркою.

Граф з $n$ вершинами називають позначеним, якщо його вершинам присвоєно якісь мітки, наприклад, числа $1,2,..., n$.

Формулу $P(\tilde{x}^n)=k_1 \oplus k_2 \oplus... \oplus k_s$, де $k_1, k_2,...k_s$  – попарно різні монотонні кон’юнкції змінних із множини $X=\{x_1, x_2,..., x_n\}$, називають поліномом Жегалкіна.

Два елементи $a$ та $b$ частково впорядкованої множини $(A,R)$ називають порівнюваними, якщо $aRb$ або $bRa$.