Подграф

Граф H={V_H;E_H} называется подграфом графа G={V_G;E_G}, если V_HÍV_G и E_HÍE_G; в этом случае говорят, что H содержится в G. Если V_H=V_G, то H - остовный подграф (фактор) графа G. Говорят, что подграф H порожден множеством вершин U, если V_H=U и множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат U.

Аналогично вводится понятие подграфа, порожденного множеством ребер E¢. У такого подграфа множество ребер совпадает с E¢, а множество вершин есть множество концов ребер из E¢.

Для того чтобы получить некоторый подграф исходного графа, используются следующие операции:

- удаление выбранного ребра при сохранении имеющихся вершин;

- удаление выбранной вершины вместе со всеми инцидентными ей ребрами.

Удаление произвольного множества вершин или ребер из графа G можно осуществить путем последовательного удаления всех элементов этого множества. Порядок удаляемых элементов при этом несущественен.