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

Граф, який містить гамільтонів цикл, часто називають гамільтоновим графом.

Цикл $x_0, x_1,... , x_{n-1}, x_0$ (тут $n \geq 3$) у графі $G$ називають гамільтоновим циклом, якщо $x_0, x_1,... , x_{n-1}$ – гамільтонів шлях.

Шлях $x_0, x_1, ..., x_{n-1}$ у неорієнтованому зв’язному графі $G=(V,E)$, $V=\{ v_1,..., v_n\}$ називають гамільтоновим шляхом, якщо  $x_i\in V$ і  $x_i \neq x_j$ для $0\leq i < j\leq n-1$ .                   

Формула $F$ має глибину $k+1$, якщо вона має вигляд  $F=f_i(F_1,..., F_n_i)$, де $f_i\in Q$, $Q=\{f_1,..., f_m\}$  -- множина елементарних функцій, $n_i$ – кількість аргументів $f_i$,  а $F_1,..., F_n_i$  – формули, максимальна з глибин яких дорівнює $k$.

Граф $G_R$, який задає відношення $R$ на множині $A$, будують так.

Вершини графа позначають елементами цієї множини, а дуга $(a_i ,a_j)$ існує тоді й лише тоді, коли пара $(a_i ,a_j) \in R$ . Такий граф $G_R$ називають графом, асоційованим із відношенням $R$, або просто графом відношення $R$.