3.03.1. Подграфы и операции на графах. Подграфы

Граф H называется Подграфом графа G (пишут: H Í G), если V(H) Í V(G) и E(H) Í E(G). Если для подграфа H графа G V(H)=V(G), то H называется Остовным подграфом.

Если подграф H содержит все рёбра графа G, оба конца которых принадлежат множеству U Ì V(G), то H называется подграфом Порождённым (Индуцированным) множеством вершин U. Такой подграф H обозначается: G(U).

Рассматриваются также подграфы, порождённые данным подмножеством рёбер графа G, которые вместе с указанными рёбрами содержат все их концы в качестве множества вершин.

Важным классом подграфов являются подграфы, полученные из данного графа G удалением некоторой вершины V (при этом удаляются также все рёбра, инцидентные V). Обозначение полученного подграфа: Gv. Понятно, что Gv = G(V(G)\{V}).

Для графа G на следующем рисунке приведены примеры вышеуказанных подграфов:

< Предыдущая		Следующая >