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

Степінь вершини $v$ позначають $deg(v)$. Якщо $deg(v)=0$, то вершину $v$ називають ізольованою.

Нехай $G_1=(V_1, E_1)$ та $G_2=(V_2, E_2)$ – прості графи, а  $\varphi : V_1 \rightarrow V_2$ – бієкція.

Якщо такий ізоморфізм існує, то графи  $G_1$ та  $G_2$ називають ізоморфними та записують $G_1\simeq G_2$.

Інваріант – це властивість, яку довільні ізоморфні графи або обидва мають, або обидва не мають.

Вершину $u$ називають інцидентною дузі $e$, якщо $u$ – початкова чи кінцева вершина цієї дуги.

Вершину $v$ та ребро $e$ називають інцидентними, якщо вершина $v$ – кінець ребра $e$.

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