Подграфы

Подграфом графа G=(V, E) называется граф G=(V, E), у которого множества вершин и ребер V и E являются такими подмножествами множеств V и E соответственно, что ребро (v_i, v_j)E тогда и только тогда, когда вершины v_i и v_jV. Граф G называется собственным подграфом графа G, если V V и E E. Если все вершины графа G присутствуют в его подграфе G, т.е. V=V, то G называется остовным подграфом G.

Подграф без изолированных вершин называется реберно-порожденным подграфом. Множество вершин реберно-порожденного подграфа полностью определяется множеством его ребер.

Если же множество вершин подграфа полностью определяет множество его ребер, то такой подграф называется вершинно-порожденным. Заметим, что множество ребер вершинно-порожденного подграфа является таким максимальным подмножеством множества ребер графа, что концевые вершины всех этих ребер принадлежат подграфу.

Н а рисунке 14 изображены: (а) исходный граф; (б) собственный подграф; (в) остовный подграф; (г) реберно-порожденный подграф; (д) вершинно-порожденный подграф.