Разница между остовным и порождённым подграфом в теории графов заключается в следующем:
- Остовный подграф имеет то же самое множество вершин, что и исходный граф, но множество дуг подграфа является подмножеством множества дуг исходного графа. 1
- Порождённый подграф состоит из подмножества вершин множества вершин исходного графа и всех таких дуг графа, у которого конечные и начальные вершины принадлежат подмножеству. 1 Другими словами, порождённый подграф содержит все возможные (для своего множества вершин) рёбра графа. 3
Таким образом, остовный подграф содержит все вершины исходного графа, а порождённый — все возможные рёбра для определённого подмножества вершин. 34