Подграфы

Пусть , – два графа, для которых , ; тогда говорят, что является подграфом графа . В свою очередь, граф по отношению к своему подграфу является надграфом. Если и , то такой подграф называется остовным. Любой остовный подграф графа может быть получен путем удаления подмножества ребер надграфа.

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

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