Подграфы

Граф G '(V', Е ') называется подграфом графа G (V, E) (обозначается ), если и/или .

Подраф G '(V', Е ') называется остовным подграфом графа G (V, E), если , то есть остовный подграф G ' содержит все вершины графа G (V, E).

Если и и , то подграф G '(V', Е ') называется собственным подграфом графа G (V, E).

Подграф G '(V ', E ') называется правильным подграфом графа G (V, E), если G ' содержит все возможные ребра G:

.

Правильный подграф G '(V ', Е ') графа G (V, Е) определяется подмножеством вер­шин V '.

На рис. 5 приведен пример графа G, а также варианты его остовного подграфа, собственного подграфа и правильного подграфа.