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

Напівстепенем виходу вершини $v$ називають кількість дуг, для яких вершина $v$ початкова; позначають $deg^{+}(v)$.

В орієнтованому мультиграфі напівстепенем входу вершини $v$ називають кількість дуг, для яких вершина $v$  кінцева; позначають  $deg^{-}(v)$.

Граф називають незв’язним, якщо він не є зв’язним.

Змінну ${{x}_{i}}$ функції $f({{x}_{1}},...,{{x}_{i-1}},{{x}_{i}},{{x}_{i+1}},...,{{x}_{n}})$ називають неістотною (фіктивною), якщо $f({{x}_{1}},...,{{x}_{i-1}},0,{{x}_{i+1}},...,{{x}_{n}})=f({{x}_{1}},...,{{x}_{i-1}},1,{{x}_{i+1}},...,{{x}_{n}})$ для будь-яких значень решти змінних.

Якщо $a$ та $b$ – такі елементи, що ні $aRb$, ні $bRa$, то їх називають непорівнюваними.

Розглянемо двійкові набори значень змінних як записи цілих чисел у двійковій системі числення. 

Це означає, що набір ${{\widetilde{a}}^{n}}=(a_1,...,a_n)$ ототожнюють із записом числа ${{a}_{1}}\cdot {{2}^{n-1}}+{{a}_{2}}\cdot {{2}^{n-2}}+...+{{a}_{n-1}}\cdot 2+{{a}_{n}}$.  Це число називають номером набору ${{\widetilde{a}}^{n}}$.

Нормою (або вагою) набору  ${{\widetilde{a}}^{n}}$ називають число $\left\| {{\widetilde{a}}^{n}} \right\|$, яке дорівнює кількості його одиничних компонент.