Подграфы

Подграфом графа 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 изображены: (а) исходный граф; (б) собственный подграф; (в) остовный подграф; (г) реберно-порожденный подграф; (д) вершинно-порожденный подграф.