Подграфы

Пусть $G = (V, E)$ - граф, $H = (V', E')$ называется **подграфом** графа $G$, если $V' \subseteq V, E' \subseteq E$, при этом предполагается, что в $E'$ могут входить только те ребра, концы которых лежат в $V'$ ($E' \subseteq E \cap (V' \times V')$).

Подграф, у которого $V = V'$, называют **субграфом**.

$H = (V', E')$ - подграф $G = (V, E)$ и при этом если $\forall{v_i, v_j \in V'}\mathpunct{:}~~ v_i v_j \in E \Rightarrow v_i v_j \in E'$, то $H$ **порожденный (индуцированный)** множеством $V'$ подграф графа $G$.

**Циклом в графе** называется подграф, являющийся циклом.