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

Нехай графи $H=(W,F)$  і $G=(V,E)$ – прості та $H$ – підграф графа $G$.

Підграф  $H$  називають каркасним підграфом (фактором), якщо  $W=V$.

Нехай  $R$ – відношення еквівалентності на множині  $A$.

Множину всіх елементів, які еквівалентні до елемента  $a\in A$, називають класом еквівалентності (елемента $a$) за відношенням  $R$, його позначають як $[a]_R$.

Колесом $W_n$ називається граф, який одержують із циклу $C_n$ додаванням іще однієї вершини, яку з’єднують з усіма $n$ вершинами в $C_n$  новими ребрами.

Нехай $R$ – відношення із множини $A$ в множину $B$, а $S$ – відношення із множини $B$ в множину $C$.

Композицією відношень $R$ і $S$ називають відношення, яке складається з усіх можливих упорядкованих пар $(a,c)$, де $a\in A$, $c\in C$, для яких існує такий елемент  $b\in B$, що $(a,b)\in R$ і $(b,c)\in S$. 

Композицію відношень $R$ та $S$  позначають як $S\circ R$ (ми пишемо справа перше з двох відношень, які беруть участь у композиції).

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

Кон’юнктивною нормальною формою (КНФ) називають кон’юнкцію $d_1\wedge d_2 \wedge ... \wedge d_s$ елементарних диз’юнкцій  $d_j, (j=\overline{1,s})$, у якій усі $d_j$ різні.

Кон’юнкція булевих  $m\times n$ матриць $P$ та $Q$ – це $m\times n$  матриця $Z=P\wedge Q$, елементи якої  $z_{ij}=p_{ij}\wedge q_{ij}$, де  $i=\overline{1,m}$, $j=\overline{1,n}$.

Елементарну диз’юнкцію, яка містить усі змінні з множини $X=\{x_1, x_2,..., x_n\}$, називають конституентою нуля.

Елементарну кон’юнкцію, яка містить усі змінні з множини $X=\{x_1, x_2,... ,x_n\}$, називають конституентою одиниці.

Дерево разом із виділеним коренем утворює орієнтований граф, який називають кореневим деревом.