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

Елемент частково впорядкованої множини називають максимальним, якщо він не менший за будь-який елемент цієї множини.

Матрицею інцидентності графа $G=(V,E)$, яка відповідає заданій нумерації вершин і ребер, називають булеву $n\times m$ матрицю $M$ з елементами  $m_{i,j} (i=\overline{1,n}, j=\overline{1,m})$, де 

$m_{i,j}=1$ , якщо вершина $v_i$ та ребро $e_j$ інцидентні, 

$m_{i,j}=0$  в протилежному випадку.

Матрицею інцидентності орієнтованого графа $G=(V,E)$, яка відповідає заданій нумерації вершин і дуг, називають $n\times m$ матрицю $M$ з елементами  $m_{i,j} (i=\overline{1,n}, j=\overline{1,m})$, де 

$m_{i,j}=1$ , якщо дуга $e_j$ виходить з вершини $v_i$, 

$m_{i,j}=-1$ , якщо дуга $e_j$ входить у вершину $v_i$,  

$m_{i,j}=2$ , якщо дуга $e_j$ - це петля у вершині $v_i$,  

$m_{i,j}=0$  в інших випадках,  

Матрицею суміжності графа $G=(V,E)$ (яка відповідає даній нумерації вершин) називають булеву $n\times n$ матрицю  $A$ з елементами $a_{i,j} (i,j=\overline{1,n})$, де

$a_{i,j}=1$, якщо $\{v_i, v_j\}\in E$,

$a_{i,j}=0$ в протилежному випадку.

Матрицею суміжності орієнтованого графа $G=(V,E)$ називають булеву $n\times n$ матрицю  $A$ з елементами $a_{i,j} (i,j=\overline{1,n})$, де

$a_{i,j}=1$, якщо $(v_i, v_j)\in E$,

$a_{i,j}=0$ в протилежному випадку.

Матриця, яка задає відношення $R$ на $n$ -елементній множині $A$ , – це $n\times n$ матриця $M_R=[m_{ij}]$,  $i,j=\overline{1,n}$, де

$m_{ij}=1$, якщо $(a_i , a_j)\in R$

$m_{ij}=0$, якщо $(a_i , a_j) \notin R$

Елемент називають мінімальним, якщо він не більший за будь-який елемент частково впорядкованої множини.

Ребро графа $G$ називають мостом, якщо його вилучення збільшує кількість компонент.

Елементарну кон’юнкцію називають монотонною, якщо вона не містить заперечень змінних.

Мультиграфом називають пару $(V,E)$, де $V$ – скінченна непорожня множина вершин, а $E$ – сім’я невпорядкованих пар різних елементів з множини $V$. Тут застосовано термін “сім’я” замість “множина”, бо елементи в $E$ (ребра) можуть повторюватись.