ПОДГРАФЫ

Граф называется подграфомграфа , если и являются подмножествами R и , причем ребро содержится в только в том случае, если его концевые вершины содержатся в .

Пусть –некоторое подмножество множества вершин графа и пусть – множество всех ребер графа G, концевые вершины которых входят в . Тогда граф называется вершинно-порожденным подграфом графа G. Обозначим через некоторое подмножество множества ребер графа G и пусть есть множество всех вершин графа G, инцидентных ребрам из . Тогда граф называется реберно-порожденным подграфом графа G.

Рисунок 3.

На рис. 3 изображены вершинно-порожденный подграф , представленного на рис. 11.1 (множество вершин ), и реберно–порожденный подграф того же графа G (того же графа G ( множество ребер ).